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.

Evaluate the sum of all the amicable numbers under 10000.


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]:
[1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110]

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)


[220, 284, 1184, 1210, 2620, 2924, 5020, 5564, 6232, 6368]
31626

In [ ]: