 ## Project Euler & HackerRank Problem 28 Solution

##### Number spiral diagonals
by {BetaProjects} | MAY 17, 2009 | Project Euler & HackerRank

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


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: 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: Finally, we can express this summation as 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 = 5. Remember, n ≥ 3 and odd.  #### HackerRank version

HackerRank requires us to run 10,000 test cases with an odd N, 1 ≤ N < 1018. Don’t forget to mod the result by 1000000007.

### Python Source Code Use this link to download the Project Euler Problem 28: Number spiral diagonals Python source. Run Project Euler Problem 28 using Python on repl.it

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