4clojure 100 Least Common Multiple

5 Jul 2012

4clojure problem 100 - calculate the Least Common Multiple (LCM) of two or more numbers.

Here’s how I worked it out in the REPL, warts and all….

I first thought about using the meaning of LCM to solve this (as given in Wikipedia), ie for two numbers a and b (eg 4 and 6), find all the multiples of a (an infinite sequence), find all the multiples of b (an infinite sequence), and find the first match. But I was impatient and didn’t want to work out how to find the first match between lists, so I decided to use the GCD definition:

From there it was just a matter of balancing parentheses (thanks paredit) by breaking up the problem into stages, starting with calculating the GCD of two numbers:

(defn gcd [a b]
  (cond
   (= b 0) a
   (= a 0) b
   (> a b) (gcd b (mod a b))
   (> b a) (gcd a (mod b a))))
(gcd 15 5)
==> 5

Now get LCM working for two arguments:

(defn lcm [x y]
  (/ (* x y) (gcd x y)))
(lcm 4 6)
==> 12

Now get LCM working for more than two arguments. I remembered seeing multiple arities used to solve other 4clojure problems, so I thought I’d use the Arity-Reduce “pattern” (well I’m using apply, same idea):

(defn lcm2
  ([x y] (/ (* x y) (gcd x y)))
  ([x y & rest] (apply lcm2 (lcm2 x y) rest)))
(lcm2 5 3 7)
==> 105

4clojure doesn’t allow defn, so I then used letfn to nest my definition of GCD inside LCM:

(fn lcm3
  ([x y]
     (letfn [(gcd2 [a b]
               (cond
                (= b 0) a
                (> a b) (gcd2 b (mod a b))
                (> b a) (gcd2 a (mod b a))))]
       (/ (* x y) (gcd2 x y))))
  ([x y & rest] (apply lcm3 (lcm3 x y) rest)))
(lcm3 5 3 7)
==> 105

So my solution worked, but it wasn’t very elegant - Dacquiri wins the prize for that, again :-)