Detailed mathematical approach

Problem Summary

Problem 983 asks for the smallest squared radius \(R(n)^2\) that allows a sufficiently large consonant family of equal circles. The implementations realize the configuration on the integer lattice: every chosen direction is a lattice point on the circle \(x^2+y^2=R(n)^2\), the actual circle centers are built from subset sums of those directions, and every nontrivial crossing of the chosen circles must occur at one of the designated crossing points produced by the same subset-sum construction.

The key simplification is that the code does not search directly for \(n\) unrelated circles. Instead it builds two parity classes of subset sums, one class for circle centers and one class for allowed crossings. If \(d\) directions are chosen, each parity class contains \(2^{d-1}\) points, so for \(n>2\) the search dimension is

$d=\min\{t\ge 1:2^{t-1}\ge n\}.$

The answer is then found by increasing \(m=1,2,3,\dots\) until the circle \(x^2+y^2=m\) supports such a \(d\)-direction construction.

Mathematical Approach

The whole method is built around equal-radius lattice vectors, subset sums, and a sharp characterization of which circle crossings are legitimate.

From \(n\) circles to \(d\) lattice directions

For \(n\le 2\), the problem is trivial and the implementations immediately return \(R(n)^2=1\). For larger \(n\), the construction uses \(d\) selected vectors \(v_1,\dots,v_d\), all with the same squared length \(m\). From them it forms the two parity classes

$E=\left\{\sum_{i\in A} v_i:\ |A|\equiv 0 \pmod 2\right\},\qquad O=\left\{\sum_{i\in A} v_i:\ |A|\equiv 1 \pmod 2\right\}.$

Here \(E\) is the family of circle centers actually counted by the search, while \(O\) is the family of crossing points that those circles are allowed to share. Both sets have size \(2^{d-1}\), which is why the least admissible \(d\) is the smallest one with \(2^{d-1}\ge n\).

Lattice points on a fixed radius

Fix \(m\) and write

$\Lambda_m=\{(x,y)\in\mathbb{Z}^2:x^2+y^2=m\}.$

Every chosen direction must come from \(\Lambda_m\). Because \(v\) and \(-v\) generate the same geometric direction up to parity reversal, the search keeps only one representative from each antipodal pair \(\{v,-v\}\). Therefore \(m\) is immediately impossible if \(\Lambda_m\) contains fewer than \(d\) antipodal pairs.

The factorization test used in the implementations is the standard two-squares criterion. If

$m=2^a\prod_i p_i^{\alpha_i}\prod_j q_j^{2\beta_j},\qquad p_i\equiv 1 \pmod 4,\quad q_j\equiv 3 \pmod 4,$

then

$|\Lambda_m|=4\prod_i(\alpha_i+1),\qquad \text{antipodal pairs}=\frac{|\Lambda_m|}{2}=2\prod_i(\alpha_i+1).$

If any prime \(q\equiv 3 \pmod 4\) appears to an odd power, then \(\Lambda_m\) is empty and the search skips \(m\) at once.

Why subset sums create the intended circle incidences

Take any even subset sum \(e\in E\). If the subset defining \(e\) does not contain \(i\), then \(e+v_i\in O\); if it does contain \(i\), then \(e-v_i\in O\). Since every \(v_i\) lies on \(x^2+y^2=m\), each point of \(O\) produced this way lies on the circle of radius \(\sqrt m\) centered at \(e\). So every circle centered at a point of \(E\) comes with \(d\) intended crossing points from \(O\).

The same relation can be read backwards: every odd subset sum \(o\in O\) differs from \(d\) even subset sums by vectors in \(\Lambda_m\), so each odd point lies on \(d\) circles of the family. The subset-sum construction therefore creates a bipartite incidence pattern isomorphic to the \(d\)-dimensional cube: toggling one chosen vector changes parity and moves by exactly one lattice vector of length \(\sqrt m\).

Injectivity inside the parity classes

The implementations require the map \(A\mapsto \sum_{i\in A}v_i\) to be injective separately on even subsets and on odd subsets. Equivalently, they reject any nontrivial relation

$\sum_{i\in A}v_i=\sum_{i\in B}v_i\quad \text{with}\quad |A|\equiv |B|\pmod 2,\ A\ne B.$

If such a collision existed inside \(E\), two circles that are supposed to be different would collapse to the same center. If it existed inside \(O\), two designated crossings would merge. This injectivity check is the first exact validation step performed after the directions have been chosen.

Translated circles and forbidden extra crossings

The deeper condition is that no point outside \(O\) may lie on two circles centered in \(E\). For an even center \(e\in E\) and a lattice vector \(u\in \Lambda_m\), consider the point \(z=e+u\), which certainly lies on the circle centered at \(e\). If \(z\in O\), then this is one of the intended crossings and it is allowed to belong to several circles. If \(z\notin O\), then the translated circle \(z+\Lambda_m\) must not hit a second point of \(E\). The exact condition checked by the code is

$z\notin O\ \Longrightarrow\ |(z+\Lambda_m)\cap E|<2.$

This is the decisive consonance test: every genuine multiple crossing of the chosen circles must come from the designated odd subset sums, and nowhere else.

The displacement set used for pruning

To reject hopeless branches early, the implementations precompute

$\Delta_m=\{a-b:\ a,b\in \Lambda_m,\ a\ne b\}.$

If two even centers lie on the same translated radius-\(\sqrt m\) circle, then their difference belongs to \(\Delta_m\). Differences of even subset sums are signed sums of an even number of chosen directions. Two-term differences correspond to intended odd crossings, so the first genuinely dangerous obstructions arise from four selected directions. During depth-first search, every newly created 4-tuple is tested through the sixteen sums

$\pm v_i\pm v_j\pm v_k\pm v_\ell,$

and the branch is pruned as soon as a nonzero value lands in \(\Delta_m\). This is not the whole proof of validity, but it is an extremely effective necessary filter before the full subset-sum test.

Worked Example: the checkpoint \(R(4)^2=5\)

For \(n=4\), the implementations need \(d=3\) because \(2^{3-1}=4\). Take \(m=5\), for which

$\Lambda_5=\{(\pm 2,\pm 1),(\pm 1,\pm 2)\}.$

Choose three representatives, for example

$v_1=(2,1),\qquad v_2=(2,-1),\qquad v_3=(1,2).$

Then the even subset sums are

$E=\{(0,0),(4,0),(3,3),(3,1)\},$

and the odd subset sums are

$O=\{(2,1),(2,-1),(1,2),(5,2)\}.$

So we obtain four circles of radius \(\sqrt 5\), centered at the points of \(E\). The circle centered at \((0,0)\) passes through \((2,1)\), \((2,-1)\), and \((1,2)\); the circle centered at \((4,0)\) passes through \((2,1)\), \((2,-1)\), and \((5,2)\); and similarly for the other two even centers. The odd points are exactly the intended shared crossings, and the full validation confirms that no other point lies on two of these four circles. That is why the checkpoint value is \(R(4)^2=5\).

How the Code Works

Arithmetic filters before the search

The C++, Python, and Java implementations first convert \(n\) into the required dimension \(d\), with the trivial shortcut \(R(n)^2=1\) for \(n\le 2\). They then scan \(m=1,2,3,\dots\). For each \(m\), they use the prime-factorization formula above to count antipodal pairs quickly, and discard \(m\) immediately if there are fewer than \(d\) available directions.

Choosing representatives and pruning the DFS

When \(m\) survives the arithmetic filter, the implementations enumerate all lattice points on \(x^2+y^2=m\), collapse them into antipodal pairs, and keep one canonical representative from each pair. A depth-first search then tries all \(d\)-element choices of those representatives. The precomputed displacement set \(\Delta_m\) is used at every step: whenever a new 4-tuple already creates a forbidden signed sum, the branch is abandoned before any expensive subset-sum work is done.

The three languages use the same mathematical search. The C++ implementation additionally parallelizes the top-level DFS branches over the choice of the first representative, while the Python and Java implementations run the same search serially.

Full candidate verification and termination

Once \(d\) directions have been selected, the implementations generate all \(2^d\) subset sums, split them into \(E\) and \(O\), and test injectivity inside each parity class. If that passes, they run the translated-circle condition \(z\notin O \Rightarrow |(z+\Lambda_m)\cap E|<2\). The first \(m\) that passes every test is returned, so by construction it is the minimal value \(R(n)^2\).

The built-in checkpoints confirm the first nontrivial cases \(R(2)^2=1\) and \(R(4)^2=5\); the C++ version also checks monotonicity for small \(n\).

Complexity Analysis

The outer loop over \(m\) is open-ended in theory, because the algorithm stops only when it reaches the first feasible squared radius. For one fixed \(m\), the trial-division factorization and the enumeration of lattice points both cost \(O(\sqrt m)\) in the current implementations.

Let \(L=|\Lambda_m|\) and \(u=L/2\). Building the displacement set \(\Delta_m\) costs \(O(L^2)\) time and memory. The search over direction choices is combinatorial in the worst case, up to \(O\!\left(\binom{u}{d}\right)\) branches, although the 4-vector pruning removes most of them in practice. For a complete candidate, generating all subset sums costs \(O(d\,2^d)\), while the translated-circle verification costs \(O(2^{d-1}L^2)\).

For the actual target \(n=500\), the dimension is \(d=10\), so each parity class has \(512\) points. The exponential part is therefore tied to a very small dimension; the practical difficulty is finding a good \(m\) and pruning the combinatorial search aggressively enough.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=983
2. Fermat's theorem on sums of two squares: Wikipedia - Fermat's theorem on sums of two squares
3. Lattice point: Wikipedia - Lattice point
4. Hypercube graph: Wikipedia - Hypercube graph
5. Backtracking: Wikipedia - Backtracking