107 lines
3.5 KiB
Plaintext
107 lines
3.5 KiB
Plaintext
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
|