Prime triangle
Prime triangle is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
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 #
PR read "primes.incl.a68" PR
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
INT result := current + 1;
WHILE result < n AND ( NOT prime pair[ i, result ] OR used[ result ] ) DO
result +:= 1
OD;
IF result >= n OR NOT prime pair[ i, result ] OR used[ result ] THEN result := 0 FI;
result
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;
[ 0 : n ]INT position;
FOR i FROM 0 TO n DO
used[ i ] := FALSE;
number[ i ] := 0;
position[ i ] := 1
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, position[ pn ], 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
position[ pn ] := next;
next := find next( pn, n, position[ pn ], used )
OD
FI;
IF next /= 0 THEN
# have a/another number that can appear at p #
used[ position[ pn ] ] := FALSE;
position[ pn ] := next;
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[ position[ pn ] ] := FALSE;
position[ pn ] := 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[ position[ pn ] ] := FALSE;
position[ pn ] := 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 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(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(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(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
Julia
<lang julia>using Combinatorics, Random, 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)
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
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 + 1
Do While result < n And (Not primePair(i, result) Or used(result))
result += 1
Loop
If result >= n Or (Not primePair(i, result) Or used(result)) 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
Dim position(n) As Integer
For i As Integer = 0 To n
position(i) = 1
Next i
' 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, position(pn), used)
If p = n - 1 Then
' We are at the final number before n.
Do While If([next] = 0, False, Not primePair([next], n))
position(pn) = [next]
[next] = findNext(pn, n, position(pn), used)
Loop
End If
If [next] <> 0 Then
' have a/another number that can appear at p.
used(position(pn)) = False
position(pn) = [next]
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(position(pn)) = False
position(pn) = 0
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(position(pn)) = False
position(pn) = 0
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 1 1 1 1 2 4 7 24 80 216 648 1304 3392 13808 59448 155464
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