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 sum over these diagonal sequences plus 1 for the middle element to get a closed form solution:
\[\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);