Problem 028

Project Euler

Number spiral diagonals

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 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?


Like Problem 1 and Problem 6, this problem can be solve using summation when examine further. Let look at the 3×3 spiral, we can see that the sum is 1+3+5+7+9, or we can rewrite this as 1+2*(3+9), where 3 and 9 is the minimum and maximum value of the square ring with 3, respectively. For 5×5 spiral, we can write the sum as 1+2*[(3+9) + (13+25)]. If you look further, you will see a pattern such that for ixi spiral, the sum is 1+2(3+9+13+25+ \ldots +i^2-3(i-1)+i^2). To represent this as a summation, the summation need to adjust to only include odd number by having i = 2j+1 and using new upper [(1001 – 1)/2 = 500] and lower [(3-1) / 2 = 1] limits:

1+ 2 \sum_{j=1}^{500} (2j+1)^2+ (2j+1)^2 - 3(2j+1-1)

by separating j^2, j and constant terms and pull out the multipliers. We can use the summation formula to obtain the correct answers.

Advertisements