Recently, I’ve been doing a bunch of Project Euler problems. If you’re unfamiliar with Project Euler, it’s a collection of challenging puzzles that require math and programming to solve. The puzzles are grouped by difficulty level. However, I’ve found that the difficulty can vary wildly within the same group. One challenge that stood out as much harder than the rest is Problem 15. The problem statement can be found here: Problem 15 Statement.

Now, I’m going to continue under the assumption that you’ve read the problem. This contains a solution, so if you want to solve it on your own, do so before reading further.

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

Construct a lattice of nodes based on the problem description, one at each possible position. Let there be n nodes (n is one greater than the number of boxes per row or per column). The nodes in the bottom row and the last column have one possible move away (right and down, respectively), except for the node in the bottom row and last column, which is the terminal node. The rest of the nodes all have 2 possible choices to move away. The possible paths to take to the terminal node is the sum of the possible paths to the terminal node of each possible move. Since every node in the bottom row has exactly 1 possible path to the terminal node (continuing right until reaching the end), the possible paths of the nodes in the 2nd row from the bottom follow the sequence n, n-1, n-2, … 2, 1. So, working our way up, the number of possible paths of the ith node from the right in the 3rd row from the bottom is given by

$$\sum_{k=1}^{i}k = \frac{i(i+1)}{2}$$

so the ith node from the right in the 4th row from the bottom is

$$\sum_{k=1}^{i}\frac{k(k+1)}{2} = \frac{1}{2}\sum_{k=1}^{i}\left( k^2+k \right) = \frac{1}{2} \left(\sum_{k=1}^{i}k^2 + \sum_{k=1}^{i}k\right) = \frac{1}{2}\left( \frac{i(i+1)}{2} + \frac{i(i+1)(2i+1)}{6} \right)$$

and so on. Continuing all the way to the top, the top left node of the m by m grid of squares has

$$\frac{(2m)!}{(m!)^2}$$

possible paths to the terminal node. Plugging in m=2 (the example), this formula gives (4!)/2^2 = 24/4 = 6. For m=20 (the problem), it gives (40!) / (20!)^2 = 137846528820. Python code:

from math import factorial

def problem_15():
    return factorial(40) / factorial(20) ** 2

This took me forever and I have no clue why it’s in the 5% difficulty range.