475 Eric Normand Newsletter

00 Least common multiple.md

Least common multiple

Write a function that finds the least common multiple of a collection of numbers. Remember that the least common multiple is the smallest integer that is evenly divisible by all the numbers in the collection.

Examples:

(lcm []) ;=> nil (undefined)
(lcm [10]) ;=> 10
(lcm [2 4]) ;=> 4
(lcm [3 7]) ;=> 21
(lcm [2 4 10]) ;=> 20
(lcm [15 2 4]) ;=> 60

Thanks to this site for the problem idea, where it is rated Very Hard in Java. The problem has been modified.

Please submit your solutions as comments on this gist.

To subscribe: https://ericnormand.me/newsletter

Trying to follow the definition of lcm

(defn lcm
  [vs]
  (some
    (fn [n]
      (when (every?
              #(zero? (mod n %))
              vs)
        n))
    (range 2 (inc (apply * vs)))))

(ns lcm)
(require '[clojure.test :as test])

(defn lcm [vect]
    (if (= vect [])
        nil
        (let [mcd (fn [a b]
                    (loop [a1 a
                           b1 b]
                        (if (= b1 0)
                            a1
                            (recur b1 (mod a1 b1)))))
              mcm (fn [a b] (/ (* a b) (mcd a b)))]
          (reduce mcm vect))))

(test/deftest lcm-test
  (test/is (= nil (lcm [])))
  (test/is (= 10  (lcm [10])))
  (test/is (= 4   (lcm [2 4])))
  (test/is (= 21  (lcm [3 7])))
  (test/is (= 20  (lcm [2 4 10])))
  (test/is (= 60  (lcm [15 2 4]))))

(test/run-tests 'lcm)

(defn gcd [a b]
  (cond
    (= 0 b) a
    (< a b) (gcd b a)
    :else   (gcd b (mod a b))))

(defn lcm
  ([]    nil)
  ([a b] (/ (* a b) (gcd a b)))
  ([xs]  (reduce lcm xs)))

;; Finding the least common multiplier for a list of numbers
;; Reference material
;; https://en.wikipedia.org/wiki/Least_common_multiple
;; https://en.wikipedia.org/wiki/Euclidean_algorithm
;; https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/
;; https://octave.sourceforge.io/octave/function/lcm.html


(defn euclid-gcd [^long a ^long b]
      "Simple eclidean gcd https://en.wikipedia.org/wiki/Euclidean_algorithm"
      (loop [a' (long (max a b)) b' (long (min a b))]
            (if (zero? b')
              a'
              (recur b' (mod a' b')))))

(def ^:dynamic *gcd* euclid-gcd)

(defn lcm
      ([])
      ([^long a ^long b]
       (* a (/ b (*gcd* a b))))
      ([ls]
       (reduce lcm ls)))

(defn lcm [[f & r]]
  (loop [i f]
    (if (every? #(zero? (mod i %)) r) i
      (recur (+ i f)))))

I'm assuming all positive ints. Supporting zero or negatives would require more defensive code.

(defn lcm [nums]
  #_ {:pre [(every? pos-int? nums)]}
  (let [gcd (fn [x y]
              (if (zero? y)
                x
                (recur y (rem x y))))]
    (when (seq nums)
      (reduce (fn [x y] (quot (* x y) (gcd x y))) 1 nums))))