Detailed mathematical approach

Problem Summary

Start with 1 at the center of a square spiral and wrap the positive integers around it in layers of odd side length \(1,3,5,\dots\). The diagonals isolate a very small subset of those values, and the task is to find the first side length for which the proportion of primes on the two diagonals drops below a chosen threshold, usually \(10\%\).

The key simplification is that when the spiral grows from side length \(s-2\) to side length \(s\), only four new diagonal values appear. So the problem is not about storing the whole spiral; it is about generating those corner values, testing the relevant ones for primality, and maintaining a running ratio.

Mathematical Approach

Let layer \(n \ge 0\) denote the square whose side length is \(s_n = 2n+1\). Layer \(0\) is just the center value \(1\). Every later layer adds one square ring around the previous one, and the only new diagonal entries are the four corners of that ring.

Geometry of the outer ring

The largest value in layer \(n\) is the square of the side length:

$s_n^2 = (2n+1)^2.$

Along the outer ring, the distance between consecutive corners is exactly

$s_n - 1 = 2n.$

Therefore the four new corner values are

$q_{n,k} = (2n+1)^2 - 2kn \qquad (k=0,1,2,3),$

or, in terms of the side length \(s\),

$s^2,\quad s^2-(s-1),\quad s^2-2(s-1),\quad s^2-3(s-1).$

These are exactly the new diagonal values, because every earlier diagonal entry already lies inside the smaller \((s-2)\times(s-2)\) square.

Diagonal-count invariant

A square of odd side length \(s\) has two diagonals of length \(s\), but the center belongs to both and must be counted once. After layer \(n\), the total number of diagonal entries is therefore

$D_n = 2s_n - 1 = 4n + 1.$

This gives the recurrence

$D_0 = 1,\qquad D_n = D_{n-1} + 4 \quad (n \ge 1),$

which is the combinatorial reason the implementations increase the diagonal count by 4 on every iteration.

Prime-count recurrence

Let \(c_n\) be the number of prime corners added at layer \(n\), and let \(P_n\) be the cumulative number of diagonal primes after that layer. Then

$P_0 = 0,\qquad P_n = P_{n-1} + c_n.$

One corner simplifies immediately: \(q_{n,0} = (2n+1)^2\) is a perfect square greater than 1 for every \(n \ge 1\), so it is never prime. Hence

$c_n \in \{0,1,2,3\},$

and each new layer requires only three genuine primality tests.

Worked example and the strict threshold

The first layers make the recurrence concrete.

For \(n=1\) we have \(s=3\), step \(=2\), and corners

$9,\ 7,\ 5,\ 3.$

Three of them are prime, so \(P_1 = 3\) and \(D_1 = 5\). The diagonal prime ratio is \(3/5 = 60\%\).

For \(n=2\) we have \(s=5\), step \(=4\), and new corners

$25,\ 21,\ 17,\ 13.$

Only \(17\) and \(13\) are prime, so \(c_2 = 2\), \(P_2 = 5\), and \(D_2 = 9\). The cumulative ratio becomes \(5/9 \approx 55.56\%\).

This also explains the checkpoint thresholds in the implementations. With threshold \(62\%\), side length \(3\) already qualifies because \(3/5 < 62\%\). With threshold \(60\%\), side length \(3\) does not qualify, because the condition is strictly “below”, not “below or equal”, so the search continues until side length \(5\).

Stopping rule without floating point

For a threshold \(T\) measured in percent, the target condition is

$\frac{P_n}{D_n} < \frac{T}{100}.$

Because all quantities are integers, this is equivalent to

$100P_n < T D_n.$

The algorithm uses this cross-multiplied form directly. It preserves the strict inequality exactly and avoids any rounding issues from floating-point arithmetic.

How the Code Works

The C++, Python, and Java implementations all follow the same layer-by-layer scan. They begin with only the center present, so the diagonal count is 1 and the prime count is 0. From there they visit the odd side lengths \(3,5,7,\dots\) in increasing order.

Generating each new ring

At each iteration the implementation computes the current side length, its square, and the corner step. From those values it forms the three non-square corners \(s^2-(s-1)\), \(s^2-2(s-1)\), and \(s^2-3(s-1)\). The corner \(s^2\) is not tested, because its compositeness is known in advance for every nontrivial layer.

Primality testing

Each version uses straightforward trial division. Numbers below 2 are rejected immediately, even numbers are handled as a special case, and then only odd divisors are tried. The loop stops once the divisor would exceed \(\sqrt{n}\); in the fixed-width languages this is written safely as \(p \le n/p\), so no floating-point square root is needed.

Maintaining the invariants

After the three primality tests, the implementation adds 4 to the diagonal count and adds the number of newly found primes to the cumulative prime count. It then checks the exact inequality \(100P < TD\). As soon as that condition becomes true, the current odd side length is returned.

The same code path also supports alternative percentage thresholds. Two built-in checkpoints verify the logic: threshold \(62\%\) should stop at side length \(3\), and threshold \(60\%\) should stop at side length \(5\). Those cases confirm both the corner formulas and the strict comparison rule.

Complexity Analysis

If the search stops after layer \(L\), then the largest tested corner is on the order of \((2L+1)^2\). Trial division on a number of that size costs \(O(L)\) odd divisor checks in the worst case. Since each layer performs three primality tests and only \(O(1)\) additional arithmetic, the total running time is

$O\!\left(\sum_{\ell=1}^{L} \ell\right)=O(L^2).$

Because the returned side length is \(s = 2L+1\), this is equivalently \(O(s^2)\) in terms of the final answer. The memory usage is \(O(1)\): the implementations keep only the current layer data, the two running counts, and a few temporary integers.

Footnotes and References

1. Project Euler problem page: Spiral primes
2. Background on the diagonal pattern: Ulam spiral
3. General reference on primality tests: Primality test
4. The trial-division method used here: Trial division