Project Euler #23 Optimization [Python 3.6]

Question

I'm having trouble getting my code to run quickly for Project Euler Problem 23. The problem is pasted below:

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.

And my code:

import math
import bisect
numbers = list(range(1, 20162))
tot = set()
numberabundance = []
abundant = []
for n in numbers:
    m = 2
    divisorsum = 1
    while m <= math.sqrt(n):
        if n % m == 0:
            divisorsum += m + (n / m)
        m += 1
    if math.sqrt(n) % 1 == 0:
        divisorsum -= math.sqrt(n)
    if divisorsum > n:
        numberabundance.append(1)
    else:
        numberabundance.append(0)
temp = 1
# print(numberabundance)
for each in numberabundance:
    if each == 1:
        abundant.append(temp)
    temp += 1
abundant_set = set(abundant)
print(abundant_set)
for i in range(12, 20162):
    for k in abundant:
        if i - k in abundant_set:
            tot.add(i)
            break
        elif i - k < i / 2:
            break
print(sum(numbers.difference(tot)))

I know the issue lies in the for loop at the bottom but I'm not quire sure how to fix it. I've tried modeling it after some of the other answers I've seen here but none of them seem to work. Any suggestions? Thanks.

StuartLC · Accepted Answer · 2018-01-07T12:23:23.643

Your upper bound is incorrect - the question states all integers greater than 28123 can be written ..., not 20162

After changing the bound, generation of abundant is correct, although you could do this generation in a single pass by directly adding to a set abundant, instead of creating the bitmask array numberabundance.

The final loop is also incorrect - as per the question, you must

Find the sum of all the positive integers

whereas your code

for i in range(12, 20162):

will skip numbers below 12 and also doesn't include the correct upper bound.

I'm a bit puzzled about your choice of

elif i - k < i / 2:

Since the abundants are already sorted, I would just check if the inner loop had passed the midpoint of the outer loop:

if k > i / 2:

Also, since we just need the sum of these numbers, I would just keep a running total, instead of having to do a final sum on a collection.

So here's the result after making the above changes:

import math
import bisect
numbers = list(range(1, 28123))
abundant = set()

for n in numbers:
    m = 2
    divisorsum = 1
    while m <= math.sqrt(n):
        if n % m == 0:
            divisorsum += m + (n / m)
        m += 1
    if math.sqrt(n) % 1 == 0:
        divisorsum -= math.sqrt(n)
    if divisorsum > n:
        abundant.add(n)
#print(sorted(abundant))
nonabundantsum = 0
for i in numbers:
    issumoftwoabundants = False
    for k in abundant:
        if k > i / 2:
            break

        if i - k in abundant:
            issumoftwoabundants = True
            break

    if not issumoftwoabundants:
        nonabundantsum += i

print(nonabundantsum)

Example here

Also, since you've tagged a modern Python version, you'll also be able to replace the imperative loops with the [FP map, reduce, filter](https://stackoverflow.com/questions/13638898/how-to-use-filter-map-and-reduce-in-python-3) approach which will reduce code line count. — StuartLC, Jan 07 '18 at 08:53
On the upper bound, I read somewhere that the actual upper bound for numbers was 20161 instead of 28123 so I hoped that would speed things up a bit. These optimizations got me under the one minute mark. Thanks for the advice. — Nolan Wheeler, Jan 07 '18 at 17:35

Project Euler #23 Optimization [Python 3.6]

1 Answers1