(16 votes, average: 5.00 out of 5)

## Project Euler 28: Find the sum of both diagonals in a square spiral

#### Project Euler 28 Problem Description

Project Euler 28: 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?

#### Analysis

The hackerrank Project Euler 28 version of this problem 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. A closed form of the summation will have to be determined.

### Using a loop to count corners

Looking at 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, d, size = 1, 1, 1001

for n in range(2, size, 2):
sum += 4*d + 10*n
d += n*4;

print "Answer to PE28 = ",sum


### Improved approach: Closed form summation

These sums of corners form the sum of the diagonals, after adding 1 for the center, for every i by i spiral where 3 ≤ in, for odd n and can be expressed as:

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

and simplified to:

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

Finally, we can further simplify this summation into 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 (odd side length ≥ 3) = 5: $s = \frac{5-1}{2} = 2$

$\frac{16\cdot2^3 + 30\cdot2^2 + 26\cdot2 +3}{3}= 101$

HackerRank Project Euler 28 runs up to 10,000 trials with odd values for N up to 1018,
requiring the need for the closed form summation to successfully pass the test cases in under a second.

This program and method
solves all test cases for
Project Euler 28 on HackerRank

#### Project Euler 28 Solution

Runs < 0.001 seconds in Python 2.7.
Use this link to get the Project Euler 28 Solution Python 2.7 source.

#### Afterthoughts

Project Euler 28 Solution last updated