# 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.833s user 0m1.828s sys 0m0.004s ## 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.485s
user   0m0.484s
sys    0m0.004s

## Rust

fn sum_divisors(n: u64) -> u64 {
let mut result = 0;
let max = (n as f64).sqrt() as u64;
for i in 2..max {
if n % i == 0 {
let x = n / i;
if x == i {
result += i;
} else {
result += i + x;
}
}
}
1 + result
}

fn main() {
let sum: u64 = (1..10000)
.filter(|&n| {
let x = sum_divisors(n);
(n != x) && (sum_divisors(x) == n)
})
.sum();
println!("{}", sum);
}
$rustc -C target-cpu=native -C opt-level=3 -o amicable amicable.rs$ time ./amicable
real   0m0.006s
user   0m0.004s
sys    0m0.000s