Project Euler Solution 28: Number spiral diagonals

Code & Zahlen

In Project Euler Problem 28: Number spiral diagonals one has to sum up the diagonals of a number spiral.

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?

Here one could generate this spiral in memory and then go through the diagonals. But I found an easier way to do it. One should just write out the numbers that one has to add here:

1, 3, 5, 7, 9, 13, 17, 21, 25, 31, …

There is a pattern readily visible, also from the above picture of the spiral. The distance between four consecutive numbers is the same, and then the distance increases by 2. This means that one can group these numbers by winding around the center:

  1. 1
  2. 3, 5, 7, 9
  3. 13, 17, 21, 25
  4. 31, …

Using that we can simply go through the 500 windings and then through the four numbers from the diagonal. We increase the number by twice the loop number and then add it to the accumulator.

def solution() -> int:
    accumulator = 1
    number = 1
    for loop in range(1, 501):
        for side in range(4):
            number += 2 * loop
            accumulator += number
    return accumulator

This runs in just 205 µs and produces the correct answer with O(N) time and O(1) memory, given this N×N spiral. If one would have represented it in memory, the memory needed would by O(N²) and the time would be O(N²) as well.