Project Euler/28

Spiral Diagonals Sum Analysis

This page provides a mathematical analysis and algorithm to compute the sum of numbers on the diagonals of an $n\times n$ spiral grid, starting from 1 at the center and moving clockwise. The problem is to find the sum for a $1001\times 1001$ spiral, given that the sum for a $5\times 5$ spiral is 101.

Understanding the 5×5 Spiral

Consider the $5\times 5$ spiral provided as an example:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

The diagonals are:

• Main diagonal (top-left to bottom-right): 21, 7, 1, 3, 13.
• Anti-diagonal (top-right to bottom-left): 25, 9, 1, 5, 17.

The sum of these numbers is:

• Main diagonal: $21+7+1+3+13=45$
• Anti-diagonal: $25+9+1+5+17=57$

Total: $45+57=102$. Since the center (1) is counted twice, subtract it once: $102-1=101$, which matches the given sum.

Analyzing the Spiral Pattern

The spiral starts at 1 in the center and moves outward in layers, clockwise. For a $5\times 5$ grid:

• Layer 0: Center (1).
• Layer 1: $3\times 3$ grid (numbers 2 to 9).
• Layer 2: $5\times 5$ grid (numbers 10 to 25).

For an $n\times n$ grid where $n$ is odd ($n=2k+1$), the number of layers $k$ is:

• $n=5$, so $5=2k+1$, $k=2$.
• $n=1001$, so $1001=2k+1$, $k=500$.

Each layer $m$ forms a square of side length $2m+1$. The numbers on the diagonals are the corners of these layers.

Number of Elements per Layer

• Layer 0: 1 number.
• Layer 1: $3\times 3=9$ numbers, minus the center, so 8 numbers.
• Layer 2: $5\times 5=25$ numbers, minus the inner $3\times 3$ (9 numbers), so $25-9=16$ numbers.

For layer $m$, the side length is $2m+1$, so the grid has $(2m+1)^{2}$ numbers. The inner grid (layer $m-1$) has $(2m-1)^{2}$ numbers. The numbers in layer $m$:

$(2m+1)^{2}-(2m-1)^{2}=(4m^{2}+4m+1)-(4m^{2}-4m+1)=8m$

Total numbers up to layer $m$:

$1+\sum _{i=1}^{m}8i=1+8\cdot {\frac {m(m+1)}{2}}=1+4m(m+1)$

The last number in layer $m$ (top-right corner) is $(2m+1)^{2}$.

Corner Numbers on Diagonals

For layer $m$, the corners are:

• Top-right: $(2m+1)^{2}$
• Top-left: $(2m+1)^{2}-2m$
• Bottom-left: $(2m+1)^{2}-4m$
• Bottom-right: $(2m+1)^{2}-6m$

Verify for $5\times 5$ ($k=2$):

• Layer 1 ($m=1$):
  • Top-right: $(2\times 1+1)^{2}=9$
  • Top-left: $9-2\times 1=7$
  • Bottom-left: $9-4\times 1=5$
  • Bottom-right: $9-6\times 1=3$
• Layer 2 ($m=2$):
  • Top-right: $(2\times 2+1)^{2}=25$
  • Top-left: $25-2\times 2=21$
  • Bottom-left: $25-4\times 2=17$
  • Bottom-right: $25-6\times 2=13$

These match the grid.

Sum of Diagonals for 1001×1001 Spiral

For $n=1001$, $k=500$. Sum the corners from layer 1 to 500, plus the center (1).

Sum of corners in layer $m$:

$4(2m+1)^{2}-(2m+4m+6m)=16m^{2}+4m+4$

Total sum from layer 1 to 500:

$\sum _{m=1}^{500}(16m^{2}+4m+4)=16\sum _{m=1}^{500}m^{2}+4\sum _{m=1}^{500}m+4\sum _{m=1}^{500}1$

Using:

• $\sum _{m=1}^{n}m^{2}={\frac {n(n+1)(2n+1)}{6}}$
• $\sum _{m=1}^{n}m={\frac {n(n+1)}{2}}$
• $\sum _{m=1}^{n}1=n$

For $n=500$:

• $\sum _{m=1}^{500}m^{2}={\frac {500\cdot 501\cdot 1001}{6}}=41791750$
• $\sum _{m=1}^{500}m={\frac {500\cdot 501}{2}}=125250$
• $\sum _{m=1}^{500}1=500$

Total:

$16\cdot 41791750+4\cdot 125250+4\cdot 500=669171000$

Add the center: $669171000+1={\mbox{the final answer}}$.

Algorithm to Compute the Sum

Below is a pseudocode algorithm to compute the sum efficiently:

function sumDiagonals(n):
    k = (n - 1) / 2
    sum = 1  # Center
    for m from 1 to k:
        sum += 16 * m * m + 4 * m + 4
    return sum

n = 1001
result = sumDiagonals(n)
print(result)

This algorithm avoids generating the entire spiral, focusing on the diagonal numbers.

Final Answer

The sum of the numbers on the diagonals of a $1001\times 1001$ spiral is