## 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 ≤ 10^{18}, 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 (* n^{2} – 3n + 3, n^{2} – 2n + 2, n^{2} – n + 1, n^{2}*) and summing them together yields

*; the sum of the corners for each odd-length square:*

**4n**^{2}– 6n + 63 + 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 ≤ *i* ≤ *n*, for **odd** *n* and can be expressed as:

and simplified to:

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):

Or, factored if you prefer:

Let’s test this equation with the example in the problem statement, *n* (odd side length ≥ 3) = 5:

HackerRank Project Euler 28 runs up to 10,000 trials with odd values for N up to 10^{18},

requiring the need for the closed form summation to successfully pass the test cases in under a second.

#### 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

- 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.
- See also, Project Euler 58 Solution:

*Project Euler 28 Solution last updated*

## Discussion

## No comments yet.