The Prime Circle

A prime circle of order $2n$ is an arrangement of the integers $1, 2, \ldots, 2n$ around a circle such that every adjacent pair sums to a prime. For $n = 2$ the arrangement $1, 2, 3, 4$ is a prime circle: the four adjacent sums are $3, 5, 7, 5$, all prime. For $n = 5$, the circle $$1 \to 2 \to 5 \to 8 \to 9 \to 10 \to 3 \to 4 \to 7 \to 6 \to 1$$ has adjacent sums $3, 7, 13, 17, 19, 13, 7, 11, 13, 7$ — again, all prime. One is naturally led to ask for which $n \geq 1$ a prime circle exists.

The problem was proposed by Antonio Filz in the Journal of Recreational Mathematics in $1982$. For $n \geq 2$, a simple parity argument shows that any prime circle must alternate even and odd numbers. Indeed, the only even prime is $2$, and two adjacent numbers in the circle can sum to $2$ only if they are both equal to $1$, which is forbidden (they are distinct). Hence every adjacent sum is odd, so one addend is even and the other odd; the circle alternates. Since the set $\{1, \ldots, 2n\}$ contains exactly $n$ evens and $n$ odds, alternation is possible whenever the circle length $2n$ is even, which it always is. The parity argument rules out no $n$; the actual question is whether the sums can all be prime, given that the evens and odds must interleave.

Filz conjectured that a prime circle exists for every $n \geq 2$. The conjecture remains open, but the evidence is substantial: the counts recorded in OEIS sequence A051252 are nonzero for every order checked, a range that Tilley and Wagon extended to $n = 10^6$, and recent work on the Hamiltonicity of prime-sum graphs has proved that prime circles exist for infinitely many even orders. No infinite family of counterexamples is known, and no full proof of existence is known either.

The programming model

The encoding is particularly compact. For each position $i \in \{0, 1, \ldots, 2n - 1\}$ on the circle, let $x_i \in \{1, \ldots, 2n\}$ be the integer occupying that position. The constraints are:

Distinctness

$$\operatorname{AllDifferent}(x_0, x_1, \ldots, x_{2n - 1}).$$

Adjacent-sum primality

Precompute the list of pairs $(a, b)$ with $a, b \in \{1, \ldots, 2n\}$, $a \neq b$, and $a + b$ prime. For every pair of adjacent positions $(i, i + 1 \bmod 2n)$ impose the table constraint $$(x_i, x_{i + 1}) \;\in\; \text{PrimePairs}.$$

Symmetry breaking

A circle and its rotation are the same arrangement; likewise a circle and its reflection. The two symmetries have orders $2n$ and $2$ respectively, giving a $4n$-fold orbit. Break the rotational symmetry by pinning $x_0 = 1$; break the reflection by requiring $x_1 < x_{2n - 1}$.

A solver in fifteen lines

from ortools.sat.python import cp_model
from sympy import isprime

def prime_circle(n):
    N = 2 * n
    pairs = [(a, b)
             for a in range(1, N + 1)
             for b in range(1, N + 1)
             if a != b and isprime(a + b)]
    m = cp_model.CpModel()
    x = [m.NewIntVar(1, N, "") for _ in range(N)]
    m.AddAllDifferent(x)
    for i in range(N):
        m.AddAllowedAssignments(
            [x[i], x[(i + 1) % N]], pairs)
    m.Add(x[0] == 1)
    m.Add(x[1] < x[N - 1])
    s = cp_model.CpSolver()
    s.Solve(m)
    return [s.Value(v) for v in x]

The solver returns one prime circle for each requested $n$ (a plain feasibility solve, so the particular circle found is not guaranteed to be the lexicographically smallest). Selected timings on a standard laptop: $$n = 3 : 2 \text{ ms}; \quad n = 5 : 4 \text{ ms};$$ $$n = 8 : 15 \text{ ms}; \quad n = 20 : 90 \text{ ms};$$ $$n = 50 : 1.2 \text{ s}.$$ Figure 13.1 shows the prime circle of order $10$ found above; Figure 13.2 is the order-$16$ case.

Sources. Filz’s original question appears as Problem $1046$ in the Journal of Recreational Mathematics, volume $14$ ($1982$), page $64$, with solutions in volume $15$ ($1983$). Count data for prime circles (up to rotation and reflection) are listed as OEIS sequence A051252: the values $a(n)$ for $n = 1, 2, 3, \ldots$ are $1, 1, 1, 2, 48, 512, 1\,440, \ldots$, growing rapidly but not yet proven to be nonzero for all $n$. The connection to Goldbach’s conjecture is sometimes asserted but is essentially superficial: if one could prove Goldbach, prime circles would not immediately follow, and the converse holds still less.