Problem 005: Smallest Multiple

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?

This is a pretty straight-forward problem: we're just trying to find the least-common multiple (LCM) of a set of numbers. To find the LCM, it is just the product of the two numbers $a$ and $b$ divided by their greatest common divisor (GCD). If we think for a second about why this works: any number is just a product of prime factors. A prime number is just a product of itself and 1, composite numbers are a more complex sequence: 12 is a product of 2 * 2 * 3, 8 is a product of 2 * 2 * 2. When you multiply the two numbers together, you're a making a long sequence of prime factors that will result in the product of $a$ and $b$.

This product however is not the least common multiple, because there could be factors in common between $a$ and $b$: both 8 and 12 have a common factor of 2 * 2, if we simply multiplied them together we'd get 96 when the LCM is actually 24. We should divide by the GCD (2 * 2) to filter out these common factors. This gives us the correct result: 96 / 4 = 24.

Here's the code, which uses the Euclidean algorithm to find the GCD of two numbers:

(defn gcd [a b]
  (cond 
    (< a b) (gcd b a)
    (== 0 b) a
    :else (gcd b (mod a b))))

(defn lcm [a b]
  (if (or (== a 0) (== b 0))
    0
    (quot (* a b) (gcd a b))))

Then we can just do a reduce to get the LCM of the range:

(println (reduce lcm (range 1 21)))

This runs pretty fast (note that on my machine the JVM takes about 1.5s to start up):

$ time clj 5.clj
232792560

real 0m1.585s
user 0m3.136s
sys 0m0.151s

An alternative approach is to use something like the Sieve of Eratosthenes (SoT). This is an algorithm for finding prime numbers, but we can use the same idea here. The way the SoT works is you take a list of numbers from 2 to $N$. For each number $i$, you loop through the rest of the list, removing any multiple of $i$. After the first pass we'll have removed all numbers divisible by 2, after the second pass all numbers divisible by 3, etc. What we'll be left with is just a list of prime numbers. We'll apply the same idea here, but instead of removing the number if it is divisible, we'll divide out our current factor.

(defn lcm-sieve [xs]
  (if (empty? xs) ()
    (let [head (first xs)
          tail (rest xs)]
      (cons head
            (lcm-sieve (map #(if (== 0 (mod % head))
                               (quot % head)
                               %)
                              tail))))))

This algorithm efficiently gives us the list of prime factors for the LCM:

user=> (lcm-sieve (range 1 11))
(2 3 2 5 1 7 2 3 1)

These can be combined using reduce:

(println (->> (range 1 21)
              (lcm-sieve)
              (reduce *)))

This gives the correct result:

rob@alien ~/code/euler $ time clj 5.clj
232792560

real 0m1.549s
user 0m3.014s
sys 0m0.143s

Both methods seem quite fast, I hit integer overflow on my machine without either of them taking more than half a second. The reason I dove into the second one is that the SoT algorithm is the basis for a lot of my solutions in the future, so it's good to see a version of it now.