Euler Project: Problem 5 in Clojure

I solved the fifth problem from Euler project in Clojure.

My first approach was not successful:

	(def positive-integers (iterate inc 1))
	(def evenly-divisible?
	(comp zero? rem))
	(defn evenly-divisible-by-numbers? [from to number]
	(let [numbers (range from (+ to 1))]
	(every? (partial evenly-divisible? number) numbers)))
	(defn positive-numbers-evenly-divisible-by-numbers [from to]
	(filter (partial evenly-divisible-by-numbers? from to)
	positive-integers))
	(first
	(positive-numbers-evenly-divisible-by-numbers 1 10)) ; 2520
	;(first
	; (positive-numbers-evenly-divisible-by-numbers 1 20))
	; java.lang.OutOfMemoryError: GC overhead limit exceeded

view raw euler-5-1.clj hosted with ❤ by GitHub

Even though it could compute the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder, it didn't work for 1 to 20.
It consumed to much memory.

So I used pen and paper to devise a better approach to solve the problem.

I saw that the numbers from 1 to 10 which multiplied produce 2520 are 9, 8, 7 and 5.
What these numbers have in common is that they all have one prime factor with the highest possible multiplicity in the 1 to 10 range.

This is the code that I derived from those two facts:

	(def factor?
	(comp zero? rem))
	(defn prime-factors [n]
	(loop [n n prime 2 factors []]
	(cond
	(= n 1) factors
	(factor? n prime) (recur (/ n prime) prime (conj factors prime))
	:else (recur n (inc prime) factors))))
	(defn unique-factor? [factors]
	(and (not (empty? factors))
	(apply = factors)))
	(defn extract-divisors [numbers-with-unique-factor]
	(loop [numbers-with-unique-factor numbers-with-unique-factor
	divisors [] factors []]
	(if (empty? numbers-with-unique-factor)
	divisors
	(let [factor (first (second (first numbers-with-unique-factor)))]
	(if (some #{factor} factors)
	(recur (rest numbers-with-unique-factor)
	divisors
	factors)
	(recur (rest numbers-with-unique-factor)
	(conj divisors (first (first numbers-with-unique-factor)))
	(conj factors factor)))))))
	(extract-divisors
	(filter #(unique-factor? (second %))
	(map #(vector % (prime-factors %))
	(reverse (range 1 10))))) ; [9 8 7 5]
	(extract-divisors
	(filter #(unique-factor? (second %))
	(map #(vector % (prime-factors %))
	(reverse (range 1 20))))) ; [19 17 16 13 11 9 7 5]
	(defn smallest-evenly-divisible-by-all [from to]
	(reduce
	*
	(extract-divisors
	(filter #(unique-factor? (second %))
	(map #(vector % (prime-factors %))
	(reverse (range from (+ to 1))))))))
	(smallest-evenly-divisible-by-all 1 10) ; 2520
	(smallest-evenly-divisible-by-all 1 20) ; 232792560

view raw euler-5-2.clj hosted with ❤ by GitHub

which yields the right result.

Update:

As Leo pointed out in his comment, the answer is the least common multiple of the numbers from 1 to 20.

This is the final (more elegant and much simpler than the previous one) solution to the problem:

	(defn greatest-common-divisor [a b]
	(if (zero? b)
	a
	(greatest-common-divisor b (rem a b))))
	(defn least-common-multiple [a b]
	(/ (* a b) (greatest-common-divisor a b)))
	(defn smallest-positive-number-evenly-divisible-by-all [from to]
	(reduce
	least-common-multiple
	(range from (+ to 1))))
	(smallest-evenly-divisible-by-all 1 10) ; 2520
	(smallest-evenly-divisible-by-all 1 20) ; 232792560

view raw euler-5-3.clj hosted with ❤ by GitHub