🔒 Problem

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?

🔐 Key Idea

finding the pattern for the series

🔑 Solution

🧭 Initial idea

$O(n)$ complexity.

The variable i iterates from 1 indicating all elements in the spiral. Since every 1 element is skipped in the spiral of size 3, and 3 elements in size 5, and so on. So with i += size - 1, we skip the i up to the next diagonal element.

sum = 1
size = 3

i = 1
k = 1001

while size <= k:
    for n in range(4):  # for 4 edge numbers in each square
        i += size - 1
        sum += i
    size += 2

print(sum)

669171001

🚀 1-loop method

$O(n)$ complexity.

Since the numbers being added are in 4 edges of the $n$ by $n$ spiral, we can derive the following formula to calculate the sum of diagonal elements from the size $n$. We can find that the right top diagonal is $n^2$, and the other elements are $n^2 - (n - 1)$, $n^2 - 2(n - 1)$, $n^2 - 3(n - 1)$.

$ S(n) = (n^2) + (n^2 - (n - 1)) + (n^2 - 2(n - 1)) + (n^2 - 3(n - 1)) $

Which can be expanded to the following.

$ S(n) = 4 n^2 - 6 n + 6 $

Noting this formula works for $ n > 1 $, we can easily convert this into a code.

sum = 1
k = 1001  # size limit

for i in range(3, k + 1, 2):
    sum += 4 * i**2 - 6 * i + 6

print(sum)

669171001