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 `1`

and `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 :: (a -> b) -> [a] -> [b]`

A `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 `map`

s, 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 `17`

:

`\x -> x `mod` 17 == 0`

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 `1`

and `10`

that factor into `123456`

:

```
Prelude> map (\y -> 123456 `mod` y == 0) [1 .. 10]
[True,True,True,True,False,True,False,True,False,False]
```

The `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:

```
and :: [Bool] -> Bool
and [] = True
and (b:bs) = b && and bs
```

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:

```
> euler5 = head [x | x <- [1 .. ]
> , and (map (\y -> x `mod` y == 0) [1 .. 20])]
```

This definition also uses the `head`

function, which takes the first element of a list, and returns an error if there are no elements:

```
head :: [a] -> a
head [] = error "Exception: empty list"
head (x:_) = x
```

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 `1`

and `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:

```
sum :: [Int] -> Int
sum [] = 0
sum (x:xs) = x + sum xs
```

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 `foldr`

:

```
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr _ k [] = k
foldr f k (x:xs) = x `f` foldr f k xs
```

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 `and`

and `sum`

in terms of `foldr`

:

```
and = foldr (&&) True
sum = foldr (+) 0
```

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:

`lcm :: Int -> Int -> Int`

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:

`1 `lcm` 2 `lcm` 3 `lcm` .. `lcm` 20`

You should be able to see that this can be expressed as a `foldr`

:

```
> lcms :: [Int] -> Int
> lcms = foldr lcm 1
```

The function `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 `1`

and `20`

:

`> euler5' = lcms [1 .. 20]`

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:

- A
`map`

preserves the structure of a list, while changing its elements. - A
`foldr`

traverses a list and changes its structure.