Project Euler 28 Problem 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”, which form the two principal diagonals, produce a simple series: (3, 5, 7, 9), (13, 17, 21, 25), (31, 37, 43, 49), …

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


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

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

Improved approach: Closed form summation

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

[latex s="1"] 1+\sum\limits_{i=1}^{s} 4(2i+1)^2-6(2i+1)+6, s=\frac{n-1}{2} [/latex]

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

This simplifies further:

[latex s="1"] 1+\sum\limits_{i=1}^{s} 16i^2+4i+4 [/latex]

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

[latex s="1"] 1+16\cdot\sum\limits_{i=1}^{s}i^2 + 4\cdot\sum\limits_{i=1}^{s}i + \sum\limits_{i=1}^{s}4 [/latex]

[latex s="1"] \frac{16s(s + 1)(2s + 1)}{6} + \frac{4s(s + 1)}{2} + 4s + 1 [/latex]

[latex s="1"] \frac{16s^3 + 30s^2 + 26s +3}{3} [/latex]

Or, factored if you prefer:

[latex s="1"] (\frac{2s}{3}) (8s^2 + 15s + 13) + 1 [/latex]

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

s = \frac{5-1}{2} = 2,
\frac{16\cdot2^3 + 30\cdot2^2 + 26\cdot2 +3}{3}= 101

HackerRank version

The Hackerrank Project Euler 28 version of this problem runs 100,000 test cases and extends the size of the square from 1001 to any odd n, where 1 ≤ n ≤ 1018. So any iterative approach will exceed their time limit. This solution works perfectly.

Python 2.7 Source

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.