Robert Eisele
Engineer, Systems Architect and DBA

Project Euler 28: 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?

Solution

This problem could be solved by re-producing the generation rule and just sum up the diagonals within a loop. However, there is a better way. We have 4 diagonals, starting in the middle of the matrix and for each diagonal, we can find a sequence:

\[\begin{array}{rll}a_n &= (9, 25, 49, 81, 121, ...) &= 4n^2 + 4n + 1\\b_n &= (5, 17, 37, 65, 101, ...) &= 4n^2 + 1\\c_n &= (3, 13, 31, 57, 91, ...) &= 4n^2 - 2n+1\\d_n &= (7, 21,43, 73, 111, ...) &= 4n^2 + 2n + 1\end{array}\]

We can now add all these diagonal sequences plus 1 for the middle element, integrate over it and form a series:

\[\begin{array}{rl}s_n &= 1+\sum\limits_{i=1}^n (a_i + b_i + c_i + d_i)\\&= 1+\sum\limits_{i=1}^n (16i^2 + 4i + 4)\\&= 1+16\sum\limits_{i=1}^ni^2 + 4\sum\limits_{i=1}^ni + \sum\limits_{i=1}^n4\\&= 1+\frac{8}{3}n(n+1)(2n+1) + 2n(n+1) + 4n\\&= 1+\frac{2}{3}n(8n^2+15n+13)\end{array}\]

The remaining question is, what exactly is n. Since we split every diagonal into two parts, forming 4 quadrants, we can't go the full 1001 elements in either direction. We must remove the middle element (and require an odd number) and divide by two since we need only half of the diagonal. For our example:

\[n := \frac{1001 - 1}{2}\]

The final solution can then be implemented as:

function solution(n) {
    n = (n - 1) / 2;
    return 2 * n * (8 * n * n + 15 * n + 13) / 3 + 1;
}
solution(5); // 101

Or as there are lots of things canceling out, we can simplify and pack together with Horner method:

function solution(n) {
    return (n * (n * (4 * n + 3) + 8) - 9) / 6;
}
solution(1001);

« Back to problem overview