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]:
from itertools import product, repeat

In [2]:
from euler import get_factors, gen_prime

In [3]:
import operator

In [4]:
def d(n):
    factors = get_factors(n)
    divisors = set([1])
    # print zip(list(product(*[range(2)] * len(factors))), repeat(factors))
    divisors = set(map((lambda x, y: reduce(operator.mul, filter(None, map(operator.mul, x, y)), 1)), product(*[range(2)] * len(factors)), repeat(factors, 2**len(factors))))
    # print map((lambda x: filter(x[0], x[1])), zip(list(product(*[range(2)] * 4)), repeat(factors)))
    return sum(divisors - set([n]))

In [5]:
print d(220), d(284)


284 220

In [6]:
def foo(n):
    ds = [d(i) for i in range(n)]
    amicable_numbers = set([])
    for i in range(2, n):
        for j in range(i+1, n):
            if ds[i] == j and ds[j] == i:
                amicable_numbers.add(i)
                amicable_numbers.add(j)
    return amicable_numbers

In [7]:
n = 10000
%timeit sum(foo(n))
sum(foo(n))


1 loops, best of 3: 6.99 s per loop
Out[7]:
31626

In [8]:
def foo(n):
    ds = [d(i) for i in range(n)]
    big_ds = dict([(i, d(i)) for i in ds if i>n])
    # print len(big_ds)
    amicable_numbers = set([])
    for i in range(2, n):
        j = ds[i]
        if j < n:
            if i != j and ds[j] == i:
                amicable_numbers.add(i)
                amicable_numbers.add(j)
        else:
            if i != j and big_ds[j] == i:
                amicable_numbers.add(i)
                
    return amicable_numbers

In [9]:
n = 10000
%timeit sum(foo(n))
sum(foo(n))


1 loops, best of 3: 1.62 s per loop
Out[9]:
31626