Problem
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.
Answer
1 | 31626 |
Python1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21# We first compute a table of sum-of-proper-divisors, then we use it to test which numbers are amicable.
# This approach differs from the Java implementation because trying to directly compute
# the proper-divisor-sum of each number by brute force is unacceptably slow in Python.
def compute():
# Compute sum of proper divisors for each number
divisorsum = [0] * 10000
for i in range(1, len(divisorsum)):
for j in range(i * 2, len(divisorsum), i):
divisorsum[j] += i
# Find all amicable pairs within range
ans = 0
for i in range(1, len(divisorsum)):
j = divisorsum[i]
if j != i and j < len(divisorsum) and divisorsum[j] == i:
ans += i
return str(ans)
if __name__ == "__main__":
print(compute())
Ruby1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#!/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(:+)
Haskell1
2
3
4
5
6
7
8
9
10
11divisors :: 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]
Clojure1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20#!/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(:+)
Mathematica1
2
3
4
5
6
7(*
* We modify a built-in function to find the sum of proper divisors of a number.
* Then we apply the definition of an amicable number straightforwardly.
*)
DivisorSum[n_] := DivisorSigma[1, n] - n
AmicableQ[n_] := DivisorSum[n] != n && DivisorSum[DivisorSum[n]] == n
Total[Select[Range[9999], AmicableQ]]
Java1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38public final class p021 implements EulerSolution {
public static void main(String[] args) {
System.out.println(new p021().run());
}
/*
* We find the sum of proper divisors of a number by brute force,
* and apply the definition of an amicable number straightforwardly.
*/
public String run() {
int sum = 0;
for (int i = 1; i < 10000; i++) {
if (isAmicable(i))
sum += i;
}
return Integer.toString(sum);
}
private static boolean isAmicable(int n) {
int m = divisorSum(n);
return m != n && divisorSum(m) == n;
}
private static int divisorSum(int n) {
int sum = 0;
for (int i = 1; i < n; i++) {
if (n % i == 0)
sum += i;
}
return sum;
}
}
