Euler #5 : Folding Multiples

by Nicolas Wu

Posted on 29 July 2010

Tags: ,

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.

Brute Force

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 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 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.

Folding

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.

Summary

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.

Comments