Lightly Seared On The Reality Grill

Also known as: Project Euler problem 15

Also known as: A week to understand, a minute to implement.

The problem:

Starting in the top left corner of a 2 x 2 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 20 x 20 grid?

To start with the simple observation first: Any route through an m x m grid can be expressed as a sequence of Rs and Ds where R is right and D is down (the without backtracking condition ensures that you can’t go left or up – this simplifies things somewhat).

The second observation is that each route must be exactly 2m steps long (m steps to the right and m steps down).

So the problem that needs to be solved is: How many ways can you combine m Rs and m Ds?

It turns out that this is a combination problem which Wikipedia handily defines as a way of selecting several things out of a larger group, where order does not matter. The larger group, in this case, is all 2m steps and the several things you want to select are the k possible combinations of R (or D). The Ds (or Rs) don’t matter because you know that they have to populate the m remaining slots in the path.

A k-combination of a set S is a subset of k distinct elements of S. If the set has n elements the number of k-combinations can be expressed as n! / k!(n - k)! as long as k<=n.

Implementing this was a doddle and, for bonus points, my solution should work for any rectangular grid.

Also known as Project Euler Problem 12.

This is the first one that has proved to be a bit of a challenge for me, and one that forced me both to do a bit of research and to take a look at the efficiency of some of my functions.

First the problem:

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

Obviously a brute-force approach is not going to work in this case. Since I already had a function for generating prime factors, which I developed for Problem 3, I started thinking about whether it was possible to calculate the total number of divisors of a number based on its prime factors.

It turns out that it is.

The factorisation of a number can be expressed as: P₁^F₁ * P₂^F₂ * … * P_n^F_n

And the total number of divisors is: (F₁ +1) * (F₂ + 1) * … * (F_n + 1)

For example, 28 can be expressed as 2^2 * 7^1 so the total number of divisors is (2 + 1) * (1 + 1) = 6

Or, 36 = 2^2 * 3^2 so the total number of divisors is 3*3 = 9.

Coding this formula was pretty straightforward. Unfortunately, the resulting program ground to a halt once I started looking for more than 200 divisors – and this has had me stumped for a couple of days. I knew my reasoning was sound and I could see the program generating correct results for small numbers of divisors, but I could not figure out why it didn’t scale.

It wasn’t until I went back to look at the efficiency of my factorisation function that the following insight hit me: You don’t need to test whether a number is prime if you can guarantee that your loop will only look at prime mumbers.

This insight resulted in the following, much more efficient, function:

def Factorise(integer):
	factors=[]
	index = 2
	while integer > 1:
		if integer % index == 0:
			factors.append(index)
			integer=integer/index
		else:
			index += 1
	return factors

Starting with an index of 2 (the lowest prime) I simply divide the integer by the index until I get a non integer result. Then I increment the index and start again.

Because the function repeatedly divides out each factor, integer/index can only return an integer result if index is prime.

With this approach, I was able to solve the problem in about half a second.