down-to-zero-2.clj

(ns down-to-zero.core)

(defn factorial
  [i n factors]
  (if (> i (Math/sqrt n))
    ;; we've found all the factors, return
    factors
    (if (zero? (mod n i))
      ;; this is a factor, add it, increment i, and recurse
      (factorial (inc i) n (conj factors i (/ n i)))
      ;; this is not a factor, increment i and recurse
      (factorial (inc i) n factors))))

(defn factor-cost
  [n]
  (let [f (factorial 1 n #{})
        c (count f)]
    (if (odd? c)
      ;; the number has an integer square root
      (first (drop (Math/floor (/ c 2)) (sort f)))
      ;; the number doesn't have an integer square root; take the larger of its
      ;; two median factors
      (second (drop (dec (Math/floor (/ c 2))) (sort f))))))

(defn cost-fn
  [q]
  (let [f-cost (factor-cost q)]
    (if (< f-cost q)
      ;; using one of the factors has a cost of 1
      (inc (cost-fn f-cost))
      q)))