Let $d(n)$ be defined as the sum of proper divisors of $n$ (numbers less than $n$ which divide evenly into $n$).
If $d(a) = b$ and $d(b) = a$, where $a ≠ b$, then $a$ and $b$ are an amicable pair and each of $a$ and $b$ are called amicable numbers.
For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so $d(284) = 220$.
Evaluate the sum of all the amicable numbers under 10000.
$n!$ means $n × (n − 1) × ... × 3 × 2 × 1$
There's a lot of potential optimizations for this one, but I found it works just fine by brute forcing it. We'll start by defining a function that sums the divisors of a number:
(defn sum-divisors "Sums the divisors for the provided number." [n] (assert (> 0 n)) ; Loop through all the numbers from 2 to sqrt(n). We only need to ; go to sqrt(n) because all divisors less than that will have a ; corresponding divisor greater than sqrt(n). (loop [current 2 ; Start total from 1 because 1 is always a divisor. total 1] (if (> current (Math/sqrt n)) total (recur (+ 1 current) (if (= 0 (mod n current)) ; In the case of a square number, we only want to ; add the number once. (if (= current (quot n current)) (+ total current) ; Here we're not square, so we add both the number ; and it's complement on the other ; side of sqrt(n). (+ total current (quot n current))) total)))))After that, our code is pretty straight-forward:
(defn sum-amicable-numbers "Sums all amicable numbers up to and including `max`." [max] (->> (range 1 (+ 1 max)) (map #(list % (sum-divisors %))) ; Prune out numbers that are amicable with themselves. (remove #(= (first %) (last %))) ; Filter out any non-amicable numbers. (filter #(= (first %) (sum-divisors (last %)))) ; And sum them all up. (map first) (reduce +)))This runs very fast:
$ lein run Processing... Total is: 41274 "Elapsed time: 153.883368 msecs"
No comments:
Post a Comment