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)
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))
Out[7]:
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))
Out[9]: