Skip to content

Instantly share code, notes, and snippets.

@amalloy
Created August 30, 2011 19:31
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save amalloy/1181797 to your computer and use it in GitHub Desktop.
Save amalloy/1181797 to your computer and use it in GitHub Desktop.
Confusing results
;; As it turns out, A is much slower than B in some cases, but faster in others! Fun.
(time (sum-divisorsA 2000000)) => "Elapsed time: 3766.863 msecs"
(time (sum-divisorsB 2000000)) => "Elapsed time: 113.786 msecs"
(time (sum-divisorsA 200000)) => "Elapsed time: 3.233 msecs"
(time (sum-divisorsB 200000)) => "Elapsed time: 8.436 msecs"
(time (is-abundant?A 1000000)) => "Elapsed time: 14.259 msecs"
(time (is-abundant?B 1000000)) => "Elapsed time: 58.678 msecs"
;; Methods marked A use the inefficient method, yet produce results faster.
;; Methods marked B use the MUCH faster sum-divisors method with no other changes but gets much slower as the range you sum rises.
(defn is-abundant?A [num]
(> (sum-divisorsA num) num))
(defn is-abundantB? [num]
(> (sum-divisorsB num) num))
(defn abundantlistA [start end]
(filter is-abundant?A (range start end)))
(defn abundantlistB [start end]
(filter is-abundant?B (range start end)))
;; Newer, faster method of summing divisors
(defn divisors [num]
"Returns a list of the Proper Divisors of given number"
(filter #(zero? (mod num %)) (range 1 (inc (/ num 2)))))
(defn sum-divisorsB [num]
(reduce + (divisors num)))
;; Original, far slower but more algorithmic method of getting sum of divisors.
(defn primes-to [n]
(take-while #(< % n) primes))
(defn thorough-prime-factors [num]
"Returns the prime factors of a given number. 20 => (5 2 2)"
(loop [a (primes-to (inc (/ num 2)))
number num
factorlist '()]
(if (seq a)
(if (zero? (mod number (first a)))
(recur a (/ number (first a)) (conj factorlist (first a)))
(recur (rest a) number factorlist))
factorlist)))
(defn sum-divisorsA [num]
"Returns sum of Proper Divisors (not including number itself)"
(let [prime-factors (partition-by identity (thorough-prime-factors num))
sum (reduce * (for [[p :as ps] prime-factors]
(if (> (count ps) 1)
(-> (apply * p ps)
(dec)
(/ (dec p)))
(inc p))))]
(if (= sum 1) 1 (- sum num))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment