Prime triangle: Difference between revisions
(→{{header|J}}: more concise approach) |
(Added FreeBASIC) |
||
(15 intermediate revisions by 10 users not shown) | |||
Line 2: | Line 2: | ||
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<sub>1</sub>=1 g<sub>S</sub>=S and generally for n=1 to n=S-1 g<sub>n</sub>+g<sub>n+1</sub> 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. |
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<sub>1</sub>=1 g<sub>S</sub>=S and generally for n=1 to n=S-1 g<sub>n</sub>+g<sub>n+1</sub> 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|OEIS:A036440]] |
|||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
Line 7: | Line 12: | ||
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}} |
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}} |
||
As Algol 68G under Windows is fully interpreted, a reduced number of rows is produced. |
As Algol 68G under Windows is fully interpreted, a reduced number of rows is produced. |
||
< |
<syntaxhighlight 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 # |
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 # |
# construct a primesieve and from that a table of pairs of numbers whose sum is prime # |
||
Line 100: | Line 105: | ||
OD; |
OD; |
||
print( ( newline ) ) |
print( ( newline ) ) |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 121: | Line 126: | ||
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 |
||
1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 |
1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 |
||
</pre> |
|||
=={{header|BASIC}}== |
|||
==={{header|FreeBASIC}}=== |
|||
{{trans|Visual Basic .NET}} |
|||
<syntaxhighlight lang="vbnet">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</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Same as Visual Basic .NET entry.</pre> |
|||
==={{header|Visual Basic .NET}}=== |
|||
{{Trans|ALGOL 68}} |
|||
<syntaxhighlight 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. |
|||
''' <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</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
</pre> |
||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<syntaxhighlight lang="c">#include <assert.h> |
||
#include <stdbool.h> |
#include <stdbool.h> |
||
#include <stdio.h> |
#include <stdio.h> |
||
Line 207: | Line 466: | ||
printf("\nElapsed time: %f seconds\n", duration); |
printf("\nElapsed time: %f seconds\n", duration); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 239: | Line 498: | ||
Number combinations are all stored in bit positions here. The <code>bpos()</code> 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. |
Number combinations are all stored in bit positions here. The <code>bpos()</code> 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. |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <stdint.h> |
#include <stdint.h> |
||
Line 330: | Line 589: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 1 2 |
<pre> 1 2 |
||
Line 355: | Line 614: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang="cpp">#include <cassert> |
||
#include <chrono> |
#include <chrono> |
||
#include <iomanip> |
#include <iomanip> |
||
Line 431: | Line 690: | ||
std::chrono::duration<double> duration(end - start); |
std::chrono::duration<double> duration(end - start); |
||
std::cout << "\nElapsed time: " << duration.count() << " seconds\n"; |
std::cout << "\nElapsed time: " << duration.count() << " seconds\n"; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 462: | Line 721: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)] |
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)] |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Prime triangle. Nigel Galloway: April 12th., 2022 |
// 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 fN i (g,(e,l))=e|>Seq.map(fun n->let n=i n in (n::g,List.partition(i>>(=)n) l)) |
||
Line 471: | Line 730: | ||
{2..20}|>Seq.iter(fun n->(primeT>>Seq.head>>List.iter(printf "%3d"))n;printfn "");; |
{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 "" |
{2..20}|>Seq.iter(primeT>>Seq.length>>printf "%d "); printfn "" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 500: | Line 759: | ||
Takes about 0.64 seconds. |
Takes about 0.64 seconds. |
||
{{trans|Phix}} |
{{trans|Phix}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 570: | Line 829: | ||
} |
} |
||
fmt.Println() |
fmt.Println() |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 599: | Line 858: | ||
=={{header|J}}== |
=={{header|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 intermediate values between 1 and y. |
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: |
Implementation: |
||
< |
<syntaxhighlight lang="j">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 }}</ |
prime_pair_seqs=: {{ y add_plink (2}.i.y) add_plink^:(y-2) 1 }}</syntaxhighlight> |
||
Task example (displaying counts of number of valid sequences to the left, because that looks nice): |
Task example (displaying counts of number of valid sequences to the left, because that looks nice): |
||
< |
<syntaxhighlight lang="j">task=: {{ |
||
for_j.2}.i.1+y do. |
for_j.2}.i.1+y do. |
||
N=. #seqs=. prime_pair_seqs j |
N=. #seqs=. prime_pair_seqs j |
||
Line 634: | Line 893: | ||
155464 | 1 16 15 14 17 12 11 8 9 10 13 6 7 4 3 2 5 18 |
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 |
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</ |
1588162 | 1 18 19 12 17 14 15 16 13 10 9 8 11 2 5 6 7 4 3 20</syntaxhighlight> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
< |
<syntaxhighlight lang="java">public class PrimeTriangle { |
||
public static void main(String[] args) { |
public static void main(String[] args) { |
||
long start = System.currentTimeMillis(); |
long start = System.currentTimeMillis(); |
||
Line 711: | Line 970: | ||
return ((1L << n) & 0x28208a20a08a28acL) != 0; |
return ((1L << n) & 0x28208a20a08a28acL) != 0; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 738: | Line 997: | ||
Elapsed time: 833 milliseconds |
Elapsed time: 833 milliseconds |
||
</pre> |
|||
=={{header|jq}}== |
|||
{{works with|jq}} |
|||
'''Adapted from [[#Wren|Wren]]''' |
|||
(gojq requires too much memory to complete the task.) |
|||
<syntaxhighlight lang=jq> |
|||
# $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)[] |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<pre> |
|||
[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] |
|||
</pre> |
</pre> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
=== Filter method === |
=== Filter method === |
||
< |
<syntaxhighlight lang="julia">using Combinatorics, Primes |
||
function primetriangle(nrows::Integer) |
function primetriangle(nrows::Integer) |
||
Line 773: | Line 1,135: | ||
@time primetriangle(16) |
@time primetriangle(16) |
||
</ |
</syntaxhighlight>{{out}} |
||
<pre> |
<pre> |
||
1 2 |
1 2 |
||
Line 797: | Line 1,159: | ||
=== Generator method === |
=== Generator method === |
||
Similar to the Phix entry. |
Similar to the Phix entry. |
||
< |
<syntaxhighlight lang="julia">using Primes |
||
function solverow(row, pos, avail) |
function solverow(row, pos, avail) |
||
Line 829: | Line 1,191: | ||
println(" 1 2\n" * prod(rowstrings), "\n", counts) |
println(" 1 2\n" * prod(rowstrings), "\n", counts) |
||
end |
end |
||
</ |
</syntaxhighlight> {{out}} |
||
<pre> |
<pre> |
||
1 2 |
1 2 |
||
Line 856: | Line 1,218: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">ClearAll[FindPrimeTriangles, FindPrimeTrianglesHelper] |
||
FindPrimeTriangles[max_] := |
FindPrimeTriangles[max_] := |
||
Module[{count = 0, firstsolution, primes, primeQ}, |
Module[{count = 0, firstsolution, primes, primeQ}, |
||
Line 888: | Line 1,250: | ||
count |
count |
||
] |
] |
||
Table[FindPrimeTriangles[S],{S, 2, 20}]</ |
Table[FindPrimeTriangles[S],{S, 2, 20}]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{1,2} |
<pre>{1,2} |
||
Line 912: | Line 1,274: | ||
{1, 1, 1, 1, 1, 2, 4, 7, 24, 80, 216, 648, 1304, 3392, 13808, 59448, 155464, 480728, 1588162}</pre> |
{1, 1, 1, 1, 1, 2, 4, 7, 24, 80, 216, 648, 1304, 3392, 13808, 59448, 155464, 480728, 1588162}</pre> |
||
=={{header|Nim}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight lang="Nim">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" |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 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 |
|||
</pre> |
|||
=={{header|Pascal}}== |
|||
==={{header|Free Pascal}}=== |
|||
Simple backtracking.Precaltulated like [[Prime_triangle#Phix]] Can_Follow by checking for sum gets prime. |
|||
<syntaxhighlight lang="pascal"> |
|||
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. |
|||
</syntaxhighlight> |
|||
{{out|@TIO.RUN}} |
|||
<pre> |
|||
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</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{trans|Raku}} |
{{trans|Raku}} |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use feature 'say'; |
use feature 'say'; |
||
Line 949: | Line 1,546: | ||
} |
} |
||
say "\n" . join ' ', @count[2..$#count];</ |
say "\n" . join ' ', @count[2..$#count];</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 2 |
<pre>1 2 |
||
Line 973: | Line 1,570: | ||
{{libheader|Phix/online}} |
{{libheader|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. 😎<br> You can run this online [http://phix.x10.mx/p2js/prime_triangles.htm here] (expect a blank screen for about 24s). |
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. 😎<br> You can run this online [http://phix.x10.mx/p2js/prime_triangles.htm here] (expect a blank screen for about 24s). |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
||
Line 1,026: | Line 1,623: | ||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">:=</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">))</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">:=</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">))</span> |
||
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span> |
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,050: | Line 1,647: | ||
1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 480728 1588162 |
1 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464 480728 1588162 |
||
"9.7s" |
"9.7s" |
||
</pre> |
|||
=={{header|Python}}== |
|||
<syntaxhighlight lang="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() |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
</pre> |
||
Line 1,055: | Line 1,731: | ||
Limit the upper threshold a bit to avoid multiple hours of pointless calculations. Even just up to 17 takes over 20 minutes. |
Limit the upper threshold a bit to avoid multiple hours of pointless calculations. Even just up to 17 takes over 20 minutes. |
||
<lang |
<syntaxhighlight lang="raku" line>my @count = 0, 0, 1; |
||
my $lock = Lock.new; |
my $lock = Lock.new; |
||
put (1,2); |
put (1,2); |
||
Line 1,079: | Line 1,755: | ||
} |
} |
||
} |
} |
||
put "\n", @count[2..*];</ |
put "\n", @count[2..*];</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 2 |
<pre>1 2 |
||
Line 1,102: | Line 1,778: | ||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
< |
<syntaxhighlight lang="rust">fn is_prime(n: u32) -> bool { |
||
assert!(n < 64); |
assert!(n < 64); |
||
((1u64 << n) & 0x28208a20a08a28ac) != 0 |
((1u64 << n) & 0x28208a20a08a28ac) != 0 |
||
Line 1,172: | Line 1,848: | ||
let time = start.elapsed(); |
let time = start.elapsed(); |
||
println!("\nElapsed time: {} milliseconds", time.as_millis()); |
println!("\nElapsed time: {} milliseconds", time.as_millis()); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,202: | Line 1,878: | ||
=={{header|Swift}}== |
=={{header|Swift}}== |
||
< |
<syntaxhighlight lang="swift">import Foundation |
||
func isPrime(_ n: Int) -> Bool { |
func isPrime(_ n: Int) -> Bool { |
||
Line 1,278: | Line 1,954: | ||
let endTime = CFAbsoluteTimeGetCurrent() |
let endTime = CFAbsoluteTimeGetCurrent() |
||
print("\nElapsed time: \(endTime - startTime) seconds")</ |
print("\nElapsed time: \(endTime - startTime) seconds")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,305: | Line 1,981: | ||
Elapsed time: 1.0268970727920532 seconds |
Elapsed time: 1.0268970727920532 seconds |
||
</pre> |
|||
=={{header|Visual Basic .NET}}== |
|||
{{Trans|ALGOL 68}} |
|||
<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. |
|||
''' <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</lang> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
</pre> |
||
Line 1,453: | Line 1,987: | ||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
Takes around 18.7 seconds which is fine for Wren. |
Takes around 18.7 seconds which is fine for Wren. |
||
< |
<syntaxhighlight lang="wren">import "./fmt" for Fmt |
||
var canFollow = [] |
var canFollow = [] |
||
Line 1,507: | Line 2,041: | ||
} |
} |
||
System.print() |
System.print() |
||
System.print(counts.join(" "))</ |
System.print(counts.join(" "))</syntaxhighlight> |
||
{{out}} |
{{out}} |
Latest revision as of 01:24, 3 March 2024
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.
- See also
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.
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
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
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.
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
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
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
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
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
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