Optimize non-abundant sums algorithm

Question

I am trying to solve this Project Euler question:

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

My solution:

#returns a list of the divisors of a given number
def Divs(Number):
    Divisors = []

    for i in range(2 , int(Number**0.5) + 1):
        if Number % i == 0:
            Divisors.append(i)

    for q in range(len(Divisors)):
        if Divisors[q] != (Number / Divisors[q]):
            Divisors.append(Number / Divisors[q])

    Divisors.insert(0,1)
    return Divisors

#returns a list of abundant numbers up to and including the limit
def AbList(limit):
    Abundant = []

    for i in range(11,limit + 1):
        if sum(Divs(i)) > i:
            Abundant.append(i)

    return Abundant

#Finds the sum of all positive integers that cannot be written as the
#sum of two abundant numbers...
def AbSum(limit):
    Abundant = AbList(limit)
    NoAbSum = 0
    for i in range(1 , limit):
        AbSum = 0
        x = 0
        for x in Abundant:
            if i - x in Abundant[:i]:
                AbSum = 1
                break
        if AbSum == 0:
            NoAbSum += i
    return NoAbSum

This took my 3.4 GhZ processor about 15 minutes to solve and I am searching for a better way. I'm not concerned with the first two functions because together they take less than a second to run. The third function is the kicker here. It runs through the range of numbers up to the limit (in this case, 20000-something), and each time, it runs through the list of abundant numbers, subtracting each from the current number, then checking that answer against the list of abundant numbers. If there is a match, the loop breaks and tries again with the next number, all the way up to the limit.

I know there has got to be a better way of doing this but I'm somewhat new to programming. How can I speed up this algorithm?

Answer 1

You can use a simple mathematical trick: The sum of all numbers that can not be written as a sum of two abundant numbers is the sum of all numbers minus the numbers that can be written as a sum of two abundant numbers:

 solution = sum(range(limit)) - sum(all_two_sums(abundant_numbers))

(sum(range(limit)) can also be simplified with math, but you might not find it unless you're Gauss ;-))

You already have a list of abundant numbers, so it's relatively easy to create the set of numbers that can be written as the sum of two abundant numbers and where the sum is smaller than the limit. Just make sure you have no duplicate numbers, a Python set does that.

Answer 2

Let's start by searching a little bit, and find out the largest number not expressible as the sum of two abundant numbers is actually 20161. Then, we can solve the problem with a simple set membership test. Plus, it runs pretty fast. :-)

#!/usr/bin/env python
# -*- coding: utf-8 -*-
from math import sqrt

def d(n):
    sum = 1
    t = sqrt(n)
    # only proper divisors; start from 2.
    for i in range(2, int(t)+1):
        if n % i == 0:
            sum += i + n / i
    # don't count the square root twice!
    if t == int(t):
        sum -= t
    return sum

limit = 20162
sum = 0
# it's a set, after all. sets are faster than lists for our needs.
abn = set()
for n in range(1, limit):
    if d(n) > n:
        abn.add(n)
    # if the difference of the number we're examining and every number in the set
    # is in the set, then the number is the sum of two abundant numbers.
    # otherwise, we must add it to our sum in question.
    if not any( (n-a in abn) for a in abn ):
        sum += n

Runs in 0.6463340939061518 seconds on average on an i5, based on timeit.

Answer 3

You're testing every number between 1 and the limit (let's say 30000) against every abundant number, so you're doing roughly 30000 * 7428 iterations; and you're checking if the result is in a list, which is a very slow operation -- it checks every item on the list until it finds a match!

Instead, you should generate every number that is a sum of two abundant numbers. At the most, that would take 7428 * 7428 iterations -- fewer if properly executed (hint: avoid checking both a + b and b + a by ensuring that b is always >= a; and as someone else suggested, be sure to stop when sums get too large). Mark those numbers off a list of numbers below limit and sum the remaining numbers.

In other words:

[... 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43 ...]

becomes

[... 31, 0, 33, 34, 35, 0, 37, 0, 39, 0, 41, 0, 43 ...]

---

Edit: After playing with implementations for a few minutes, I can confidently say that if i - x in Abundant[:i]: is the problem. The first python solution posted to Project Euler's p23 forum is essentially a clever implementation of your algorithm, the only major difference being that it uses a set of abundant numbers instead of a list. It solves the problem on an Atom processor in 15 seconds; when I changed it to use a list, after fifteen minutes, it still hadn't solved the problem.

Moral of the story: x in list is SLOW.

Still, generating the sums directly is faster than subtracting and checking. :)