Five Euler Problems

I particularly like the problems laid out in Project Euler. They are not practical problems, but they are good coding drills. This post will cover the first 5 problems and their solutions in Python (a language I’m trying to get better at), with explanations.

In this post, I’ve implemented spoiler tags that look like this: This is a spoiler!. Just mouse over or touch to reveal.

Problem #1: Multiples of 3 and 5

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.

At the face of it, this is about as simple as it gets. We simply need to run through a range of integers (specifically 0-999) and only sum the integers that are multiples of 3 or 5.

Solution

001.py
1
2
3
4
#!/usr/bin/env python

print sum(i for i in range(1000)
    if (i % 3 == 0) or (i % 5 == 0))

This gives us the result 233168.

Explanation

This shouldn’t require much breakdown, as it is a one-liner (split over 2 lines for readability). We are iterating over a range, with a running sum of all integers that are divisible by 3 or 5. We use the modulo operation % to test if the integers are divisible.

Problem #2: Even Fibonacci Numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …


By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Now this is a big step up from #1, but follows mostly the same principles. First of all, we need to generate a Fibonacci sequence of up to four million, then sum all of the even integers. To do this, we should import itertools. itertools is a native Python module that implements iterator building blocks inspired by functional programming languages such as Haskell.

Solution

002.py
1
2
3
4
5
6
7
8
9
10
#!/usr/bin/env python
import itertools

def fib():
    x,y = 0,1
    while True:
        yield x
        x,y = y, x+y

print sum(x for x in itertools.takewhile(lambda x: x <= 4e6, fib()) if x % 2 == 0)

This gives us the result 4613732.

Explanation

Unlike the solution to #1, this does require some explanation. First of all, we import itertools to be able to make use of some of the functions contained within.

On lines 4-8, we define our Fibonacci generator. It is a while loop that generates a Fibonacci sequence i.e. the current integer is the sum of the previous two integers, starting at 0 (as per OEIS). yield is a little tricky to understand. Very loosely, it is a return statement that runs multiple times. Essentially, it allows us to iterate over the whole of the sequence and store the values in memory, where using return would end the function after reaching the next integer in the sequence.

The real magic is going on in line 10. Here, we use the takewhile function. This makes an iterator that returns elements from the iteratable (in this case, fib()) as long as a predicate is true (in this case, lambda x: x <= 4e6).

The lambda function is an anonymous function, i.e. a function that is created at runtime, and adds a bit of functional flavour to the program. This is primarily used to prevent the use of another while loop.

So, print sum(x for x in itertools.takewhile(lambda x: x <= 4e6, fib()) if x % 2 == 0) (roughly) translates to English as:

While x is less than four million, run the Fibonacci sequence generator. If x is divisible by 2, add it to the previous even integer in the Fibonacci sequence. Stop when you get to beyond four million, and print the sum of all the even integers to the console.

Earlier in this section I said ‘we need to generate a Fibonacci sequence of up to four million, then sum all of the even integers’. In this solution, we did both at the same time. This results in a much faster solution than generating a list of all the integers of a Fibonacci sequence up to four million, then iterating over that list to find all the even integers, and then calculating the sum of all the even integers.

Problem #3: Largest Prime Factor

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

Prime factorisation is one of the most well known, and relied upon, problems in mathematics. For a number as large as ~6e11, we need to be clever in our method (though maybe not as clever as a general number field sieve).

Essentially, we want to use Python’s max function, in combination with a function that can do the prime factorisation. Unfortunately, such a function doesn’t exist in any of the default Python modules, so we’ll need to define one ourselves.

Solution

003.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#!/usr/bin/env python

def pfactors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

print max(pfactors(600851475143))

This gives us the result 6857. The list of prime factors is [71, 839, 1471, 6857].

Explanation

Let me preface this with that this solution is pretty much a brute-force algorithm, and is not optimised for performance. It is in keeping with the idea of creating a growing ‘toolset’ to solve further Euler problems.

Firstly, we define our prime factorisation function, that takes any integer as an argument. i = 2 is our starting point, the first prime. We create an empty list on line 4, and introduce our while loop in line 5. We are brute forcing our way through the factors by dividing the first factor out of the original intger, and so on (n //= i is short-hand for ‘divide n by the whole integer i, and then set n to the result’). We can see this process with a little bit of tracing code:

1
2
3
4
5
6
$ python 003.py
71 is a factor. Test for 8462696833
839 is a factor. Test for 10086647
1471 is a factor. Test for 6857
Appending 6857
6857

This is fairly good for for relatively small integers, but for larger integers we would need to implement some sort of number sieve to get rid of all square numbers, for example, to speed things up.

Problem #4: Largest Palindrome Product

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.

This is a fun little problem. As usual, let’s break it down into the component parts. At first glance, it seems we need to enumerate all products of all possible combinations of two integers between 100 and 999, then test if those products are palindromic, then find the maximum value in the list. That sounds like a lot of work.

Fortunately, by treating the products as strings, we can speed this process up considerably.

Solution

004.py
1
2
3
4
5
6
7
8
9
10
11
12
#!/usr/bin/env python

n = 0
for a in xrange(100, 1000):
     for b in xrange(a, 1000):
         x = a * b
         if x > n:
             s = str(x)
             if s == s[::-1]:
                 n = a * b

print n

This gives us the result 906609.

Explanation

xrange is a function that creates an xrange object that you can iterate over, and the memory footprint of the object does not change no matter how big the range contained within is, unlike a list. Briefly, we iterate over an xrange object that starts at 100 and ends at 999, increasing by a step of 1 each time, while iterating over another xrange object that starts at the current value of a and terminates at 999, increasing by 1.

These two for loops create the terms that we multiply together to get the product x, which then if x > n we convert the product to a string, and then test if it is palindromic (line 9). The s[::-1] notation takes the string s and reverses it, and is called an extended slice.

Finally, n is set to the palindromic product of a and b, and the loop begins anew until if x > n is no longer satisfied.

Problem 5: Smallest Multiple

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

What we are looking for is a way to compute the least common multiple (hereon written as ‘lcm’) for a range between 1 and 20. To do this, we also need to be able to compute the greatest common divisor (hereon written as ‘gcd’), so we will need include both in the solution.

Solution

005.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!/usr/bin/env python

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

n = 1
for i in xrange(1,21):
    n = lcm(n, i)
print n

This gives the result 232792560.

Explanation

The gcd can be calculated using Euclid’s algorithm, described formally below:

$$gcd(a, b) = gcd(b, a \,\mathrm{mod}\ b)$$

$$where$$

$$a \,\mathrm{mod}\, b = a – b \left\lfloor {a \over b} \right\rfloor$$

We define our function gcd to use the above algorithm over lines 3 to 6, and is a simple while loop containing the algorithm.

The least common multiple can be computed using the greatest common divisor, as below:

$$lcm(a, b) = \frac{a \cdot b}{gcd(a, b)}$$

We create an xrange object to iterate over that contains the integers from 1 to 20, and find the lcm for the xrange object.

Conclusion

In this post, I have gone over possible solutions for Euler problems 1 – 5, written in Python. These are not definitive, nor elegant solutions. All solutions can be found as seperate .py files in the project_euler repository on my Github, and will be updated if/when the problems change parameters.

What’s next?

Where to go from here? More Euler problems with solutions and explanations, and possibly the start of a larger project, documented here.