In [2]:
"""
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.
"""
# import collections
def factorsLess(n):
"""Returns all factors of n that are less than n. (c) agf, steveha and Steinar Lima from SO."""
step = 2 if n%2 else 1
a = set(x for tup in ([i, n//i]
for i in range(1, int(n**0.5)+1, step) if n % i == 0) for x in tup)
a.discard(n)
return a
def amicableNumbers(x):
"""Returns the sum of all amicable numbers under x."""
sums = []
ams = []
for i in range(1,x+1):
sums.append(sum(factorsLess(i)))
for j in range(1,x+1):
if sums[j-1] <= x:
# print(j," ",sums[j-1]," ",sums[sums[j-1]-1])
if sums[sums[j-1]-1] == j and sums[j-1] != j:
print(j," ",sums[j-1]," ",sums[sums[j-1]-1])
if(j not in ams):
ams.append(j)
return(sum(ams))
In [4]:
amicableNumbers(10000)
Out[4]: