--- title: "Project Euler #5: Smallest Multiple" author: nbloomf date: 2017-03-10 tags: project-euler, literate-haskell --- First some boilerplate. > module ProjectEuler005 where [Problem 5](https://projecteuler.net/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. haskell $> 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