# Project Euler Problem 21 Solution

## Question

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 \neq 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.

## Clojure

#!/usr/bin/env clojure
(defn divisors [n]
(filter #(zero? (mod n %)) (range 1 (+ 1 (/ n 2)))))

(defn d [n]
(reduce + (divisors n)))

(defn amicable? [a b]
(and (not (= a b)) (= (d a) b) (= (d b) a)))

(println (reduce + (filter #(amicable? % (d %)) (range 10000))))
$time ./amicable real 0m1.378s user 0m1.364s sys 0m0.000s ## Ruby #!/usr/bin/env ruby require 'mathn' class Integer def divisors return [1] if self == 1 primes, powers = self.prime_division.transpose exponents = powers.map{|i| (0..i).to_a} divisors = exponents.shift.product(*exponents).map do |powers| primes.zip(powers).map{|prime, power| prime ** power}.inject(:*) end divisors.sort.take divisors.length - 1 end def amicable?(n=self.divisors.reduce(:+)) n != self && n.divisors.reduce(:+) == self end end puts (1..10000).find_all { |n| n.amicable? }.reduce(:+) $ time ruby amicable.rb
real   0m0.419s
user   0m0.408s
sys    0m0.008s