Detailed mathematical approach

Problem Summary

The spiral starts with \(1\) at the center and writes the positive integers in a clockwise square pattern. For an odd side length \(N\), the goal is to compute the sum of the entries on the two diagonals of the resulting \(N \times N\) spiral without constructing the entire grid.

In the \(5 \times 5\) case, the diagonal entries are \(1,3,5,7,9,13,17,21,25\), so the total is \(101\). The same idea works for every positive odd \(N\), including the target size \(1001\).

Mathematical Approach

The key observation is that when the spiral grows from one odd square size to the next, the diagonals gain only four new values: the four corners of the new outer ring. Every other value in that ring lies off both diagonals, so the full matrix is unnecessary.

Concentric Square Rings

View the spiral as a sequence of concentric square layers. Layer \(0\) is the center alone. Layer \(k\) has side length \(2k+1\), so moving from layer \(k-1\) to layer \(k\) means extending the spiral from size \(2k-1\) to size \(2k+1\).

If the diagonal sum of the inner spiral is already known, the only new diagonal values are the four corners of the surrounding ring. This reduces the problem to finding those four corner values explicitly.

Corner Values of One Ring

Let \(s\) be an odd side length with \(s \ge 3\). The top-right corner of the outer ring is always \(s^2\), because the numbers increase until the ring closes there. Consecutive corners differ by exactly \(s-1\), which is the number of steps along one side of the square.

Therefore the four corners are

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

Equivalently, for \(j=0,1,2,3\), the corners are \(s^2-j(s-1)\). Their sum is

$ L(s)=\sum_{j=0}^{3}\bigl(s^2-j(s-1)\bigr)=4s^2-6(s-1)=4s^2-6s+6. $

This is the exact ring contribution accumulated by the implementations.

A Recurrence for the Diagonal Sum

Let \(D(s)\) denote the diagonal sum for the spiral of odd side length \(s\). The center gives the base case \(D(1)=1\). Every larger odd square is obtained by adding one outer ring, so for odd \(s \ge 3\),

$ D(s)=D(s-2)+4s^2-6s+6. $

The loop invariant in the code is precisely this statement: after processing side length \(s\), the running total equals \(D(s)\). The center is counted once in the base case and never appears again, so there is no double counting issue.

Summing the Recurrence

Write \(N=2m+1\), where \(m=(N-1)/2\) is the number of outer rings beyond the center. Substituting \(s=2k+1\) into the ring contribution gives

$ L(2k+1)=16k^2+4k+4. $

Hence

$ D(N)=1+\sum_{k=1}^{m}(16k^2+4k+4). $

Using the standard formulas for \(\sum k\) and \(\sum k^2\), this becomes

$ D(N)=\frac{16m^3+30m^2+26m+3}{3} =\frac{4N^3+3N^2+8N-9}{6}. $

The implementations do not need the closed form, because the layer-by-layer loop is already tiny for \(N=1001\). Still, the closed form shows that the recurrence is exact and that the answer depends only on the odd side length.

Worked Example: Extending to \(7 \times 7\)

The \(5 \times 5\) spiral has diagonal sum \(101\). The next ring has side length \(s=7\), so its corners are

$ 7^2=49,\qquad 49-6=43,\qquad 49-12=37,\qquad 49-18=31. $

The new contribution is \(49+43+37+31=160\), so the \(7 \times 7\) diagonal sum is \(101+160=261\). This is exactly the second checkpoint used in the implementations.

How the Code Works

Validation and Known Checkpoints

The C++, Python, and Java implementations accept an optional odd size and default to \(1001\). They reject non-positive or even inputs because a centered spiral with a single middle cell exists only for odd side lengths.

Before producing the final result, the implementation can verify two known values: \(D(5)=101\) and \(D(7)=261\). These checkpoints confirm the corner formula and the loop boundaries.

Ring-by-Ring Accumulation

The computation begins with a running total of \(1\) for the center. It then iterates over odd side lengths \(3,5,7,\dots,N\). For each side length \(s\), it adds \(4s^2-6(s-1)\), which is the sum of the four corners of the new outer ring.

No spiral array is allocated, and no individual interior cells are generated. The implementation stores only the current side length and the running total, so it mirrors the recurrence directly in constant space.

Complexity Analysis

The loop visits each odd side length once, so the number of iterations is \((N-1)/2\). That gives \(O(N)\) time and \(O(1)\) space.

A literal construction of the whole spiral would require \(O(N^2)\) work and \(O(N^2)\) storage. The implemented method is faster and simpler because it uses only the corner arithmetic. A closed-form evaluation would be \(O(1)\), but for this problem size the iterative method is already effectively instantaneous.

Footnotes and References

1. Problem page: Project Euler Problem 28
2. Square spiral background: Wikipedia - Ulam spiral
3. Square numbers: Wikipedia - Square number
4. Sum of squares: Wikipedia - Square pyramidal number