Project Euler #5: Smallest Multiple

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:

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.

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 \/ (a`rem`b)

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.

Anyway, the final answer is:

pe5 :: Integer
pe5 = lcms [1..20]

main :: IO ()
main = putStrLn $ show pe5