Project Euler Problem 28 Solution: Number spiral diagonals

Project Euler Problem 28 Statement

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 both diagonals is 101.

What is the sum of both diagonals in a 1001 by 1001 spiral formed in the same way?

Solution

Basic approach: Using a loop to count corners

The corners of each sub-square (shown above in red) form the two principal diagonals and produce a simple series: (3, 5, 7, 9), (13, 17, 21, 25), (31, 37, 43, 49), …

This can be quantified as the quad $(n^2-3n+3, n^2-2n+2, n^2-n+1, n^2)$ and summing them together yields $4n^2-6n+6$; the sum of the corners for each odd-size square:

3 + 5 + 7 + 9 = 24, 13 + 17 + 21 + 25 = 76, 31 + 37 + 43 + 49 = 160, …

sum, size = 1, 1001
for n in range(3, size+1, 2):
    sum+= 4*n*n - 6*n + 6
print("Answer to PE28 =", sum)

This simple, O(n), iterative approach will not solve the larger sizes specified in the HackerRank version of this problem; a better, O(1), solution must be found.

Improved approach: Closed form summation

If we rewrite the for loop as a summation we will have:

$$1+\sum\limits_{i=1}^{s} 4(2i+1)^2-6(2i+1)+6, s=\frac{n-1}{2}$$

$2i+1$ is every odd number, starting with $3$, until we reach the size of the square. This will take $\frac{(n-1)}{2}$ iterations.

This simplifies further:

$$1+\sum\limits_{i=1}^{s} 16i^2+4i+4$$

Finally, we can express this summation as a closed form equation by using the algebra of summation notation (Wikipedia or Project Euler Problem 6):

$$1+16\cdot\sum\limits_{i=1}^{s}i^2 + 4\cdot\sum\limits_{i=1}^{s}i + \sum\limits_{i=1}^{s}4$$ $$\frac{16s(s + 1)(2s + 1)}{6} + \frac{4s(s + 1)}{2} + 4s + 1$$ $$\frac{16s^3 + 30s^2 + 26s +3}{3}$$

Or, factored if you prefer:

$$(\frac{2s}{3}) (8s^2 + 15s + 13) + 1$$

Let’s test this equation with the example in the problem statement, $n = 5$. Remember, $n\ge 3$ and odd.

$$s = \frac{5-1}{2} = 2, \frac{s\cdot(32+30+13)}{3}+1= 101$$

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 28

HackerRank Project Euler 28 requires us to run 10,000 test cases with an odd N, 1 ≤ N < 10¹⁸. Don’t forget to mod the result by 10⁹ + 7.

Python Source Code

for _ in range(int(input())):
    n = (int(input()) -1 ) // 2
    print((16*n**3 + 30*n**2 + 26*n + 3) // 3 % 1000000007)

Last Word

Reference: The On-Line Encyclopedia of Integer Sequences (OEIS) A114254: Sum of all terms on the two principal diagonals of a 2n+1 X 2n+1 square spiral.