In this post, I will show a method for analyzing Problem 28 on Project Euler that goes beyond brute-forcing (even though that is an option).

If you’re not familiar with Project Euler, here is a description from its website:

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems.

After my answer was submitted I read through some of the solutions that have been posted. It seems that most of them are using brute-force to attack this problem, so I will show how I devised a more efficient method to solving it.

## The Problem

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

The first thing to notice is that you don’t have to actually construct the spiral in order to solve this problem. In an `nxn` spiral, the values of the four corners are as follows:

top-right: `n^2` top-left: `n^2 - n + 1` bottom-left: `n^2 - 2n + 2` bottom-right: `n^2 - 3n + 3`

Adding all that up yields `4n^2 -6n + 6`.

At this point you can loop through from 3 to 1001 (in increments of 2) and add up the results. Just make sure you add a 1 to the results for the base case. :)

## Further Generalization

Of course, we can take this generalization even further. The result for an `nxn` spiral can be expressed by a formula.

``````Sum(i = 1:500)[4(2*i + 1)^2 - 6(2i + 1) +6]
``````

The beginning reads “sum from i=1 to 500”… I’m not too sure how to type out sigma notations properly.

Converting the summation into closed form gives the formula we’re looking for.

``````(16n^3)/3 + (10n^2)/2 + 26n/3
``````

And here is the complete solution in Python.