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 = 669171001 \).

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