Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?

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.

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

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: P1^F1 * P2^F2 * … * Pn^Fn

And the total number of divisors is: (F1 +1) * (F2 + 1) * … * (Fn + 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.

Decathlete

I don’t really have anything more to say about Project Euler, but I am quite pleased with myself for having unlocked the second progress award.

I can now claim to be a Python programming Mathematical Decathlete and the 14170th person to unlock this achievement.

I have to admit that my maths were more than a little rusty when I started having a go at these problems but, in figuring out how best to attack these problems, I have both remembered and learned a huge amount. I have also, over the past few weeks, gained a much greater appreciation of just how elegant many mathematical concepts can be.

This is getting addictive

After mentioning Project Euler yesterday, I signed up and have started working through the problems. What is interesting – and something I hadn’t realised when I signed up – is that once you have solved a problem, you can access a forum discussing it. This allows you to compare your solution to other people’s and gain a decent insight into how your code can be improved.

The other thing that adds to the addictiveness of the site is the progress page and the awards that you can earn.

I have now solved the first three problems which means that I have earned the Baby Steps award. Go me!

Better than FreeCell

From the Project Euler home page, which I found by way of Vincent Knight:

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.

The motivation for starting Project Euler, and its continuation, is to provide a platform for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context.

The first few problems (as far as I’ve browsed, at least) don’t appear to be particularly difficult from a mathematical point of view, but they do appear to provide enough of a programming/scripting challenge to be worth having a crack at rather than wasting time with the more mind-numbing types of solitaire.