Created
April 28, 2022 21:56
-
-
Save jamiepratt/84762b9d537ab486d32cb9d8959593aa to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(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)))))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment