Project Euler Problem 28
Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows: 21 22
Solution
Answer: 669171001
For an $n \times n$ spiral (with $n$ odd), each square “layer” contributes four corner values.
For a layer with side length $s$:
- Top-right corner: $s^2$
- Top-left corner: $s^2-(s-1)$
- Bottom-left corner: $s^2-2(s-1)$
- Bottom-right corner: $s^2-3(s-1)$
So the sum of the four corners is:
$$4s^2 - 6(s-1)$$
The spiral starts at $1$, then layers have side lengths:
$$3,5,7,\dots,1001$$
Thus the total diagonal sum is:
$$1 + \sum_{s=3,5,\dots,1001} \left(4s^2 - 6(s-1)\right)$$
We can compute this directly.
Python code:
total = 1
for s in range(3, 1002, 2):
total += 4 * s * s - 6 * (s - 1)
print(total)
Tracing small cases:
-
$1 \times 1$: sum $=1$
-
$5 \times 5$:
-
$3 \times 3$ layer corners: $3,5,7,9$ → sum $24$
-
$5 \times 5$ layer corners: $13,17,21,25$ → sum $76$
-
Total: $1+24+76=101$, matching the example.
Running the same logic for $1001 \times 1001$ gives:
Answer: 669171001