Problem 021: Amicable Numbers

It's been a long time since I've posted! That's alright though, we're back into it now. From Project Euler:

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"