Amicable Numbers

Question

I am struggling with optimizing these functions that I have used to calculate the sum of the amicable pairs under 10000. An amicable pair is a pair (a, b) where the sum of the divisors of "a" excluding "a" itself equals b and the sum of the divisors of "b" excluding "b" itself equals "a".

I.e. divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110: The sum of which is 284. And the sum of the divisors of 284 (1, 2, 4, 71 and 142) equals 220.

My code is:

import math
def Divisorsbaritself(x):
    divList = [1]
    y = 2
    while y <= math.sqrt(x):
        if x % y == 0:
            divList.append(y)
            divList.append(int(x / y))
        y += 1
    return sum(divList)

def amicable():
    solution = []
    for i in range(10000):
        if Divisorsbaritself(Divisorsbaritself(i)) == i:
            solution.append(i)
    return sum(solution)

print amicable()

I need help with understanding why the amicable function is not working. To me it makes logical sense that the if Divisorsbaritself(Divisorsbaritself(i)) == i: condition is the right condition to include i in the list, but it is giving me 40285, rather than 31626, the answer.

Answer 1

If Divisorsbaritself(i)==i you shouldn't count i.

def amicable():
    solution = []
    for i in range(10000):
        if Divisorsbaritself(i)!=i and Divisorsbaritself(Divisorsbaritself(i)) == i:
            solution.append(i)
    return sum(solution)

But you should also fix the bug that would be an issue if i is a perfect square and in an amicable pair.

You can improve this with list comprehensions.

def amicable():
    solution = [i for i in xrange(10000) if Divisorsbaritself(i)!=i and Divisorsbaritself(Divisorsbaritself(i)) == i]
    return sum(solution)

Answer 2

They're amicable numbers only if they're different. So if divsum(i) is equal to i, then that's not included, despite the fact that means that divsum(divsum(i)) also equals i.

In addition, your current check counts the square root of a perfect square twice, even though it's only one factor.

And, on top of that, I wouldn't be using a list then summing it at the end when you can simply use an accumulator. And it's usually faster to do multiplication than square roots so you can change the while loop to take that into account.

Finally, for the love of whatever deities you believe in, comment your code! It'll make it so much easier to understand what's going on, both for others and for yourself six months down the track.

Incorporating those changes gives you the following DivisorsBarItself function:

def DivisorsBarItself(num):
    # Maintain sum of factors.

    divSum = 1

    # Go through every integer up to but excluding sqrt(num).

    testnum = 2
    while testnum * testnum < num:
        # If factor, add it and the complement (guaranteed integer).

        if num % testnum == 0:
            divSum += testnum + num/testnum
        testnum += 1

    # If perfect square, add the square root once.

    if testnum * testnum == num:
        divSum += testnum

    # Return the sum.

    return divSum

Fixing the logic for detecting amicable numbers and using a sum rather than a list gives you:

def AmicableSum():
    # Set sum to zero and process all numbers below 10,000.

    solution = 0
    for num in range(10000):
        # Get the "friend", add only if different and f(f(x)) = x.

        numFriend = DivisorsBarItself(num)
        if numFriend != num and DivisorsBarItself(numFriend) == num:
            solution += num

    return solution

print AmicableSum()

which gives the correct result of 31626.