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.
As Algol 68G under Windows is fully interpreted, a reduced number of rows is produced. <lang algol68>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; [ 1 : max number, 1 : max number ]BOOL prime pair; FOR a TO max number DO prime pair[ a, 1 ] := FALSE; FOR b FROM 2 TO max number DO prime pair[ a, b ] := prime[ a + b ] OD; prime pair[ a, a ] := FALSE OD; # finds the next number that can follow i or 0 if there isn't one # PROC find next = ( INT i, INT n, INT current, []BOOL used )INT: BEGIN # the numbers must alternate between even and odd in order for the sum to be prime # INT result := IF current > 0 THEN current + 2 ELIF ODD i THEN 2 ELSE 3 FI; WHILE IF result >= n THEN FALSE ELSE NOT prime pair[ i, result ] OR used[ result ] FI DO result +:= 2 OD; IF result >= n THEN 0 ELSE result FI END # find next # ; # returns the number of possible arrangements of the integers for a row in the prime triangle # PROC count arrangements = ( INT n, BOOL print solution )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 # IF print solution THEN FOR i TO n DO print( ( whole( i, -3 ) ) ) OD; print( ( newline ) ) FI; 1 ELSE # 4 or more - must find the solutions # [ 0 : n ]BOOL used; [ 0 : n ]INT number; FOR i FROM 0 TO n DO used[ i ] := FALSE; number[ i ] := 0 OD; # the triangle row must have 1 in the leftmost and n in the rightmost elements # number[ 1 ] := 1; 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 < n DO INT pn = number[ p - 1 ]; INT next := find next( pn, n, number[ p ], used ); IF p = n - 1 THEN # we are at the final number before n # WHILE IF next = 0 THEN FALSE ELSE NOT prime pair[ next, n ] FI DO next := find next( pn, n, next, used ) OD FI; IF next /= 0 THEN # have a/another number that can appear at p # used[ number[ p ] ] := FALSE; used[ next ] := TRUE; number[ p ] := next; IF p < n - 1 THEN # haven't found all the intervening digits yet # p +:= 1; number[ p ] := 0 ELSE # found a solution # count +:= 1; IF count = 1 AND print solution THEN FOR i TO n DO print( ( whole( number[ i ], -3 ) ) ) OD; print( ( newline ) ) FI; # backtrack for more solutions # used[ number[ p ] ] := FALSE; number[ p ] := 0; p -:= 1 FI ELIF p <= 2 THEN # no more solutions # p := n ELSE # can't find a number for this position, backtrack # used[ number[ p ] ] := FALSE; number[ p ] := 0; 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, TRUE ) OD; FOR n FROM LWB arrangements TO UPB arrangements DO print( ( " ", whole( arrangements[ n ], 0 ) ) ) OD; print( ( newline ) )
END </lang>
- 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
<lang 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;
}</lang>
- 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++
<lang cpp>#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";
}</lang>
- 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#) <lang fsharp> // 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 "" </lang>
- 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
<lang go>package main
import "fmt"
var canFollow [][]bool var avail []bool var arrang []int var bCount = false
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 !bCount { for _, e := range arrang { fmt.Printf("%2d ", e) } fmt.Println() } res++ } } else { done++ for i := 1; i <= n-2; i++ { if avail[i] && canFollow[ad-1][i] { avail[i] = false arrang[done-1] = i + 1 res = ptrs(res, n, done) if !bCount && res != 0 { return res } avail[i] = true } } } 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 } } avail = make([]bool, n) for i := 1; i < n-1; i++ { avail[i] = true } arrang = make([]int, n) arrang[0] = 1 arrang[n-1] = n return ptrs(0, n, 1)
}
func main() {
for i := 2; i <= 20; i++ { primeTriangle(i) } fmt.Println() bCount = true for i := 2; i <= 20; i++ { fmt.Printf("%d ", primeTriangle(i)) } fmt.Println()
}</lang>
- 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
Paraphrase of C based on OEIS:
<lang 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.
}}</lang>
Task example:
<lang J>
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</lang>
Java
<lang 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) { 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) { 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; }
}</lang>
- 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: 977 milliseconds
Julia
Filter method
<lang julia>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)
</lang>
- 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. <lang julia>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
</lang>
- 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)
Phix
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 42s).
with javascript_semantics atom t0 = time() sequence can_follow, avail, 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 for i=2 to n-1 do if avail[i] and can_follow[ad][i] then avail[i] = false arrang[done] = i res = ptrs(res,n,done) avail[i] = true 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 avail = reinstate(repeat(true,n),{1,n},{false,false}) arrang = reinstate(repeat(0,n),{1,n},{1,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 "15.5s"
Raku
Limit the upper threshold a bit to avoid multiple hours of pointless calculations. Even just up to 17 takes over 20 minutes.
<lang perl6>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..*];</lang>
- 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
<lang 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 { 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 { 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());
}</lang>
- 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: 711 milliseconds
Swift
<lang 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 ArraySlice<Int>) -> Bool {
let start = a.startIndex let end = a.endIndex if a.count == 2 { return isPrime(a[start] + a[start + 1]) } for i in start + 1..<end - 1 { if isPrime(a[start] + a[i]) { a.swapAt(i, start + 1) if primeTriangleRow(&a[start + 1..<end]) { return true } a.swapAt(i, start + 1) } } return false
}
func primeTriangleCount(_ a: inout ArraySlice<Int>) -> Int {
let start = a.startIndex let end = a.endIndex var count = 0 if a.count == 2 { if isPrime(a[start] + a[start + 1]) { count += 1 } } else { for i in start + 1..<end - 1 { if isPrime(a[start] + a[i]) { a.swapAt(i, start + 1) count += primeTriangleCount(&a[start + 1..<end]) a.swapAt(i, 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()
}
for n in 2...20 {
var a = Array(1...n) if primeTriangleRow(&a[...]) { printRow(a) }
} print()
for n in 2...20 {
var a = Array(1...n) if n > 2 { print(" ", terminator: "") } print("\(primeTriangleCount(&a[...]))", terminator: "")
} print()</lang>
- 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
Visual Basic .NET
<lang vbnet>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. Dim primePair(maxNumber, maxNumber) As Boolean ' Table of numbers that sum to a prime.
<returns>The next number that can follow i or 0 if there isn't one.</returns> Public Function findNext(ByVal i As Integer, ByVal n As Integer, ByVal current As Integer, ByVal used() As Boolean) As Integer Dim result As Integer = current + 2 ' The numbers must alternate between even and odd in order for the sum to be prime. If i Mod 2 = 0 And result = 2 Then result = 3 End If Do While result < n AndAlso (Not primePair(i, result) Or used(result)) result += 2 Loop If result >= n Then result = 0 End If Return result End Function
<returns>The number of possible arrangements of the integers for a row in the prime triangle.</returns> Public Function countArrangements(ByVal n As Integer, ByVal printSolution As Boolean ) 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. If printSolution Then For i As Integer = 1 To n Console.Out.Write(i.ToString.PadLeft(3)) Next i Console.Out.WriteLine() End If Return 1 Else ' 4 or more - must find the solutions. 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. number(1) = 1 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 < n Dim pn As Integer = number(p - 1) Dim [next] As Integer = findNext(pn, n, number(p), used) If p = n - 1 Then ' We are at the final number before n. Do While If([next] = 0, False, Not primePair([next], n)) [next] = findNext(pn, n, [next], used) Loop End If If [next] <> 0 Then ' have a/another number that can appear at p. used(number(p)) = False used([next]) = True number(p) = [next] If p < n - 1 Then ' Haven't found all the intervening digits yet. p += 1 number(p) = 0 Else ' Found a solution. count += 1 If count = 1 And printSolution Then For i As Integer = 1 To n Console.Out.Write(number(i).ToString.PadLeft(3)) Next i Console.Out.WriteLine() End If ' Backtrack for more solutions. used(number(p)) = False number(p) = 0 p -= 1 End If ElseIf p <= 2 Then ' No more solutions. p = n Else ' Can't find a number for this position, backtrack. used(number(p)) = False number(p) = 0 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 For a As Integer = 1 To maxNumber primePair(a, 1) = False For b As Integer = 2 To maxNumber primePair(a, b) = prime(a + b) Next b primePair(a, a) = False Next a
Dim arrangements(maxNumber) As Integer For n As Integer = 2 To UBound(arrangements) arrangements(n) = countArrangements(n, True) Next n For n As Integer = 2 To UBound(arrangements) Console.Out.Write(" " & arrangements(n)) Next n Console.Out.WriteLine()
End Sub
End Module</lang>
- 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
Takes around 57.3 seconds which is fine for Wren. <lang ecmascript>import "./fmt" for Fmt import "./ioutil" for Output
var canFollow = [] var avail = [] var arrang = [] var bCount = false
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 (!bCount) Fmt.print("$2d", arrang) res = res + 1 } } else { done = done + 1 for (i in 1..n-2) { if (avail[i] && canFollow[ad-1][i]) { avail[i] = false arrang[done-1] = i+1 res = ptrs.call(res, n, done) if (!bCount && res != 0) return res avail[i] = true } } } 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) } avail = List.filled(n, true) avail[0] = avail[n-1] = false arrang = List.filled(n, 0) arrang[0] = 1 arrang[n-1] = n return ptrs.call(0, n, 1)
}
for (i in 2..20) primeTriangle.call(i) System.print() bCount = true for (i in 2..20) Output.fwrite("%(primeTriangle.call(i)) ") System.print()</lang>
- 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