Project Euler Problem 5

Ivar Thorson bio photo By Ivar Thorson

Here’s the link to the problem description. My first try at the problem resulted in a slow but working implementation.

(defn multiple-of-all? [n factors]
  (every? #(zero? (rem n %)) factors))

(defn least-common-multiple [nums]
  (let [ns (sort > nums)
        mx (first ns)]
    (first (filter #(multiple-of-all? % ns) (iterate #(+ mx %) mx)))))

(least-common-multiple (range 2 21))

A peek at what other people wrote revealed that once again, I went with a stupid search-based idea instead of looking at the mathematical structure of the problem.

An elegant three-line solution submitted anonymously was my favorite, and is very fast:

(defn gcd [a b] (if (zero? b) a (recur b (mod a b))))
(defn lcm [a b] (/ (* a b) (gcd a b)))
(reduce #(lcm %1 %2) (range 1 21))

There are three clever things about this that I like:

  1. Using recur in gcd leads to a simple, efficient definition.
  2. No functions use variable arity or require collections as arguments. Simple.
  3. Using reduce is the right idiom for “multiplication-like” algorithms such as this.

Once again, it seems it is useful to check if a problem easily fits into the reduce abstraction.