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 clojure amicable.clj
real   0m5.683s
user   0m7.039s
sys    0m0.506s

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.439s
user   0m1.438s
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.345s
user   0m0.345s
sys    0m0.000s

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.006s
sys    0m0.000s