Least common multiple
Find the least common multiple of an array of integers. That is, find the smallest positive integer that is evenly divisible by all of the integers in the array.
Examples
(lcm [1 2 3]) ;=> 6
(lcm [5 4 4]) ;=> 20
(lcm []) ;=> 1
(lcm [10]) ;=> 10Thanks to this site for the challenge idea where it is considered Expert in JavaScript.
Please submit your solutions as comments on this gist.
(defn gcd [x y]
(if (zero? y)
x
(recur y (mod x y))))
(defn lcm
([nums]
(reduce lcm 1 nums))
([x y]
(quot (* x y) (gcd x y))))
(letfn [(lcm [vs]
(letfn [(cm? [v] (every? (fn [x]
(zero? (rem v x)))
vs))]
;; eduction should avoid chunks
(first (eduction (comp (map inc)
(filter cm?))
(range (apply * vs))))))]
[(lcm [1 2 3]) #_> 6
(lcm [5 4 4]) #_> 20
(lcm []) #_> 1
(lcm [10]) #_> 10
(lcm [2 3 4 5 7]) #_> 420]) In JS
let lcm = vs => Array(vs.reduce((acc, v) => acc * v, 1))
.fill()
.map((el, idx) => idx + 1)
.filter(v => vs.reduce((acc, x) => acc && (0 == v % x), true))[0]
In Rust, integers already have a pairwise lcm, so we might do a list of them like so
fn lcm(s: &[i32]) -> i32 {
s.iter().fold(1, |acc, item| acc.lcm(item))
}But Rust has lots of types of integers, so we would want a generic version. For this, we need a generic 1 also.
fn lcm<T: Integer>(s: &[T]) -> T {
s.iter().fold(num::one(), |acc, item| acc.lcm(item))
}These are things we don't often worry about in Clojure (or JavaScript or...).
(defn lcm [[f & r]]
(loop [i f]
(if (every? #(zero? (mod i %)) r)
(if (nil? i) 1 i)
(recur (+ i f)))))
@oylenshpeegul in clojure, you can do num::one() with (*)
In @mchampine example:
(defn lcm [[f & r]]
(loop [i f]
(if (every? #(zero? (mod i %)) r)
(if (nil? i) (*) i)
(recur (+ i f)))))
Ah, yes! Multiplying no things together gives 1, the multiplicative identity. Similarly, we could get Rust's num::zero() with (+). Adding no things together gives 0, the additive identity. Clojure is so beautiful!
Using a naive sieve, taking the maximum power of each prime factor for all numbers and multiplying everything together:
(defn factors-map [n]
(loop [n n, factors [], divs (drop 2 (range))]
(let [div (first divs)]
(if (= n 1)
(frequencies factors)
(if (zero? (rem n div))
(recur (/ n div) (conj factors div) divs)
(recur n factors (rest divs)))))))
(defn lcm [xs]
(->> (map factors-map xs)
(reduce (partial merge-with max) {})
(mapcat (fn [[base pow]] (repeat pow base)))
(reduce * 1)))
;; (lcm [1 2 3]) ;=> 6
;; (lcm [5 4 4]) ;=> 20
;; (lcm []) ;=> 1
;; (lcm [10]) ;=> 10
(defn multiples [n]
(iterate (partial + n) n))
(defn lcm [xs]
(->> xs
(map multiples)
(apply interleave)
(reduce (fn [freqs x]
(if (> (count xs) (inc (get freqs x)))
(update freqs x inc)
(reduced x)))
{}))) 
(defn reduce-nums [[a b]]
(if (= a b)
(list a b)
(list (min a b) (- (max a b) (min a b)))))
(defn gcd [a b]
(->> (iterate reduce-nums [a b])
(drop-while (partial apply not=))
(first)
(first)))
(defn lcm [[x1 x2 & xs :as x-all]]
(cond (empty? x-all) 1
(nil? x2) x1
:else (let [lcm (/ (* x1 x2) (gcd x1 x2))]
(if (empty? xs)
lcm
(recur (cons lcm xs))))))
A set-based version:
(defn multiples [n]
(iterate #(+ n %) n))
(defn keep-le [nums n]
(take-while #(<= % n) nums))
(defn lcm [nums]
(let [product (apply * nums)]
(->> nums
(cons 1)
(map multiples)
(map #(keep-le % product))
(map set)
(apply clojure.set/intersection)
(apply min))))Compare multiples lazily:
(defn lcm2 [a b]
(loop [[a & as :as aas] (range a (inc (* a b)) a)
[b & bs :as bbs] (range b (inc (* a b)) b)]
(cond
(= a b)
a
(< a b)
(recur as bbs)
(> a b)
(recur aas bs)
:else
(throw (ex-data "Should not get here." {:a a :b b})))))
(defn lcm [nums]
(reduce lcm2 1 nums))
A pretty straightforward aproach:
(defn lcm
([coll] (reduce lcm 1 coll))
([a b]
(let [numbers (drop (max a b) (range))]
(first
(filter #(and (zero? (mod % a))
(zero? (mod % b)))
numbers)))))Loved the ones that were the math definition :D
(use '[clojure.math.numeric-tower :only (gcd)])
(defn lcm [ns] (reduce (fn [n m] (/ (* m n) (gcd m n))) 1 ns))