Project Euler Problem 21 Solution

Question

Let d(n)d(n) be defined as the sum of proper divisors of nn (numbers less than nn which divide evenly into nn).

If d(a)=bd(a) = b and d(b)=ad(b) = a, where aba \neq b, then aa and bb are an amicable pair and each of aa and bb 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)=284d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284)=220d(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 clojure amicable.clj
real   0m5.875s
user   0m11.844s
sys    0m0.412s

Haskell

divisors ::  Integer -> [Integer]
divisors n = [x | x <- [1..(div n 2)], n `mod` x == 0]

d ::  Integer -> Integer
d = sum . divisors

isAmicable ::  Integer -> Bool
isAmicable n = n /= x && d x == n where x = d n

main ::  IO ()
main = print $ sum $ filter isAmicable [1..10000]
$ ghc -O2 -o amicable amicable.hs
$ 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