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.336s
user   0m6.348s
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.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