Solution
Problem 1218 asked for a circular arrangement of the numbers from 1 to 20 so that each pair of neighbors sums to a prime.
First, some source notes. The problem is known as the "Prime Circle Problem" and is due to Antonio Filz (Problem 1046, J. Recr. Math. vol 14, p 64, 1982; vol 15, p 71, 1983). It appears in the classic book by Richard Guy, Unsolved Problems in Number Theory, 2nd edition, §C1. See MathWorld's entry and The New York Times' Numberplay blog post on the puzzle. Good information about the problem is available from The On-Line Encyclopedia of Integer Sequences® entries for sequences A051252, A072616, and A227050, the last two of which describe even stronger versions that seem to be true.
It appears that such prime-sum cycles exist for all even n. They cannot exist for odd n by a simple parity argument.
Several readers found a solution for the case posed: Joseph DeVincentis, Robert Israel, Jim Tilley, Stephen Meskin, Philippe Fondanaiche, Al Zimmermann, and Rob Pratt.
In terms of lexicography, the first solution is
1, 2, 3, 4, 7, 6, 5, 8, 9, 10, 13, 16, 15, 14, 17, 20, 11, 12, 19, 18
Nothing is known about how to find a general proof for all n, but there are several interesting computational approaches.
The prime circle is a Hamiltonian cycle in the bipartite graph made from the edges that exist upon satisfaction of the condition (namely, the sum is prime). There are many algorithms for finding Hamiltonian cycles, so solving a given small case by computer is not hard. I used a sophisticated method based on Concorde, the world's best code for the traveling salesman problem, to find such cycles for 1000 points.
But there are more efficient ways. Robert Israel has an inductive technique that he used, with Maple's help, to check all cases up to n = 20,000. Jim Tilley did something similar, working in APL, and got up to n = 80,000. I programmed Jim's method in Mathematica and it got to 1,300,000 overnight.
The OEIS entry on the problem describes a very simple greedy algorithm that appears to work in all cases. Start with 1 and, at each step, choose the largest (!) unchosen number that works. That is quite easy to program and I did so in Mathematica, using 1.5 CPU hours to get a prime circle for n = 100,000. The code is
GreedyPrimeCircle[n_]:=(Clear[f, used]; f[1] = 1; used[_] = False;
used[1] = True; r = Range[n,1,-1];
Do[ f[i] =
Select[r, !used[#] && PrimeQ[ f[i-1] + #] &,1][[1]];
used[ f[i] ] = True, {i, 2, n}];
f /@ Reverse[r] )
So we see that there are several conjectures about prime circles that are stronger than the basic question.
1. Does the greedy algorithm always yield a prime circle?
2. Is there always a prime circle where the odd numbers appear in order 1, 3, 5, ...? (See the OEIS entry A072616.) A positive solution to (2) implies the twin prime conjecture, since 2N - 1, 2M, 2N + 1, at the end of circle gives twin primes 2N + 2M + {-1, +1}, which is larger than 2N.
3. Is there, for n ≥ 22, a "strong prime circle," where BOTH the sum and the absolute value of the difference of any neighboring pair is prime? (See the OEIS entry A227050.) For problem 3, note that, when n = 14, there is a unique solution.
Of course, the Holy Grail is a proof of a general result for any of these problems, but that seems difficult. I am not sure if anyone has formulated a hypothesis on the primes that would imply a prime circle exists for all n. So much is known about prime distribution that this would seem like the first necessary step.
Here is Tilley's algorithm to find cycles of lengths 2 up to some maximum n.
Start with n = 2 and the cycle (1, 2, 1). Iterate two at a time, moving to n = 4, 6, etc. Extend the Hamiltonian cycle as follows:
1. If n + 1, n + 2 sum to a prime, find a point in the n-cycle where the pair n + 1, n + 2 can be inserted, in one of the two orders, between two adjacent numbers so as to preserve the prime-sum property. If such a point does not exist, return FAILED and quit.
2. If 2n + 3 is not prime, take the odd number n + 1 and find an odd number in the n-cycle that it can replace and maintain the integrity of consecutive numbers adding to a prime. If no such exists, return FAILED and quit. Do this in two ways:
2A: First, test the odd numbers (in as yet "untried" positions) that, when added to n + 2, produce a prime. If one of those exists, call it newOdd; make the switch and go to Step 1 with the pair (newOdd, n + 2).
2B. If 2A fails, test the remaining odd numbers (in as yet "untried" positions), but ignore the condition on newOdd + (n + 2). Get a newOdd in this way. Now go back to step 2 with the new cycle and the new pair of numbers to add being (newOdd, n + 2). But before doing so, mark the switching position as having been "tried" so that it is not tried again (else an infinite loop can arise).
Here is Tilley's algorithm coded by me in Mathematica. Some optimization might be possible, but this is already pretty fast.
selectone[a_, b_] := (If[# == {}, #, #[[1]]] &)[Select[a, b, 1]];
switchStep1PrimeSum[cy_, {i_, j_}] := With[{n = Length[cy] - 1,
rr = Range[Length[cy] - 1]},
sss = selectone[rr[[2;;n;;2]],
PrimeQ[cy[[#]] + i] && PrimeQ[j + cy[[#+1]]] &];
If[IntegerQ[sss], Flatten[Insert[cy, {i, j}, sss + 1]],
sss = selectone[rr[[1;;n;;2]],
PrimeQ[cy[[#]] + j] && PrimeQ[cy[[#+1]] + i] &];
If[IntegerQ[sss], Flatten[Insert[cy, {j, i}, sss + 1]], $Failed]]];
switch[s_] := ({currentOdd, ans1[[s]]} = {ans1[[s]], currentOdd};
If[s == 1, ans1[[-1]] = ans1[[s]]]);
next[ans_] := With[{n = Length[ans] - 1}, Clear[tried];
tried[_] = False; ans1 = ans;
success = False; r = Range[1, n, 2];
If[PrimeQ[2n+3], ans1 = switchStep1PrimeSum[ans, {n+1, n+2}],
currentOdd = n+1;
While[ !success,
ss1 = selectone[r, PrimeQ[ans1[[#]] + n+2] &&
PrimeQ[ans1[[#+1]] + currentOdd] &&
PrimeQ[ans1[[#-1 /. 0 -> n]] + currentOdd] &];
If[IntegerQ[ss1], switch[ss1]; success = True;
ans1 = switchStep1PrimeSum[ans1, {currentOdd, n+2}],
ss2 = selectone[r, !tried[#] && PrimeQ[ans1[[#+1]] + currentOdd] &&
PrimeQ[ans1[[#-1 /. 0 -> n]] + currentOdd] &];
If[IntegerQ[ss2],tried[ss2]=True; switch[ss2]]]];
ans1]]
Then one gets, say, a cycle of length 100,000 by
Nest[next, {1,2,1}, 49999]
This method takes 6.5 seconds to cycles for all evens up to 20,000 and about two minutes for 100,000. I do not know what the prior record for this conjecture verification is, but Tilley's method is remarkably efficient and could probably get to 10,000,000. Perhaps some reader having a computer with lots of memory will code it in a faster language to see if 107 is possible. I got to 1,300,000 in about 8 hours with the code above, and it is pretty clear there can be no doubt that the basic prime-circle conjecture is true.
[Back to Problem 1218]
© Copyright 2016 Stan Wagon. Reproduced with permission.