#28 - Number spiral diagonals

in Project Euler on 5%

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?

Let’s add another step and make it a 7 by 7 spiral:

43 44 45 46 47 48 49
42 21 22 23 24 25 26
41 20  7  8  9 10 27
40 19  6  1  2 11 28
39 18  5  4  3 12 29
38 17 16 15 14 13 30
37 36 35 34 33 32 31

Note that the diagonal heading northeast has $1,9,25,49,\dots$. These are the squares of the odd numbers i.e. $1^2,3^2,5^2,7^2,\dots$. We can get the other 3 numbers at the other corners by subtracting the side length minus one once, twice, and three times. For example, $25$ is at the corner of the 5 by 5 circle. If we subtract $5-1=4$ from $25$, we get $21$, the number on the northwest diagonal. Subtracting two times and three times gets us $17$ and $13$ respectively.

So our method is loop through each odd number until 1001, and add that number squared, as well as the other 3 numbers described in the preceding paragraph. We will start from 3, as to not triple count the 1 in the center.

# file: "problem028.py"
spiralLim = 1001
s = 0
for n in range(3, spiralLim + 1, 2):
    s += n ** 2
    # Add the other three numbers:
    s += n ** 2 - (n - 1)
    s += n ** 2 - 2 * (n - 1)
    s += n ** 2 - 3 * (n - 1)
   
# Add 1 from center
s += 1

print(s)

Running the above code results in,

669171001
0.00024259998463094234 seconds.

Therefore, 669171001 is our final sum.

Bonus

This is one of the few problems that can be done by hand, although it’s a little messy. Let the spiral loop we are on by denoted $n$. Recall that for each loop in the spiral, we add $n^2$, and the three numbers that have been subtracted by $n-1$ once, twice, and three times. Therefore, in each loop, the sum is \[\begin{align*} S_n &= n^2+n^2-(n-1)+n^2-2(n-1)+n^2-3(n-1) \\ &= 4n^2-6(n-1) \\ &= 4n^2-6n+6 \end{align*}\]

So, in actuality, instead of the 4 lines we had in the for loop, we could have had one line where add s by this sum. However, there are more steps we could do.

An odd number $n$ can be written in the form $2k+1$. In our problem, $1\leq k\leq 500$. Thus, we can write a summation and evaluate it as follows: \[\begin{aligned} S &= \sum_{k=1}^{500}S_{2k+1} +1 \\ &= \sum_{k=1}^{500}\left( 4(2k+1)^2 - 6(2k+1) + 6 \right) +1 \\ &= \sum_{k=1}^{500}\left( 4\left( 4k^2+4k+1 \right) - 12k - 6 + 6 \right) +1 \\ &= \sum_{k=1}^{500}\left( 16k^2+16k+4-12k \right) +1 \\ &= \sum_{k=1}^{500}\left( 16k^2+4k+4 \right) +1 \\ &= 16\sum_{k=1}^{500}k^2+4\sum_{k=1}^{500}k+\sum_{k=1}^{500}4 +1 \\ &= 16\left( \frac{500(500+1)(2(500)+1)}{6} \right)+4\left( \frac{500(500+1)}{2} \right) + 4(500) +1 \\ &= 16(41\,791\,750)+4(125\,250) + 2000 +1 \\ &= \boxed{669\,171\,001} \end{aligned}\]