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?
The first \(k\) layers of the spiral produce a \(2k + 1\) by \(2k + 1\) square. The \(k\)-th layer has four values on the diagonal: \((2k+1)^2\) in the upper right, \((2k+1)^2 - 2k\) in the upper left, \((2k+1)^2 - 4k\) in the lower left, and \((2k+1)^2 - 6k\) in the lower right. The sum of these values is \(4(2k+1)^2 - 12k\). If \(n\) is the side length of the final spiral, then there will be a total of \(\lfloor n / 2 \rfloor = (n-1)/2 \) layers wrapped around the central \(1\). Therefore, we need to solve:
\[\begin{aligned} &1 + \sum_{k = 1}^{(n-1)/2} (4(2k+1)^2 - 12k) \\ &= 1 + \sum_{k = 1}^{(n-1)/2} (16k^2 + 4k + 4) \\ &= 1 + 16 \sum_{k = 1}^{(n-1)/2} k^2 + 4 \sum_{k = 1}^{(n-1)/2} k + \sum_{k = 1}^{(n-1)/2} 4 \end{aligned}\]The first sum is a square pyramidal number, which I cover in my writeup of problem 6. The second is a triangular number, which I cover in my writeup of problem 1. The third is just repeated addition of a constant, or in other words, multiplication. The equation simplifies to
\[\begin{aligned} &1 + 16 \frac{\frac{n-1}2 (\frac{n-1}2 + 1)(2\frac{n-1}2 +1)}6 + 4 \frac{\frac{n-1}2 (\frac{n-1}2 +1)}2 + 4\frac{n-1}2 \\ &= 1 + 4 \frac{(n-1)(n+1)n}{6} + \frac{(n-1)(n+1)}{2} + 2n - 2 \\ &= \frac 23 (n^3 - n) + \frac 12 (n^2 - 1) + 2n - 1 \\ &= \frac 23 n^3 + \frac 12 n^2 + \frac 43 n - \frac 32. \end{aligned}\]Once again, we could have gotten this by brute force because the cap is pretty low, but formulating a more efficient solution is far more instructive.
p28 = lambda n=1001: 2*(n**3 - n)//3 + (n**2 - 1)//2 + 2*n - 1