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
```

## 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);            splice @list, -2, -1 if not defined \$list[-2];            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
```