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 ≠ 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.
In [1]:
import itertools
import numpy as np
def prime_factors(n): # from eratosthenes
factors = []
d = 2
while n > 1:
while n % d == 0:
factors.append(d)
n /= d
d = d + 1
if d * d > n:
if n > 1:
factors.append(n)
break
return factors
def powerset(iterable): # from itertools
"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
s = list(iterable)
return itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(len(s)+1))
def proper_divisors(n):
pf = prime_factors(n)
factors = []
for p in set(powerset(pf)):
factors.append(int(np.prod(np.array(p))))
return sorted(factors)[:-1]
proper_divisors(n=220)
Out[1]:
In [2]:
divisor_sums = {}
for i in range(10001):
divisor_sums[i] = sum(proper_divisors(n=i))
amicable = []
for a in range(10001):
b = divisor_sums[a]
pa = divisor_sums[b] if b in divisor_sums else -1
if pa == a and a != b:
amicable.append(a)
print amicable
print sum(amicable)
In [ ]: