Euler #5 : Folding Multiples
by Nicolas Wu
Posted on 29 July 2010
Time for the next instalment in our Project Euler series of posts:
What is the smallest number divisible by each of the numbers 1 to 20?
We’ll first tackle this question by using a brute force method, where we check all the natural numbers, one after the other, until we find one that matches our criterion. Once we’ve done that, we’ll see how a little bit of thinking leads to a much simpler and faster solution.
One approach to this problem is to generate the list of natural numbers, and to check them one by one until we reach a number that is divisible by each of the numbers between
20. Although this version isn’t very smart, and is unbearably slow, its construction gives us a bit more practice with maps and other list functions.
We’ve already seen
map in the article about streaming Fibonaccis, where we saw that it has the following type:
map takes a function and a list, and changes the values in the list using the function while preserving the list structure.
Sometimes it’s convenient to describe small nameless functions so that we can use them in places, like in
maps, without having to worry about naming them. These functions are called lambda functions. As an example of one, here’s a lambda function that takes a value
x, and checks to see if it is a multiple of
Lambda functions are very useful in
map functions since we don’t always want to give the function we feed to
map a name. For example, here’s an expression that returns a list of
Bool values which correspond to the values between
10 that factor into
map in this expression transforms the list of numbers
[1 .. 10] into ten
Bool values, where each
Bool tells us whether or not
123456 is a multiple of the corresponding number. If each of the values in the list that was returned were
True, then we would know that
123456 was a multiple of them all. We can express this by using the
and function takes a list of
Bool values, and returns
True if the values in the list are all
True. We can put these functions together to produce our basic version of a solution to the problem:
This definition also uses the
head function, which takes the first element of a list, and returns an error if there are no elements:
The list we take the
head of is built from all the values of
x drawn from the natural numbers such that each of the values betwen
20 returns a
True after the
map. In other words, it is the a value which is evenly divisible by all those numbers.
You might have noticed that the structure of
and is very similar to that of
sum we saw before:
This kind of pattern is what is called a fold. A fold is basically a function that collapses a list into some value according to some pattern. Here’s the definition of
The first line of the definition tells us that when we apply
foldr to an empty list, then we simply return the constant
k. If the list is not empty, then we use
f as an infix operator to combine
x with the result of folding the rest of the list.
Using this function, we can write definitions of
sum in terms of
It turns out that this kind of pattern crops up all over the place so folds are a really useful concept. In fact, we’ll use a
foldr to solve our problem almost directly.
The smallest value divisible by two numbers is called the lowest common multiple, and Haskell comes equipped with a function, called
lcm, that finds this for us:
One way of understanding the lowest common multiple is that its list of prime factors is the smallest list that contains the prime factors of its arguments. This property allows us to freely distribute
lcm in a list of numbers to get the lowest common multiple of them all.
We can think of our answer as something like this:
You should be able to see that this can be expressed as a
lcms takes a list and produces the value obtained by applying
lcm between each consecutive element, where the base case is
1. Our final version is therefore the application of
lcms to the list of numbers between
This version runs much more quickly than our previous brute force approach.
Here’s a quick summary of some of the points we’ve made:
mappreserves the structure of a list, while changing its elements.
foldrtraverses a list and changes its structure.