Prime triangle: Difference between revisions

Content added Content deleted

Inline

Latest revision as of 01:24, 3 March 2024

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 g₁=1 g_S=S and generally for n=1 to n=S-1 g_n+g_n+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.

See also

OEIS:A036440

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

BASIC

FreeBASIC

Translation of: Visual Basic .NET

Dim Shared As Uinteger maxNumber = 20 ' Largest number we will consider.
Dim Shared As Uinteger prime(2 * maxNumber) ' prime sieve.

Function countArrangements(Byval n As Uinteger) As Uinteger
    Dim As Uinteger i
    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 = 1 To n
            Print Using "###"; i;
        Next i
        Print
        Return 1
    Else
        ' 4 or more - must find the solutions.
        Dim As Boolean printSolution = True
        Dim As Boolean used(n)
        Dim As Uinteger number(n)
        ' 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 = 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 As Uinteger count = 0
        Dim As Uinteger p = 2
        Do While p > 0
            Dim As Uinteger p1 = number(p - 1)
            Dim As Uinteger current = number(p)
            Dim As Uinteger sgte = current + 2
            Do While sgte < n Andalso (Not prime(p1 + sgte) Or used(sgte))
                sgte += 2
            Loop
            If sgte >= n Then
                sgte = 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 sgte <> 0 Then
                    ' Possible solution.
                    If prime(sgte + n) Then
                        ' Found a solution.
                        count += 1
                        If printSolution Then
                            For i = 1 To n - 2
                                Print Using "###"; number(i);
                            Next i
                            Print Using "###"; sgte; n
                            printSolution = False
                        End If
                    End If
                    sgte = 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 sgte <> 0 Then
                ' have a/another number that can appear at p.
                used(current) = False
                used(sgte) = True
                number(p) = sgte
                ' 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

Dim As Integer i, s, n
prime(2) = True
For i = 3 To Ubound(prime) Step  2
    prime(i) = True
Next i
For i = 3 To Cint(Sqr(Ubound(prime))) Step 2
    If prime(i) Then
        For s = i * i To Ubound(prime) Step i + i
            prime(s) = False
        Next s
    End If
Next i

Dim As Integer arrangements(maxNumber)
For n = 2 To Ubound(arrangements)
    arrangements(n) = countArrangements(n)
Next n
For n = 2 To Ubound(arrangements)
    Print arrangements(n);
Next n
Print

Sleep

Output:

Same as Visual Basic .NET entry.

Visual Basic .NET

Translation of: ALGOL 68

Option Strict On
Option 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

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 func
typedef uint32_t uint;
typedef uint64_t ulong;

#define MASK 0xa08228828228a2bULL

#ifdef GCC_ASM

static inline uint
bpos(uint x)
{
	uint b;
	asm("bsf %0, %0" : "=r" (b): "0" (x));
	return b;
}

#else

static inline uint
bpos(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., 2022
let     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

Takes about 0.64 seconds.

Translation of: Phix

package main

import "fmt"

var canFollow [][]bool
var arrang []int
var 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

Essentially, we're traversing a directed graph starting at 1, ending at y, with edges such that adjacent pairs sum to a prime number and with distinct intermediate values between 1 and y.

Implementation:

add_plink=: [:;{{ <y,"1 0 x #~ 1 p:+/|:(x=. x-. y),"0/{: y }}"1
prime_pair_seqs=: {{ y add_plink (2}.i.y) add_plink^:(y-2) 1 }}

Task example (displaying counts of number of valid sequences to the left, because that looks nice):

task=: {{
  for_j.2}.i.1+y do.
    N=. #seqs=. prime_pair_seqs j
    echo (_8{.":N),' | ',3":{:seqs
  end.
}}

   task 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  6  5  2  3  4  7
       4 |   1  6  7  4  3  2  5  8
       7 |   1  6  7  4  3  8  5  2  9
      24 |   1  6  7  4  9  8  5  2  3 10
      80 |   1 10  9  8  5  6  7  4  3  2 11
     216 |   1 10  9  8 11  6  7  4  3  2  5 12
     648 |   1 12 11  8  9 10  7  6  5  2  3  4 13
    1304 |   1 12 11  8  9 10 13  6  7  4  3  2  5 14
    3392 |   1 12 11  8  9 14  5  6 13 10  7  4  3  2 15
   13808 |   1 12 11  8 15 14  9 10 13  6  5  2  3  4  7 16
   59448 |   1 16 15 14  9 10 13  6 11 12  7  4  3  8  5  2 17
  155464 |   1 16 15 14 17 12 11  8  9 10 13  6  7  4  3  2  5 18
  480728 |   1 18 13 16 15 14 17 12 11  8  9 10  7  6  5  2  3  4 19
 1588162 |   1 18 19 12 17 14 15 16 13 10  9  8 11  2  5  6  7  4  3 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

jq

Works with: jq

Adapted from Wren

(gojq requires too much memory to complete the task.)

# $i and $j should be relevant integers (possibly negataive)
# Usage with an array-valued key: .key |= array_swap($i; $j)
def array_swap($i; $j):
  if $i == $j then .
  else .[$i] as $t
  | .[$i] = .[$j]
  | .[$j] = $t
  end;

# For syntactic convenience
def swap($array; $i; $j):
  $array | array_swap($i; $j);

def pmap:
  reduce (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) as $i ([];
    .[$i] = true)  ;

# input: {bFirst, arrang, canFollow, emit}
# output: same + {res, emit, i, count}
def ptrs($res; $n; $done):
  . + {$res, count: $done}
  | .arrang[$done-1] as $ad
  | if ($n - $done <= 1)
    then if .canFollow[$ad-1][$n-1]
         then if .bFirst
              then .emit += [.arrang]
              | .bFirst = false
              else .
              end
         | .res += 1
         else .
         end
    else .count += 1
    | .count as $count
    | reduce range($count - 1; $n - 1; 2) as $i (.;
        .arrang[$i] as $ai
        | if .canFollow[$ad-1][$ai-1]
          then .arrang = swap(.arrang; $i; $count-1)
          | ptrs(.res; $n; $count)
          | .arrang = swap(.arrang; $i; $count-1)
          else .
          end )
     end;

# Emit {emit, res} from the call to ptrs
def primeTriangle($n):
  pmap as $pmap
  | {}
  | .canFollow = (reduce range(0;$n) as $i ([];
        .[$i] = [range(0;$n) | false]
        | reduce range(0;$n) as $j (.;
            .[$i][$j] = $pmap[$i+$j+2] )))
  | .bFirst = true
  | .arrang = [range(1; 1+$n)]
  | ptrs(0; $n; 1)
  | {emit, res} ;

def task($n):
  range(2;$n+1) as $i
  |  primeTriangle($i) ;

def task($n):
  foreach (range(2;$n+1), null) as $i ({counts: [], emit: null};
    if $i == null then .emit = "\n\(.counts)"
    else primeTriangle($i) as $pt
    | .counts += [$pt|.res]
    | .emit = $pt.emit
    end;
    .emit);

task(20)[]

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]

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, nresults
end

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)

Mathematica/Wolfram Language

ClearAll[FindPrimeTriangles, FindPrimeTrianglesHelper]
FindPrimeTriangles[max_] := 
 Module[{count = 0, firstsolution, primes, primeQ},
  primes = PrimeQ[Range[2 max]];
  primeQ[n_] := primes[[n]];
  ClearAll[FindPrimeTrianglesHelper];
  FindPrimeTrianglesHelper[start_, remainder_, mxx_] := 
   Module[{last, nexts, r, newstart, newremainder},
    If[Length[remainder] > 0,
     last = Last[start];
     Do[
      r = remainder[[ri]];
      If[primeQ[last + r],
       newstart = Append[start, r];
       newremainder = Delete[remainder, ri];
       FindPrimeTrianglesHelper[newstart, newremainder, mxx]
       ]
      ,
      {ri, Length[remainder]}
      ]
     ,
     If[primeQ[Last[start] + mxx],
      count++;
      If[count == 1,
       Print[Append[start, mxx]]
       ]
      ]
     ]
    ];
  FindPrimeTrianglesHelper[{1}, Range[2, max - 1], max];
  count
  ]
Table[FindPrimeTriangles[S],{S, 2, 20}]

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}

Nim

Translation of: C

import std/[monotimes, strutils, times]

const IsPrime = [false, false, true, true, false, true, false, true,
                 false, false, false, true, false, true, false, false,
                 false, true, false, true, false, false, false, true,
                 false, false, false, false, false, true, false, true,
                 false, false, false, false, false, true, false, false,
                 false, true, false, true, false, false, false, true,
                 false, false, false, false, false, true, false, false,
                 false, false, false, true, false, true, false, false]

type TriangleRow = openArray[Natural]

template isPrime(n: Natural): bool = IsPrime[n]

func primeTriangleRow(a: var TriangleRow): bool =
  if a.len == 2:
    return isPrime(a[0] + a[1])
  for i in countup(1, a.len - 2, 2):
    if isPrime(a[0] + a[i]):
      swap a[i], a[1]
      if primeTriangleRow(a.toOpenArray(1, a.high)):
        return true
      swap a[i], a[1]

func primeTriangleCount(a: var TriangleRow): Natural =
  if a.len == 2:
    if isPrime(a[0] + a[1]):
      inc result
  else:
    for i in countup(1, a.len - 2, 2):
      if isPrime(a[0] + a[i]):
        swap a[i], a[1]
        inc result, primeTriangleCount(a.toOpenArray(1, a.high))
        swap a[i], a[1]

proc print(a: TriangleRow) =
  if a.len == 0: return
  for i, n in a:
    if n > 0: stdout.write ' '
    stdout.write align($n, 2)
  stdout.write '\n'

let start = getMonoTime()
for n in 2..20:
  var a = newSeq[Natural](n)
  for i in 0..<n:
    a[i] = i + 1
  if a.primeTriangleRow:
    print a
echo()
for n in 2..20:
  var a = newSeq[Natural](n)
  for i in 0..<n:
    a[i] = i + 1
  if n > 2: stdout.write " "
  stdout.write a.primeTriangleCount
echo '\n'

echo "Elapsed time: ", (getMonoTime() - start).inMilliseconds, " ms"

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: 535 ms

Pascal

Free Pascal

Simple backtracking.Precaltulated like Prime_triangle#Phix Can_Follow by checking for sum gets prime.

program PrimePyramid;
{$IFDEF FPC}
  {$MODE delphi}{$Optimization ON,ALL}{$CodeAlign proc=32}
{$IFEND}
const
  MAX = 21;//max 8 different  SumToPrime : array[0..MAX,0..7] of byte;
  //MAX = 57;//max 16 different SumToPrime : array[0..MAX,0..15] of byte;
  cMaxAlign32 = (((MAX-1)DIV 32)+1)*32-1;//MAX > 0
type
  tPrimeRange = set of 0..127;
var
  SetOfPrimes :tPrimeRange =[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,
                             53,59,61,67,71,73,79,83,89,97,101,103,107,
                             109,113,127];

  SumToPrime : array[0..cMaxAlign32,0..7] of byte;
//  SumToPrime : array[0..MAX,0..15] of byte;
  SumToPrimeMaxIdx,
  SumMaxIdx,
  Solution,
  FirstSolution    : array[0..cMaxAlign32] of byte;

  free : array[0..cMaxAlign32] of boolean;

  maxused : integer;
  digitcount,SolCount : integer;

procedure InitSumToPrime;
var
  i,j,idx : integer;
begin
  For i := 1 to MAX do
  Begin
    idx := 0;
    For j := 1 to MAX do
      If (i+j) in SetOfPrimes then
      Begin
        SumToPrime[i,idx] := j;
        inc(idx);
      end;
    SumToPrimeMaxIdx[i] := idx;
  end;
end;

procedure InitFree(maxused : integer);
var
  i,j : Integer;
begin
  For i := 0 to 1 do
    Free[i] := false;
  For i := 2 to maxused-1 do
    Free[i] := true;
  For i := maxused to MAX do
    Free[i] := false;
  // search maxidx of max neighour sum to prime
  For i := 1 to maxused-1 do
  begin
    j := SumToPrimeMaxIdx[i]-1;
    while SumToPrime[i,j] > maxused-1 do
      j -= 1;
    SumMaxIdx[i] := j+1;
  end;
end;

procedure CountSolution(digit:integer);
begin
  // check if maxused can follow
  if (digit+maxused) in SetOfPrimes then
  Begin
    if solcount = 0 then
       FirstSolution := Solution;
    inc(solCount);
  end;
end;

procedure checkDigits(digit:integer);
var
  idx,nextDigit: integer;
begin
  idx := 0;
  repeat
    nextDigit := SumToPrime[digit,idx];
    if Free[nextdigit] then
    Begin
      Solution[digitcount] := nextDigit;
      dec(digitcount);
      IF digitcount = 0 then
        CountSolution(nextDigit);
      free[nextdigit]:= false;
      checkDigits(nextdigit);
      inc(digitcount);
      free[nextdigit]:= true;
    end;
    inc(idx);
  until idx >= SumMaxIdx[digit];
end;

var
  i,j : integer;
Begin
  InitSumToPrime;
  writeln('number|   count|  first solution');
  writeln('   2|         1|  1  2');
  For i := 3 to 20 do
  Begin
    maxused := i;
    InitFree(i);
    digitcount := i-2;
    solCount := 0;
    checkDigits(1);
    write(i:4,'|',solcount:10,'|  1');
    For j := i-2 downto 1 do
      write( FirstSolution[j]:3);
    writeln(i:3);
  end;
end.

@TIO.RUN:

number|   count|  first solution
   2|         1|  1  2
   3|         1|  1  2  3
   4|         1|  1  2  3  4
   5|         1|  1  4  3  2  5
   6|         1|  1  4  3  2  5  6
   7|         2|  1  4  3  2  5  6  7
   8|         4|  1  2  3  4  7  6  5  8
   9|         7|  1  2  3  4  7  6  5  8  9
  10|        24|  1  2  3  4  7  6  5  8  9 10
  11|        80|  1  2  3  4  7 10  9  8  5  6 11
  12|       216|  1  2  3  4  7 10  9  8  5  6 11 12
  13|       648|  1  2  3  4  7  6  5 12 11  8  9 10 13
  14|      1304|  1  2  3  4  7  6 13 10  9  8 11 12  5 14
  15|      3392|  1  2  3  4  7  6 13 10  9  8 11 12  5 14 15
  16|     13808|  1  2  3  4  7  6  5 12 11  8 15 14  9 10 13 16
  17|     59448|  1  2  3  4  7  6  5 12 11  8  9 10 13 16 15 14 17
  18|    155464|  1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18
  19|    480728|  1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 11 18 19
  20|   1588162|  1  2  3  4  7  6  5  8  9 10 13 16 15 14 17 12 19 18 11 20
Real time: 1.827 s User time: 1.794 s Sys. time: 0.021 s CPU share: 99.36 %
@home: real 0m0,679s

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.
    integer ad = arrang[done]
    if n-done<=1 then
        if can_follow[ad][n] 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]
            if can_follow[ad][ai] then
                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)
    can_follow = repeat(repeat(false,n),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"

Python

from numpy import array
# for Rosetta Code by MG - 20230312
def is_prime(n: int) -> bool:
    assert n < 64
    return ((1 << n) & 0x28208a20a08a28ac) != 0

def prime_triangle_row(a: array, start: int, length: int) -> bool:
    if length == 2:
        return is_prime(a[0] + a[1])
    for i in range(1, length - 1, 1):
        if is_prime(a[start] + a[start + i]):
            a[start + i], a[start + 1] = a[start + 1], a[start + i]
            if prime_triangle_row(a, start + 1, length - 1):
                return True
            a[start + i], a[start + 1] = a[start + 1], a[start + i]
    return False

def prime_triangle_count(a: array, start: int, length: int) -> int:
    count: int = 0
    if length == 2:
        if is_prime(a[start] + a[start + 1]):
            count += 1
    else:
        for i in range(1, length - 1, 1):
            if is_prime(a[start] + a[start + i]):
                a[start + i], a[start + 1] = a[start + 1], a[start + i]
                count += prime_triangle_count(a, start + 1, length - 1)
                a[start + i], a[start + 1] = a[start + 1], a[start + i]
    return count

def print_row(a: array):
    if a == []:
        return
    print("%2d"% a[0], end=" ")
    for x in a[1:]:
        print("%2d"% x, end=" ")
    print()

for n in range(2, 21):
    tr: array = [_ for _ in range(1, n + 1)]
    if prime_triangle_row(tr, 0, n):
        print_row(tr)
print()
for n in range(2, 21):
    tr: array = [_ for _ in range(1, n + 1)]
    if n > 2:
        print(" ", end="")
    print(prime_triangle_count(tr, 0, n), end="")
print()

Output:

 1  2 
 1  2  3 
 1  2  3  4 
 1  2  3  4  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  6  5  8  9 10 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  5 12 11  8  9 10 13 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 11 18 19 20 

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

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

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 ptrs
ptrs = 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