Project Euler

I discovered Project Euler a few weeks ago while searching for something to keep my mind (and programming skills) busy during the holidays. Its proven itself to be exactly what I was looking for — if a bit more challenging than I was expecting.

Project Euler isn’t for everyone. If you don’t have a fairly decent grasp of maths and the ability to do a bit of coding then you will struggle with the vast majority of the 250+ problems. These are not easy. Of course if you’re willing to learn and have enough determination then the first few should be well within your reach.

One of the fantastic things about Project Euler is that many of the concepts you learn can be used later on as part of a solution to a much more difficult problem. This is a great learning experience and something well worth putting some time into if you’re interested in this sort of thing.

Problem 1

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

A very simple first problem to get us started.

Arguably the most obvious solution is a bruteforce algorithm which looks at the numbers 1-999, checks whether they meet the desired criteria (divides evenly by 3 or 5) and returns the sum of the valid results.

Below is my implementation of the algorithm in Python:

sum = 0
for i in xrange(1000):
    if ((i % 3) == 0) or ((i % 5) == 0):
        sum += i
print sum

Or in much less (readable) code:

print sum(x for x in xrange(1000) if (x % 3) == 0 or (x % 5) == 0)

Even using bruteforce it computes the answer comfortably inside Project Euler’s “one-minute rule”, it takes only 0.035s to run only my 2.2Ghz laptop.

Of course there’s more than one way to skin a cat. Another solution is to sum all the multiples of 3 and 5 between 1 and 999 and subtract the sum of the duplicates, in this case all multiples of 15. This method is an example of the Inclusion-exclusion principle.

Python makes this very easy to do thanks to the range() function (or xrange if you’re working with larger numbers and have the memory to spare):

print sum(xrange(0,1000,3)) + sum(xrange(0,1000,5)) - sum(xrange(0,1000,15))

This runs in approximately the same time as my bruteforce algorithm, there are much more efficient ways of calculating the sum of a series of numbers but I’ll leave you to discover them for yourself.