I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Prime triangle

Prime triangle
You are encouraged to solve this task according to the task description, using any language you may know.

You will require a function f which when given an integer S will return a list of the arrangements of the integers 1 to S such that g1=1 gS=S and generally for n=1 to n=S-1 gn+gn+1 is prime. S=1 is undefined. For S=2 to S=20 print f(S) to form a triangle. Then again for S=2 to S=20 print the number of possible arrangements of 1 to S meeting these requirements.

## ALGOL 68

Iterative, backtracking solution - similar to the Phix and Wren versions but not recursive. Counts the arrangements but does not store them.

Works with: ALGOL 68G version Any - tested with release 2.8.3.win32

As Algol 68G under Windows is fully interpreted, a reduced number of rows is produced.

`BEGIN # find solutions to the "Prime Triangle" - a triangle of numbers that sum to primes #    INT max number = 18; # largest number we will consider #    # construct a primesieve and from that a table of pairs of numbers whose sum is prime #    [ 0 : 2 * max number ]BOOL prime;    prime[ 0 ] := prime[ 1 ] := FALSE;    prime[ 2 ] := TRUE;    FOR i FROM 3 BY 2 TO UPB prime DO prime[ i ] := TRUE  OD;    FOR i FROM 4 BY 2 TO UPB prime DO prime[ i ] := FALSE OD;    FOR i FROM 3 BY 2 TO ENTIER sqrt( UPB prime ) DO        IF prime[ i ] THEN            FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] := FALSE OD        FI    OD;    # returns the number of possible arrangements of the integers for a row in the prime triangle #    PROC count arrangements = ( INT n )INT:         IF   n < 2 THEN # no solutions for n < 2 # 0         ELIF n < 4 THEN             # for 2 and 3. there is only 1 solution: 1, 2 and 1, 2, 3 #             FOR i TO n DO print( ( whole( i, -3 ) ) ) OD; print( ( newline ) );             1         ELSE             # 4 or more - must find the solutions #             BOOL print solution := TRUE;             [ 0 : n ]BOOL used;             [ 0 : n ]INT  number;             # the triangle row must have 1 in the leftmost and n in the rightmost elements #             # the numbers must alternate between even and odd in order for the sum to be prime #             FOR i FROM 0 TO n DO                 used[   i ] := FALSE;                 number[ i ] := i MOD 2             OD;             used[   1 ] := TRUE;             number[ n ] := n;             used[   n ] := TRUE;             # find the intervening numbers and count the solutions #             INT count := 0;             INT p     := 2;             WHILE p > 0 DO                 INT p1      = number[ p - 1 ];                 INT current = number[ p     ];                 INT next   := current + 2;                 WHILE IF next >= n THEN FALSE ELSE NOT prime[ p1 + next ] OR used[ next ] FI DO                     next +:= 2                 OD;                 IF next >= n THEN next := 0 FI;                 IF p = n - 1 THEN                     # we are at the final number before n #                     # it must be the final even/odd number preceded by the final odd/even number #                     IF next /= 0 THEN                         # possible solution #                         IF prime[ next + n ] THEN                             # found a solution #                             count +:= 1;                             IF print solution THEN                                 FOR i TO n - 2 DO                                     print( ( whole( number[ i ], -3 ) ) )                                 OD;                                 print( ( whole( next, -3 ), whole( n, - 3 ), newline ) );                                 print solution := FALSE                             FI                         FI;                         next := 0                     FI;                     # backtrack for more solutions #                     p -:= 1                     # here will be a further backtrack as next is 0 ( there could only be one possible number at p - 1 ) #                 FI;                 IF next /= 0 THEN                     # have a/another number that can appear at p #                     used[ current ] := FALSE;                     used[    next ] := TRUE;                     number[     p ] := next;                     p +:= 1                 ELIF p <= 2 THEN                     # no more solutions #                     p := 0                 ELSE                     # can't find a number for this position, backtrack #                     used[ number[ p ] ] := FALSE;                     number[       p   ] := p MOD 2;                     p -:= 1                 FI             OD;             count         FI # count arrangements # ;    [ 2 : max number ]INT arrangements;    FOR n FROM LWB arrangements TO UPB arrangements DO        arrangements[ n ] := count arrangements( n )    OD;    FOR n FROM LWB arrangements TO UPB arrangements DO        print( ( " ", whole( arrangements[ n ], 0 ) ) )    OD;    print( ( newline ) )        END`
Output:
```  1  2
1  2  3
1  2  3  4
1  4  3  2  5
1  4  3  2  5  6
1  4  3  2  5  6  7
1  2  3  4  7  6  5  8
1  2  3  4  7  6  5  8  9
1  2  3  4  7  6  5  8  9 10
1  2  3  4  7 10  9  8  5  6 11
1  2  3  4  7 10  9  8  5  6 11 12
1  2  3  4  7  6  5 12 11  8  9 10 13
1  2  3  4  7  6 13 10  9  8 11 12  5 14
1  2  3  4  7  6 13 10  9  8 11 12  5 14 15
1  2  3  4  7  6  5 12 11  8 15 14  9 10 13 16
1  2  3  4  7  6  5 12 11  8  9 10 13 16 15 14 17
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18
1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464
```

## C

`#include <assert.h>#include <stdbool.h>#include <stdio.h>#include <time.h> bool is_prime(unsigned int n) {    assert(n < 64);    static bool isprime[] = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0,                             0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1,                             0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1,                             0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0};    return isprime[n];} void swap(unsigned int* a, size_t i, size_t j) {    unsigned int tmp = a[i];    a[i] = a[j];    a[j] = tmp;} bool prime_triangle_row(unsigned int* a, size_t length) {    if (length == 2)        return is_prime(a[0] + a[1]);    for (size_t i = 1; i + 1 < length; i += 2) {        if (is_prime(a[0] + a[i])) {            swap(a, i, 1);            if (prime_triangle_row(a + 1, length - 1))                return true;            swap(a, i, 1);        }    }    return false;} int prime_triangle_count(unsigned int* a, size_t length) {    int count = 0;    if (length == 2) {        if (is_prime(a[0] + a[1]))            ++count;    } else {        for (size_t i = 1; i + 1 < length; i += 2) {            if (is_prime(a[0] + a[i])) {                swap(a, i, 1);                count += prime_triangle_count(a + 1, length - 1);                swap(a, i, 1);            }        }    }    return count;} void print(unsigned int* a, size_t length) {    if (length == 0)        return;    printf("%2u", a[0]);    for (size_t i = 1; i < length; ++i)        printf(" %2u", a[i]);    printf("\n");} int main() {    clock_t start = clock();    for (unsigned int n = 2; n < 21; ++n) {        unsigned int a[n];        for (unsigned int i = 0; i < n; ++i)            a[i] = i + 1;        if (prime_triangle_row(a, n))            print(a, n);    }    printf("\n");    for (unsigned int n = 2; n < 21; ++n) {        unsigned int a[n];        for (unsigned int i = 0; i < n; ++i)            a[i] = i + 1;        if (n > 2)            printf(" ");        printf("%d", prime_triangle_count(a, n));    }    printf("\n");    clock_t end = clock();    double duration = (end - start + 0.0) / CLOCKS_PER_SEC;    printf("\nElapsed time: %f seconds\n", duration);    return 0;}`
Output:
``` 1  2
1  2  3
1  2  3  4
1  4  3  2  5
1  4  3  2  5  6
1  4  3  2  5  6  7
1  2  3  4  7  6  5  8
1  2  3  4  7  6  5  8  9
1  2  3  4  7  6  5  8  9 10
1  2  3  4  7 10  9  8  5  6 11
1  2  3  4  7 10  9  8  5  6 11 12
1  2  3  4  7  6  5 12 11  8  9 10 13
1  2  3  4  7  6 13 10  9  8 11 12  5 14
1  2  3  4  7  6 13 10  9  8 11 12  5 14 15
1  2  3  4  7  6  5 12 11  8 15 14  9 10 13 16
1  2  3  4  7  6  5 12 11  8  9 10 13 16 15 14 17
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18 19
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 19 18 11 20

1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 480728 1588162

Elapsed time: 0.572986 seconds
```

### Use bit patterns

Number combinations are all stored in bit positions here. The `bpos()` functions returns the position index of the least significant bit in an integer. This code gains some speed, at the cost of total loss of readability. On the plus side, it has some bit manipulation tricks that may be interesting to some.

`#include <stdio.h>#include <stdint.h> #define GCC_ASM // use GCC's asm for i386. If it does not work, #undef it to use alternative functypedef uint32_t uint;typedef uint64_t ulong; #define MASK 0xa08228828228a2bULL #ifdef GCC_ASM static inline uintbpos(uint x){	uint b;	asm("bsf %0, %0" : "=r" (b): "0" (x));	return b;} #else static inline uintbpos(uint x){	static const uint bruijin[32] = {		 0,  1, 28,  2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17,  4, 8, 		31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18,  6, 11,  5, 10, 9	};	return bruijin[((uint)((x & -x) * 0x077CB531U)) >> 27];} #endif // GCC_ASM int count(uint n, const uint s, uint avail){	int cnt = 0; 	avail ^= s;	if (--n)		for (uint b = (uint)(MASK>>bpos(s)) & avail; b; b &= b-1)			cnt += count(n, b&-b, avail);	else		return (MASK & s) != 0; 	return cnt;} int disp(uint n, const uint s, uint avail, int maxn, uint *seq){	seq[n--] = s;	if (!n) {		if ((MASK & s)) {			for (int i = 0; i < maxn; i++)				printf(" %d", bpos(seq[i]) + 1);			putchar('\n');			return 1;		}	} else {		for (uint b = (uint)(MASK>>bpos(s)) & (avail ^= s); b; b &= b-1)			if (disp(n, b&-b, avail, maxn, seq))				return 1;	}	return 0;} int chain(uint n, int count_only){	const uint top = 1U<<(n - 1);	const uint avail = 2*top - 2; 	if (count_only)		return count(n - 1, top, avail); 	uint seq[32];	seq[0] = 1;	disp(n - 1, top, avail, n, seq); 	return 0;} int main(void){	for (int n = 2; n < 21; n++)		chain(n, 0);	putchar('\n'); 	for (int n = 2; n < 21; n++)		printf("%d ", chain(n, 1));	putchar('\n'); 	return 0;}`
Output:
``` 1 2
1 2 3
1 2 3 4
1 4 3 2 5
1 4 3 2 5 6
1 6 5 2 3 4 7
1 4 7 6 5 2 3 8
1 4 7 6 5 8 3 2 9
1 6 7 4 9 8 5 2 3 10
1 10 9 8 5 6 7 4 3 2 11
1 10 9 8 11 6 7 4 3 2 5 12
1 12 11 8 9 10 7 6 5 2 3 4 13
1 12 11 8 9 10 13 4 7 6 5 2 3 14
1 12 11 8 5 14 9 10 13 6 7 4 3 2 15
1 12 11 8 15 14 9 10 13 4 7 6 5 2 3 16
1 10 13 16 15 14 9 8 11 12 5 6 7 4 3 2 17
1 12 17 14 15 16 13 10 9 8 11 6 7 4 3 2 5 18
1 18 13 16 15 14 17 12 11 8 9 10 7 6 5 2 3 4 19
1 18 19 10 13 16 15 14 17 12 11 8 9 4 7 6 5 2 3 20

1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 480728 1588162```

## C++

`#include <cassert>#include <chrono>#include <iomanip>#include <iostream>#include <numeric>#include <vector> bool is_prime(unsigned int n) {    assert(n > 0 && n < 64);    return (1ULL << n) & 0x28208a20a08a28ac;} template <typename Iterator>bool prime_triangle_row(Iterator begin, Iterator end) {    if (std::distance(begin, end) == 2)        return is_prime(*begin + *(begin + 1));    for (auto i = begin + 1; i + 1 != end; ++i) {        if (is_prime(*begin + *i)) {            std::iter_swap(i, begin + 1);            if (prime_triangle_row(begin + 1, end))                return true;            std::iter_swap(i, begin + 1);        }    }    return false;} template <typename Iterator>void prime_triangle_count(Iterator begin, Iterator end, int& count) {    if (std::distance(begin, end) == 2) {        if (is_prime(*begin + *(begin + 1)))            ++count;        return;    }    for (auto i = begin + 1; i + 1 != end; ++i) {        if (is_prime(*begin + *i)) {            std::iter_swap(i, begin + 1);            prime_triangle_count(begin + 1, end, count);            std::iter_swap(i, begin + 1);        }    }} template <typename Iterator>void print(Iterator begin, Iterator end) {    if (begin == end)        return;    auto i = begin;    std::cout << std::setw(2) << *i++;    for (; i != end; ++i)        std::cout << ' ' << std::setw(2) << *i;    std::cout << '\n';} int main() {    auto start = std::chrono::high_resolution_clock::now();    for (unsigned int n = 2; n < 21; ++n) {        std::vector<unsigned int> v(n);        std::iota(v.begin(), v.end(), 1);        if (prime_triangle_row(v.begin(), v.end()))            print(v.begin(), v.end());    }    std::cout << '\n';    for (unsigned int n = 2; n < 21; ++n) {        std::vector<unsigned int> v(n);        std::iota(v.begin(), v.end(), 1);        int count = 0;        prime_triangle_count(v.begin(), v.end(), count);        if (n > 2)            std::cout << ' ';        std::cout << count;    }    std::cout << '\n';    auto end = std::chrono::high_resolution_clock::now();    std::chrono::duration<double> duration(end - start);    std::cout << "\nElapsed time: " << duration.count() << " seconds\n";}`
Output:
``` 1  2
1  2  3
1  2  3  4
1  4  3  2  5
1  4  3  2  5  6
1  4  3  2  5  6  7
1  2  3  4  7  6  5  8
1  2  3  4  7  6  5  8  9
1  2  3  4  7  6  5  8  9 10
1  2  3  4  7 10  9  8  5  6 11
1  2  3  4  7 10  9  8  5  6 11 12
1  2  3  4  7  6  5 12 11  8  9 10 13
1  2  3  4  7  6 13 10  9  8 11 12  5 14
1  2  3  4  7  6 13 10  9  8 11 12  5 14 15
1  2  3  4  7  6  5 12 11  8 15 14  9 10 13 16
1  2  3  4  7  6  5 12 11  8  9 10 13 16 15 14 17
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18 19
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 19 18 11 20

1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 480728 1588162

Elapsed time: 0.636331 seconds
```

## F#

This task uses Extensible Prime Generator (F#)

` // Prime triangle. Nigel Galloway: April 12th., 2022let     fN i (g,(e,l))=e|>Seq.map(fun n->let n=i n in (n::g,List.partition(i>>(=)n) l))let rec fG n g=function 0->n|>Seq.map fst |x->fG(n|>Seq.collect(fN(if g then fst else snd)))(not g)(x-1)let primeT row=fG [([1],([for g in {2..2..row-1} do if isPrime(g+1) then yield (1,g)],[for n in {3..2..row-1} do for g in {2..2..row-1} do if isPrime(n+g) then yield (n,g)]))] false (row-2)                 |>Seq.filter(List.head>>(+)row>>isPrime)|>Seq.map(fun n->row::n|>List.rev) {2..20}|>Seq.iter(fun n->(primeT>>Seq.head>>List.iter(printf "%3d"))n;printfn "");;{2..20}|>Seq.iter(primeT>>Seq.length>>printf "%d "); printfn "" `
Output:
```  1  2
1  2  3
1  2  3  4
1  4  3  2  5
1  4  3  2  5  6
1  4  3  2  5  6  7
1  2  3  4  7  6  5  8
1  2  3  4  7  6  5  8  9
1  2  3  4  7  6  5  8  9 10
1  2  3  4  7 10  9  8  5  6 11
1  2  3  4  7 10  9  8  5  6 11 12
1  2  3  4  7  6  5 12 11  8  9 10 13
1  2  3  4  7  6 13 10  9  8 11 12  5 14
1  2  3  4  7  6 13 10  9  8 11 12  5 14 15
1  2  3  4  7  6  5 12 11  8 15 14  9 10 13 16
1  2  3  4  7  6  5 12 11  8  9 10 13 16 15 14 17
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18 19
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 19 18 11 20

1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 480728 1588162
```

## Go

Translation of: Phix
`package main import "fmt" var canFollow [][]boolvar arrang []intvar bFirst = true var pmap = make(map[int]bool) func init() {    for _, i := range []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} {        pmap[i] = true    }} func ptrs(res, n, done int) int {    ad := arrang[done-1]    if n-done <= 1 {        if canFollow[ad-1][n-1] {            if bFirst {                for _, e := range arrang {                    fmt.Printf("%2d ", e)                }                fmt.Println()                bFirst = false            }            res++        }    } else {        done++        for i := done - 1; i <= n-2; i += 2 {            ai := arrang[i]            if canFollow[ad-1][ai-1] {                arrang[i], arrang[done-1] = arrang[done-1], arrang[i]                res = ptrs(res, n, done)                arrang[i], arrang[done-1] = arrang[done-1], arrang[i]            }        }    }    return res} func primeTriangle(n int) int {    canFollow = make([][]bool, n)    for i := 0; i < n; i++ {        canFollow[i] = make([]bool, n)        for j := 0; j < n; j++ {            _, ok := pmap[i+j+2]            canFollow[i][j] = ok        }    }    bFirst = true    arrang = make([]int, n)    for i := 0; i < n; i++ {        arrang[i] = i + 1    }    return ptrs(0, n, 1)} func main() {    counts := make([]int, 19)    for i := 2; i <= 20; i++ {        counts[i-2] = primeTriangle(i)    }    fmt.Println()    for i := 0; i < 19; i++ {        fmt.Printf("%d ", counts[i])    }    fmt.Println()}`
Output:
``` 1  2
1  2  3
1  2  3  4
1  4  3  2  5
1  4  3  2  5  6
1  4  3  2  5  6  7
1  2  3  4  7  6  5  8
1  2  3  4  7  6  5  8  9
1  2  3  4  7  6  5  8  9 10
1  2  3  4  7 10  9  8  5  6 11
1  2  3  4  7 10  9  8  5  6 11 12
1  2  3  4  7  6  5 12 11  8  9 10 13
1  2  3  4  7  6 13 10  9  8 11 12  5 14
1  2  3  4  7  6 13 10  9  8 11 12  5 14 15
1  2  3  4  7  6  5 12 11  8 15 14  9 10 13 16
1  2  3  4  7  6  5 12 11  8  9 10 13 16 15 14 17
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18 19
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 19 18 11 20

1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 480728 1588162
```

## J

`is_prime=: 1&p:@(+/) is_prime_triangle=: {{  NB. y is index into L and thus analogous to *a  p=. is_prime L{~y+0 1  if. N=y do. p return.end.  i=. Y=. y+1  if. p do. if. is_prime_triangle Y do. 1 return.end.end.  while. M>i=.i+2 do.    if. is_prime L{~y,i do.      L=: (L{~Y,i) (i,Y)} L      if. is_prime_triangle Y do. 1 return.end.      L=: (L{~Y,i) (i,Y)} L    end.  end.  0}} prime_triangle_counter=: {{  NB. y is index into L and thus analogous to *a  p=. is_prime L{~y+0 1  if. N=y do.    count=: count+p return.  end.  i=. Y=. y+1  if. p do. prime_triangle_counter Y end.  while. M>i=. i+2 do.    if. is_prime L{~y,i do.      L=: (L{~Y,i) (i,Y)} L      prime_triangle_counter Y      L=: (L{~Y,i) (i,Y)} L    end.  end.  count}} prime_triangles=: {{  for_k. i.y-1 do.    L=: l=. 1+i.1+M=: 1+N=: k    count=: 0    prime_triangle_counter 0    L=: l    assert is_prime_triangle 0    echo (8":count),' | ',3":L  end.}}`

`    prime_triangles 20       1 |   1  2       1 |   1  2  3       1 |   1  2  3  4       1 |   1  4  3  2  5       1 |   1  4  3  2  5  6       2 |   1  4  3  2  5  6  7       4 |   1  2  3  4  7  6  5  8       7 |   1  2  3  4  7  6  5  8  9      24 |   1  2  3  4  7  6  5  8  9 10      80 |   1  2  3  4  7 10  9  8  5  6 11     216 |   1  2  3  4  7 10  9  8  5  6 11 12     648 |   1  2  3  4  7  6  5 12 11  8  9 10 13    1304 |   1  2  3  4  7  6 13 10  9  8 11 12  5 14    3392 |   1  2  3  4  7  6 13 10  9  8 11 12  5 14 15   13808 |   1  2  3  4  7  6  5 12 11  8 15 14  9 10 13 16   59448 |   1  2  3  4  7  6  5 12 11  8  9 10 13 16 15 14 17  155464 |   1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18  480728 |   1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18 19 1588162 |   1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 19 18 11 20`

## Java

`public class PrimeTriangle {    public static void main(String[] args) {        long start = System.currentTimeMillis();        for (int i = 2; i <= 20; ++i) {            int[] a = new int[i];            for (int j = 0; j < i; ++j)                a[j] = j + 1;            if (findRow(a, 0, i))                printRow(a);                        }        System.out.println();        StringBuilder s = new StringBuilder();        for (int i = 2; i <= 20; ++i) {            int[] a = new int[i];            for (int j = 0; j < i; ++j)                a[j] = j + 1;            if (i > 2)                s.append(" ");            s.append(countRows(a, 0, i));        }        System.out.println(s);        long finish = System.currentTimeMillis();        System.out.printf("\nElapsed time: %d milliseconds\n", finish - start);    }     private static void printRow(int[] a) {        for (int i = 0; i < a.length; ++i) {            if (i != 0)                System.out.print(" ");            System.out.printf("%2d", a[i]);        }        System.out.println();    }     private static boolean findRow(int[] a, int start, int length) {        if (length == 2)            return isPrime(a[start] + a[start + 1]);        for (int i = 1; i + 1 < length; i += 2) {            if (isPrime(a[start] + a[start + i])) {                swap(a, start + i, start + 1);                if (findRow(a, start + 1, length - 1))                    return true;                swap(a, start + i, start + 1);            }        }        return false;    }     private static int countRows(int[] a, int start, int length) {        int count = 0;        if (length == 2) {            if (isPrime(a[start] + a[start + 1]))                ++count;        } else {            for (int i = 1; i + 1 < length; i += 2) {                if (isPrime(a[start] + a[start + i])) {                    swap(a, start + i, start + 1);                    count += countRows(a, start + 1, length - 1);                    swap(a, start + i, start + 1);                }            }        }        return count;    }     private static void swap(int[] a, int i, int j) {        int tmp = a[i];        a[i] = a[j];        a[j] = tmp;    }     private static boolean isPrime(int n) {        return ((1L << n) & 0x28208a20a08a28acL) != 0;    }}`
Output:
``` 1  2
1  2  3
1  2  3  4
1  4  3  2  5
1  4  3  2  5  6
1  4  3  2  5  6  7
1  2  3  4  7  6  5  8
1  2  3  4  7  6  5  8  9
1  2  3  4  7  6  5  8  9 10
1  2  3  4  7 10  9  8  5  6 11
1  2  3  4  7 10  9  8  5  6 11 12
1  2  3  4  7  6  5 12 11  8  9 10 13
1  2  3  4  7  6 13 10  9  8 11 12  5 14
1  2  3  4  7  6 13 10  9  8 11 12  5 14 15
1  2  3  4  7  6  5 12 11  8 15 14  9 10 13 16
1  2  3  4  7  6  5 12 11  8  9 10 13 16 15 14 17
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18 19
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 19 18 11 20

1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 480728 1588162

Elapsed time: 833 milliseconds
```

## Julia

### Filter method

`using Combinatorics, Primes function primetriangle(nrows::Integer)    nrows < 2 && error("number of rows requested must be > 1")    pmask, spinlock = primesmask(2 * (nrows + 1)), Threads.SpinLock()    counts, rowstrings = [1; zeros(Int, nrows - 1)], ["" for _ in 1:nrows]    for r in 2:nrows        @Threads.threads for e in collect(permutations(2:2:r))            p = zeros(Int, r - 1)            for o in permutations(3:2:r)                i = 0                for (x, y) in zip(e, o)                    p[i += 1] = x                    p[i += 1] = y                end                length(e) > length(o) && (p[i += 1] = e[end])                if pmask[p[i] + r + 1] && pmask[p[begin] + 1] && all(j -> pmask[p[j] + p[j + 1]], 1:r-2)                    lock(spinlock)                    if counts[r] == 0                        rowstrings[r] = "  1" * prod([lpad(n, 3) for n in p]) * lpad(r + 1, 3) * "\n"                    end                    counts[r] += 1                    unlock(spinlock)                end            end        end    end    println("  1  2\n" * prod(rowstrings), "\n", counts)end @time primetriangle(16) `
Output:
```  1  2
1  2  3
1  2  3  4
1  4  3  2  5
1  4  3  2  5  6
1  4  3  2  5  6  7
1  2  3  4  7  6  5  8
1  2  3  4  7  6  5  8  9
1  2  3  4  7  6  5  8  9 10
1  2  3  4  9 10  7  6  5  8 11
1  2  3  4  9 10  7  6  5  8 11 12
1  2  3  4  7  6  5 12 11  8  9 10 13
1  2  3  4 13  6 11  8  9 10  7 12  5 14
1  2  3  4 13  6 11  8  9 10  7 12  5 14 15
1  2  3  4 13  6 11  8  9 10  7 12  5 14 15 16
1  2 15  4 13  6 11  8  9 10  3 16  7 12  5 14 17

[1, 1, 1, 1, 1, 2, 4, 7, 24, 80, 216, 648, 1304, 3392, 13808, 59448]
36.933227 seconds (699.10 M allocations: 55.557 GiB, 46.71% gc time, 0.37% compilation time)
```

### Generator method

Similar to the Phix entry.

`using Primes function solverow(row, pos, avail)    results, nresults = Int[], 0    for (i, tf) in enumerate(avail)        if tf && isprime(row[pos - 1] + i + 1)            if pos >= length(row) - 1 && isprime(row[end] + i + 1)                row[pos] = i + 1                return (copy(row), 1)            else                row[pos] = i + 1                newav = copy(avail)                newav[i] = false                newresults, n = solverow(copy(row), pos + 1, newav)                nresults += n                results = isempty(results) && !isempty(newresults) ? newresults : results            end        end    end    return results, nresultsend function primetriangle(nrows::Integer)    nrows < 2 && error("number of rows requested must be > 1")    counts, rowstrings = [1; zeros(Int, nrows - 1)], ["" for _ in 1:nrows]    for r in 2:nrows        p, n = solverow(collect(1:r+1), 2, trues(r - 1))        rowstrings[r] = prod([lpad(n, 3) for n in p]) * "\n"        counts[r] = n    end    println("  1  2\n" * prod(rowstrings), "\n", counts)end `
Output:
```  1  2
1  2  3
1  2  3  4
1  4  3  2  5
1  4  3  2  5  6
1  4  3  2  5  6  7
1  2  3  4  7  6  5  8
1  2  3  4  7  6  5  8  9
1  2  3  4  7  6  5  8  9 10
1  2  3  4  7 10  9  8  5  6 11
1  2  3  4  7 10  9  8  5  6 11 12
1  2  3  4  7  6  5 12 11  8  9 10 13
1  2  3  4  7  6 13 10  9  8 11 12  5 14
1  2  3  4  7  6 13 10  9  8 11 12  5 14 15
1  2  3  4  7  6  5 12 11  8 15 14  9 10 13 16
1  2  3  4  7  6  5 12 11  8  9 10 13 16 15 14 17
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18 19
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 19 18 11 20

[1, 1, 1, 1, 1, 2, 4, 7, 24, 80, 216, 648, 1304, 3392, 13808, 59448, 155464, 480728, 1588162]
25.818809 seconds (249.58 M allocations: 22.295 GiB, 15.56% gc time)
```

## Perl

Translation of: Raku
Library: ntheory
`use strict;use warnings;use feature 'say';use ntheory 'is_prime';use List::MoreUtils qw(zip slideatatime);use Algorithm::Combinatorics qw(permutations); say '1 2'; my @count = (0, 0, 1); for my \$n (3..17) {    my @even_nums = grep { 0 == \$_ % 2 } 2..\$n-1;    my @odd_nums  = grep { 1 == \$_ % 2 } 3..\$n-1;    for my \$e (permutations [@even_nums]) {        next if \$\$e[0] == 8 or \$\$e[0] == 14;        my \$nope = 0;        for my \$o (permutations [@odd_nums]) {            my @list = (zip(@\$e, @\$o), \$n);                 # 'zip' makes a list with a gap if more evens than odds            splice @list, -2, -1 if not defined \$list[-2];  # in which case splice out 'undef' in next-to-last position            my \$it = slideatatime(1, 2, @list);            while ( my @rr = \$it->() ) {                last unless defined \$rr[1];                \$nope++ and last unless is_prime \$rr[0]+\$rr[1];            }            unless (\$nope) {                say '1 ' . join ' ', @list unless \$count[\$n];                \$count[\$n]++;            }            \$nope = 0;        }    }} say "\n" . join ' ', @count[2..\$#count];`
Output:
```1 2
1 2 3
1 2 3 4
1 4 3 2 5
1 4 3 2 5 6
1 4 3 2 5 6 7
1 2 3 4 7 6 5 8
1 2 3 4 7 6 5 8 9
1 2 3 4 7 6 5 8 9 10
1 2 3 4 9 10 7 6 5 8 11
1 2 3 4 9 10 7 6 5 8 11 12
1 2 3 4 7 6 5 12 11 8 9 10 13
1 2 3 4 13 6 11 8 9 10 7 12 5 14
1 2 3 4 13 6 11 8 9 10 7 12 5 14 15
1 2 3 4 13 6 11 8 9 10 7 12 5 14 15 16
1 2 15 4 13 6 11 8 9 10 3 16 7 12 5 14 17

1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448```

## Phix

Library: Phix/online

Not sure this counts as particularly clever but by the sound of things it's quite a bit faster than the other entries so far. 😎
You can run this online here (expect a blank screen for about 24s).

```with javascript_semantics
atom t0 = time()
sequence can_follow, arrang
bool bFirst = true

function ptrs(integer res, n, done)
-- prime triangle recursive sub-procedure
-- on entry, arrang[done] is set and arrang[\$]==n.
-- find something/everything that fits between them.
if n-done<=1 then
if bFirst then
printf(1,"%s\n",join(arrang,fmt:="%d"))
bFirst = false
end if
res += 1
end if
else
done += 1
-- as per talk page, we only need to examine odd
-- numbers following an even number & vice versa
for i=done to n-1 by 2 do
integer ai = arrang[i]
integer aid = arrang[done]
arrang[i] = aid
arrang[done] = ai
res = ptrs(res,n,done)
arrang[i] = ai
arrang[done] = aid
end if
end for
end if
return res
end function

function prime_triangle(integer n)
for i=1 to n do
for j=1 to n do
can_follow[i][j] = is_prime(i+j)
end for
end for
arrang = tagset(n)
bFirst = true
return ptrs(0,n,1)
end function

sequence res = apply(tagset(20,2),prime_triangle)
printf(1,"%s\n",join(res,fmt:="%d"))
?elapsed(time()-t0)
```
Output:
```1 2
1 2 3
1 2 3 4
1 4 3 2 5
1 4 3 2 5 6
1 4 3 2 5 6 7
1 2 3 4 7 6 5 8
1 2 3 4 7 6 5 8 9
1 2 3 4 7 6 5 8 9 10
1 2 3 4 7 10 9 8 5 6 11
1 2 3 4 7 10 9 8 5 6 11 12
1 2 3 4 7 6 5 12 11 8 9 10 13
1 2 3 4 7 6 13 10 9 8 11 12 5 14
1 2 3 4 7 6 13 10 9 8 11 12 5 14 15
1 2 3 4 7 6 5 12 11 8 15 14 9 10 13 16
1 2 3 4 7 6 5 12 11 8 9 10 13 16 15 14 17
1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11 18
1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 11 18 19
1 2 3 4 7 6 5 8 9 10 13 16 15 14 17 12 19 18 11 20
1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 480728 1588162
"9.7s"
```

## Raku

Limit the upper threshold a bit to avoid multiple hours of pointless calculations. Even just up to 17 takes over 20 minutes.

`my @count = 0, 0, 1;my \$lock = Lock.new;put (1,2); for 3..17 -> \$n {    my @even = (2..^\$n).grep: * %% 2;    my @odd  = (3..^\$n).grep: so * % 2;    @even.permutations.race.map: -> @e {        quietly next if @e[0] == 8|14;        my \$nope = 0;        for @odd.permutations -> @o {            quietly next unless (@e[0] + @o[0]).is-prime;            my @list;            for (@list = (flat (roundrobin(@e, @o)), \$n)).rotor(2 => -1) {                \$nope++ and last unless .sum.is-prime;            }            unless \$nope {                put '1 ', @list unless @count[\$n];                \$lock.protect({ @count[\$n]++ });            }            \$nope = 0;        }    }}put "\n", @count[2..*];`
Output:
```1 2
1 2 3
1 2 3 4
1 4 3 2 5
1 4 3 2 5 6
1 4 3 2 5 6 7
1 2 3 4 7 6 5 8
1 2 3 4 7 6 5 8 9
1 2 3 4 7 6 5 8 9 10
1 6 5 8 3 10 7 4 9 2 11
1 6 5 8 3 10 7 4 9 2 11 12
1 4 3 2 5 8 9 10 7 12 11 6 13
1 4 3 2 11 8 9 10 13 6 7 12 5 14
1 2 3 8 5 12 11 6 7 10 13 4 9 14 15
1 2 3 8 5 12 11 6 7 10 13 4 9 14 15 16
1 2 9 4 7 10 13 6 5 14 3 16 15 8 11 12 17

1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448
```

## Rust

`fn is_prime(n: u32) -> bool {    assert!(n < 64);    ((1u64 << n) & 0x28208a20a08a28ac) != 0} fn prime_triangle_row(a: &mut [u32]) -> bool {    if a.len() == 2 {        return is_prime(a[0] + a[1]);    }    for i in (1..a.len() - 1).step_by(2) {        if is_prime(a[0] + a[i]) {            a.swap(i, 1);            if prime_triangle_row(&mut a[1..]) {                return true;            }            a.swap(i, 1);        }    }    false} fn prime_triangle_count(a: &mut [u32]) -> u32 {    let mut count = 0;    if a.len() == 2 {        if is_prime(a[0] + a[1]) {            count += 1;        }    } else {        for i in (1..a.len() - 1).step_by(2) {            if is_prime(a[0] + a[i]) {                a.swap(i, 1);                count += prime_triangle_count(&mut a[1..]);                a.swap(i, 1);            }        }    }    count} fn print(a: &[u32]) {    if a.is_empty() {        return;    }    print!("{:2}", a[0]);    for x in &a[1..] {        print!(" {:2}", x);    }    println!();} fn main() {    use std::time::Instant;    let start = Instant::now();    for n in 2..21 {        let mut a: Vec<u32> = (1..=n).collect();        if prime_triangle_row(&mut a) {            print(&a);        }    }    println!();    for n in 2..21 {        let mut a: Vec<u32> = (1..=n).collect();        if n > 2 {            print!(" ");        }        print!("{}", prime_triangle_count(&mut a));    }    println!();    let time = start.elapsed();    println!("\nElapsed time: {} milliseconds", time.as_millis());}`
Output:
``` 1  2
1  2  3
1  2  3  4
1  4  3  2  5
1  4  3  2  5  6
1  4  3  2  5  6  7
1  2  3  4  7  6  5  8
1  2  3  4  7  6  5  8  9
1  2  3  4  7  6  5  8  9 10
1  2  3  4  7 10  9  8  5  6 11
1  2  3  4  7 10  9  8  5  6 11 12
1  2  3  4  7  6  5 12 11  8  9 10 13
1  2  3  4  7  6 13 10  9  8 11 12  5 14
1  2  3  4  7  6 13 10  9  8 11 12  5 14 15
1  2  3  4  7  6  5 12 11  8 15 14  9 10 13 16
1  2  3  4  7  6  5 12 11  8  9 10 13 16 15 14 17
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18 19
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 19 18 11 20

1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 480728 1588162

Elapsed time: 674 milliseconds
```

## Swift

`import Foundation func isPrime(_ n: Int) -> Bool {    guard n > 0 && n < 64 else {        return false    }    return ((UInt64(1) << n) & 0x28208a20a08a28ac) != 0} func primeTriangleRow(_ a: inout [Int], start: Int, length: Int) -> Bool {    if length == 2 {        return isPrime(a[start] + a[start + 1])    }    for i in stride(from: 1, to: length - 1, by: 2) {        let index = start + i        if isPrime(a[start] + a[index]) {            a.swapAt(index, start + 1)            if primeTriangleRow(&a, start: start + 1, length: length - 1) {                return true            }            a.swapAt(index, start + 1)        }    }    return false} func primeTriangleCount(_ a: inout [Int], start: Int, length: Int) -> Int {    var count = 0    if length == 2 {        if isPrime(a[start] + a[start + 1]) {            count += 1        }    } else {        for i in stride(from: 1, to: length - 1, by: 2) {            let index = start + i            if isPrime(a[start] + a[index]) {                a.swapAt(index, start + 1)                count += primeTriangleCount(&a, start: start + 1, length: length - 1)                a.swapAt(index, start + 1)            }        }    }    return count} func printRow(_ a: [Int]) {    if a.count == 0 {        return    }    print(String(format: "%2d", a[0]), terminator: "")    for x in a[1...] {        print(String(format: " %2d", x), terminator: "")    }    print()} let startTime = CFAbsoluteTimeGetCurrent() for n in 2...20 {    var a = Array(1...n)    if primeTriangleRow(&a, start: 0, length: n) {        printRow(a)    }}print() for n in 2...20 {    var a = Array(1...n)    if n > 2 {        print(" ", terminator: "")    }    print("\(primeTriangleCount(&a, start: 0, length: n))", terminator: "")}print() let endTime = CFAbsoluteTimeGetCurrent()print("\nElapsed time: \(endTime - startTime) seconds")`
Output:
``` 1  2
1  2  3
1  2  3  4
1  4  3  2  5
1  4  3  2  5  6
1  4  3  2  5  6  7
1  2  3  4  7  6  5  8
1  2  3  4  7  6  5  8  9
1  2  3  4  7  6  5  8  9 10
1  2  3  4  7 10  9  8  5  6 11
1  2  3  4  7 10  9  8  5  6 11 12
1  2  3  4  7  6  5 12 11  8  9 10 13
1  2  3  4  7  6 13 10  9  8 11 12  5 14
1  2  3  4  7  6 13 10  9  8 11 12  5 14 15
1  2  3  4  7  6  5 12 11  8 15 14  9 10 13 16
1  2  3  4  7  6  5 12 11  8  9 10 13 16 15 14 17
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18 19
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 19 18 11 20

1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 480728 1588162

Elapsed time: 1.0268970727920532 seconds
```

## Visual Basic .NET

Translation of: ALGOL 68
`Option Strict OnOption Explicit On Imports System.IO ''' <summary>Find solutions to the "Prime Triangle" - a triangle of numbers that sum to primes.</summary>Module vMain     Public Const maxNumber As Integer = 20 ' Largest number we will consider.    Dim prime(2 * maxNumber) As Boolean    ' prime sieve.     ''' <returns>The number of possible arrangements of the integers for a row in the prime triangle.</returns>    Public Function countArrangements(ByVal n As Integer) As Integer        If n < 2 Then ' No solutions for n < 2.            Return 0        ElseIf n < 4 Then             ' For 2 and 3. there is only 1 solution: 1, 2 and 1, 2, 3.            For i As Integer = 1 To n                Console.Out.Write(i.ToString.PadLeft(3))            Next i            Console.Out.WriteLine()            Return 1        Else            ' 4 or more - must find the solutions.            Dim printSolution As Boolean = true            Dim used(n) As Boolean            Dim number(n) As Integer            ' The triangle row must have 1 in the leftmost and n in the rightmost elements.            ' The numbers must alternate between even and odd in order for the sums to be prime.            For i As Integer = 0 To n - 1                number(i) = i Mod 2            Next i            used(1) = True            number(n) = n            used(n) = True            ' Find the intervening numbers and count the solutions.            Dim count As Integer = 0            Dim p As Integer = 2            Do While p > 0                Dim p1 As Integer = number(p - 1)                Dim current As Integer = number(p)                Dim [next] As Integer = current + 2                Do While [next] < n AndAlso (Not prime(p1 + [next]) Or used([next]))                    [next] += 2                Loop                If [next] >= n Then                    [next] = 0                End If                If p = n - 1 Then                    ' We are at the final number before n.                    ' It must be the final even/odd number preceded by the final odd/even number.                    If [next] <> 0 Then                        ' Possible solution.                        If prime([next] + n) Then                            ' Found a solution.                            count += 1                            If printSolution Then                                For i As Integer = 1 To n - 2                                     Console.Out.Write(number(i).ToString.PadLeft(3))                                Next i                                Console.Out.WriteLine([next].ToString.PadLeft(3) & n.ToString.PadLeft(3))                                printSolution = False                            End If                        End If                        [next] = 0                    End If                    ' Backtrack for more solutions.                    p -= 1                    ' There will be a further backtrack as next is 0 ( there could only be one possible number at p - 1 ).                End If                If [next] <> 0 Then                    ' have a/another number that can appear at p.                    used(current) = False                    used([next]) = True                    number(p) = [next]                    ' Haven't found all the intervening digits yet.                    p += 1                ElseIf p <= 2 Then                    ' No more solutions.                    p = 0                Else                    ' Can't find a number for this position, backtrack.                    used(number(p)) = False                    number(p) = p Mod 2                    p -= 1                End If            Loop            Return count        End If    End Function     Public Sub Main        prime(2) = True        For i As Integer = 3 To UBound(prime) Step  2            prime(i) = True        Next i        For i As Integer = 3 To Convert.ToInt32(Math.Floor(Math.Sqrt(Ubound(prime)))) Step 2            If prime(i) Then                For s As Integer = i * i To Ubound(prime) Step i + i                    prime(s) = False                Next s            End If        Next i         Dim  arrangements(maxNumber) As Integer        For n As Integer = 2 To UBound(arrangements)            arrangements(n) = countArrangements(n)        Next n        For n As Integer = 2 To UBound(arrangements)            Console.Out.Write(" " & arrangements(n))        Next n        Console.Out.WriteLine()     End Sub End Module`
Output:
```  1  2
1  2  3
1  2  3  4
1  4  3  2  5
1  4  3  2  5  6
1  4  3  2  5  6  7
1  2  3  4  7  6  5  8
1  2  3  4  7  6  5  8  9
1  2  3  4  7  6  5  8  9 10
1  2  3  4  7 10  9  8  5  6 11
1  2  3  4  7 10  9  8  5  6 11 12
1  2  3  4  7  6  5 12 11  8  9 10 13
1  2  3  4  7  6 13 10  9  8 11 12  5 14
1  2  3  4  7  6 13 10  9  8 11 12  5 14 15
1  2  3  4  7  6  5 12 11  8 15 14  9 10 13 16
1  2  3  4  7  6  5 12 11  8  9 10 13 16 15 14 17
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18 19
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 19 18 11 20
1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 480728 1588162
```

## Wren

Translation of: Phix
Library: Wren-fmt

Takes around 18.7 seconds which is fine for Wren.

`import "./fmt" for Fmt var canFollow = []var arrang = []var bFirst = true var pmap = {}for (i in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]) {    pmap[i] = true} var ptrsptrs = Fn.new { |res, n, done|    var ad = arrang[done-1]    if (n - done <= 1) {        if (canFollow[ad-1][n-1]) {            if (bFirst) {                Fmt.print("\$2d", arrang)                bFirst = false            }            res = res + 1        }    } else {        done = done + 1        var i = done - 1        while (i <= n-2) {            var ai = arrang[i]            if (canFollow[ad-1][ai-1]) {                arrang.swap(i, done-1)                res = ptrs.call(res, n, done)                arrang.swap(i, done-1)            }            i = i + 2        }    }    return res} var primeTriangle = Fn.new { |n|    canFollow = List.filled(n, null)    for (i in 0...n) {        canFollow[i] = List.filled(n, false)        for (j in 0...n) canFollow[i][j] = pmap.containsKey(i+j+2)    }    bFirst = true    arrang = (1..n).toList    return ptrs.call(0, n, 1)} var counts = []for (i in 2..20) {    counts.add(primeTriangle.call(i))}System.print()System.print(counts.join(" "))`
Output:
``` 1  2
1  2  3
1  2  3  4
1  4  3  2  5
1  4  3  2  5  6
1  4  3  2  5  6  7
1  2  3  4  7  6  5  8
1  2  3  4  7  6  5  8  9
1  2  3  4  7  6  5  8  9 10
1  2  3  4  7 10  9  8  5  6 11
1  2  3  4  7 10  9  8  5  6 11 12
1  2  3  4  7  6  5 12 11  8  9 10 13
1  2  3  4  7  6 13 10  9  8 11 12  5 14
1  2  3  4  7  6 13 10  9  8 11 12  5 14 15
1  2  3  4  7  6  5 12 11  8 15 14  9 10 13 16
1  2  3  4  7  6  5 12 11  8  9 10 13 16 15 14 17
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18 19
1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 19 18 11 20

1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 480728 1588162
```