Find the sum of amicable numbers under 10000

Project Euler problem 21 is to find the sum of all amicable numbers under 10000. An amicable number is:

Let \(d(n)\) be the sum of proper divisors of \(n\) then \(d(a)=b\) and \(d(b)=a\) if \(a!=b\) then \(a\) and \(b\) are amicable numbers.

Brute force approach first in Python:

amicables = set()
# LIMIT is the value tested up to
LIMIT = 10000

def factorize(number):
    factors = []
    for i in range(1, number):
        if number % i == 0:

def amicable(a):
    # Let d(n) is the sum of proper divisors of n (less than n that
    # divide into n) d(a) = b and d(b)=a if a!=b then a and b are
    # amicable numbers.
    Da = sum(factorize(a))
    Db = sum(factorize(Da))
    if Db == Da:
        return None
    if Db == a:
        if Db > Da:
            return (Da, Db)
        return (Db, Da)

for value in range(1, LIMIT):
    test = amicable(value)
    if test != None:
for amicable in amicables:
    total = total + sum(amicable)

Gives the correct answer, so that’s a start.

Leave a Reply

Your email address will not be published.