p549_divisibility_of_factorials_v3.clj

(ns euler.p549-divisibility-of-factorials-v3)


(defn primes
  ([] (primes (iterate inc 2)))
  ([s]
   (lazy-seq (if (nil? (first s))
               nil
               (cons (first s)
                     (primes
                       (filter #(not= 0 (mod % (first s))) (rest s))))))))

(defn find-a-prime-factor [x]
  "If we don't find a factor below the sqrt of x then we know x is prime."
  (let [to-check (primes (range 2 (+ (int (Math/sqrt x)) 2)))
        found (seq (filter #(zero? (mod x %)) to-check))]
    (if found
      (first found)
      x)))

(defn prime-factors-of [x]
  (let [factor (find-a-prime-factor x)
        to-factorize (quot x factor)]
    (cons factor
          (if (= to-factorize 1)
            nil
            (prime-factors-of to-factorize)))))

(defn factorials []
  "An infinite sequence of factorials!"
  (reductions *' (iterate inc 1)))

(defn ! [x]
  (nth (factorials) (dec x)))

(defn x-to-power-n [x n]
  (reduce #(* %1 %2) 1 (repeat n x)))

(defn smallest-m-for-power-of-factor [factor freq]
  (loop [m-to-try factor]
    (if (zero? (mod (! m-to-try) (x-to-power-n factor freq)))
      m-to-try
      (recur (+ m-to-try factor)))))

(def smallest-m-for-power-of-factor-memo (memoize smallest-m-for-power-of-factor))

(defn smallest-m-for-n [n]
  (let [pf-n (prime-factors-of n)
        f-pf-n (frequencies pf-n)]
    (apply max (map (fn [[factor freq]] (smallest-m-for-power-of-factor-memo factor freq)) f-pf-n))))

(defn smallest-m-for-n-naive
  "m is the lowest number where m! is divisible by n."
  [n]
  (loop [mtotry 2]
    (if (zero? (mod (! mtotry) n))
      mtotry
      (recur (inc mtotry)))))

(defn seq-of-smallest-m
  ([smallest-m-for-n-algo] (seq-of-smallest-m smallest-m-for-n-algo (iterate inc 2)))
  ([smallest-m-for-n-algo ns]
  (lazy-seq (cons (smallest-m-for-n-algo (first ns))
                  (seq-of-smallest-m smallest-m-for-n-algo (rest ns))))))

(defn smallest-m-so-that-!m-is-divisible-by-n
  ([find-m-func]
   (smallest-m-so-that-!m-is-divisible-by-n find-m-func 2))
  ([find-m-func n]
   (lazy-seq (cons (find-m-func n) (smallest-m-so-that-!m-is-divisible-by-n find-m-func (inc n))))))

(defn -main [& args]
  (println (time (apply + (take (dec (int 10e8)) (seq-of-smallest-m smallest-m-for-n))))))