Another Project Euler problem has sparked my attention. This one isn’t particularly difficult (much less than the last one I posted about – despite being in the same category of difficulty), but it’s an interesting problem with a nice solution. Most people probably don’t approach this in the way I did, but for once I think my solution is cleaner than the others that are posted on the forum. The problem statement can be found here: Problem 28 Statement.

Like last time, I’m going to proceed under the assumption that you’ve read through the problem statement. And remember, this post contains a full solution, so be sure to try the problem before continuing if you want to solve it on your own.

I posted this solution on the Project Euler forum for problem 28, but you can’t see it unless you’ve given a solution.

The southwest diagonal numbers are always 1 more than the square of an even number, say $n^2+1$. Then, it is pretty easy to define the rest of the diagonals in terms of $n$. The northeast diagonal is $(n+1)^2=n^2+2n+1$, the northwest is $n^2+n+1$, and the southeast is $n^2-n+1$. So, for an $N$ by $N$ grid, the sum is:

$$1+\sum_{n \text{ even}}^{N-1}\left(n^2+1+n^2+2n+1+n^2+n+1+n^2-n+1\right) = 1+\sum_{n \text{ even}}^{N-1}\left(4n^2+2n+4\right)$$

For a 1001 by 1001 grid, this evaluates to

$$1+\sum_{n \text{ even}}^{1000}\left(4n^2+2n+4\right) = 669171001$$

And the python implementation is trivial with the sum function.

def problem_28():
    return 1 + sum(4*n*n+2*n+4 for n in range(2,1001,2))

We can easily get a generalized closed-form solution to this problem by using the formulas for the sum of the first $n$ natural numbers and the sum of the squares of the first $n$ natural numbers.

$$1+2+3+\cdots+n-1+n = \sum_{k=1}^{n}k = \frac{n(n+1)}{2}$$

$$1^2+2^2+3^2+\cdots+(n-1)^2+n^2 = \sum_{k=1}^{n}k^2 = \frac{n(n+1)(2n+1)}{6}$$

These formulas can be modified to yield the sums of the first $n$ even numbers and their squares:

$$2+4+6+\cdots+2(n-1)+2n = \sum_{k\in\mathbb{N} \text{ even}}^{n}k = n(n+1)$$

$$2^2+4^2+6^2+\cdots+(2n-2)^2+(2n)^2 = \sum_{k\in\mathbb{N} \text{ even}}^{n}k^2 = \frac{2n(n+1)(2n+1)}{3}$$

The second of those two formulas is a bit harder to obtain, but the trick is realizing that you can factor $2^2=4$ out of every term of the sum, and modifying the formula accordingly. With these, we can define $m=N-1$ to clean up the calculations, since we are summing all the even numbers less than or equal to $N-1$. $N$ itself will always be odd due to the nature of the puzzle, so $m$ will always be even. Using the above formulas, a closed form solution to this puzzle with an $N$ by $N$ grid of numbers is:

$$\frac{2m(m+1)(m+2)}{3}+\frac{m}{2}(m+2)+2m+1$$

Plug in $m = N – 1 = 1001 – 1 = 1000$ to get the correct answer (669171001). Here’s the python implementation for this part:

def problem_28_closedform():
    N = 1001
    m = N-1
    return 2*m*(m+2)*(m+1)//3 + m*(m+2)//2 + 2*m + 1