# 4clojure 100 Least Common Multiple

06-Jul-2012 | Posted by Sonia Hamilton under Clojure |

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 :-)

## Recent Comments