Project Euler #5: Smallest Multiple

Posted on 2017-03-10 by nbloomf
Tags: project-euler, literate-haskell

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 \/ (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]

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