# Project Euler #5: Smallest Multiple

Posted on 2017-03-10 by nbloomf

Spoiler alert! This page is part of a series on solutions to Project Euler problems. If you prefer to solve problems yourself, do not read on!

This post is literate Haskell; you can load the source into GHCi and play along.

First some boilerplate.

module ProjectEuler005 where

Problem 5 from Project Euler:

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?

The smallest natural number $$k$$ that is divisible by natural numbers $$a$$ and $$b$$ is called their least common multiple; we’ll denote this by $$a \wedge b$$.

The inverse notion, the largest natural number that divides both $$a$$ and $$b$$, is called their greatest common divisor; we’ll denote this by $$a \vee b$$.

As operations, the LCM and GCD have lots of nice properties. But two are important for us. For all natural numbers $$a$$, $$b$$, and $$c$$, we have the following.

1. $$a \wedge b = \frac{ab}{a \vee b}$$
2. $$a \wedge (b \wedge c) = (a \wedge b) \wedge c$$

The first property says that the LCM can be computed easily if we know the GCD. This is useful because there is a nice algorithm, called the Euclidean Algorithm, for computing GCDs.

Let $$a$$ and $$b$$ be natural numbers, and let $$q$$ and $$r$$ be natural numbers such that $$a = qb+r$$ and $$0 \leq r < b$$. Then $$a \vee b = b \vee r$$.

What makes the Euclidean Algorithm so nice is that, combined with the Well-Ordering Property of the natural numbers, it gives us a recursive algorithm for computing GCDs.

(\/), (/\) :: Integer -> Integer -> Integer

a \/ 0 = a
a \/ b = b \/ (aremb)

a /\ b = (a*b)div(a \/ b)

The second property above says that if we want to find the LCM of a bunch of integers, we can do so pairwise, and it doesn’t matter what order we do this in. For instance, using foldr1:

lcms :: [Integer] -> Integer
lcms = foldr1 (/\)

Now lcms will take a nonempty list of positive integers and compute their least common multiple.

$> lcms [1..10] 2520 The Euclidean Algorithm is pretty snappy. Just for fun, here are some timings. k lcms [1..(k*10^4)] 1 0.26 s 2 0.74 s 3 1.76 s 4 2.67 s 5 4.26 s 6 5.63 s 7 7.81 s 8 9.51 s 9 11.24 s Anyway, the final answer is: pe5 :: Integer pe5 = lcms [1..20] main :: IO () main = putStrLn$ show pe5