#21: Amicable numbers | Ben Cunningham

#21: Amicable numbers

Problem by Project Euler · on July 5, 2002

Let be defined as the sum of proper divisors of (numbers less than which divide evenly into n).

If and , where , then and are an amicable pair and each of and 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 . The proper divisors of 284 are 1, 2, 4, 71 and 142; so .

Evaluate the sum of all the amicable numbers under 10000.

Python

import functools
import operator

def l_factors(x):

    [ll, lh] = [[], []]

    for f in range(1, int(x ** (1/2.0)) + 1):
        if x % f == 0:
            ll.append(f)
            fp = x / f
            if fp != f:
                lh.append(int(fp))

    return ll + list(reversed(lh))

def is_prime(x):

    if x < 4:
        return True

    if x % 2 == 0:
        return False

    for fac in range(3, int(x ** (1/2.0)) + 1, 2):
        if x % fac == 0:
            return False

    return True

def v_sum(x):
    if len(x) < 1:
        return 0
    return functools.reduce(operator.add, x)
    
ans = 0
for a in range(1, 10000):
    if not (is_prime(a)):
        b = v_sum(l_factors(a)[:-1])
        if (a != b) and (a == v_sum(l_factors(b)[:-1])):
            ans += a
            
print(ans)
## 31626