How to speed up search for abundant numbers?

Question

Is there a way which this code could be improved so that it would run faster? Currently, this task takes between 11 and 12 seconds to run on my virtual environment

def divisors(n):
    return sum([x for x in range(1, (round(n/2))) if n % x == 0])

def abundant_numbers():
    return [x for x in range(1, 28123) if x < divisors(x)]

result = abundant_numbers()

Answer 1

Whenever you look for speeding up, you should first check whether the algorithm itself should change. And in this case it should.

Instead of looking for divisors given a number, look for numbers that divide by a divisor. For the latter you can use a sieve-like approach. That leads to this algorithm:

def abundant_numbers(n):
    # All numbers are strict multiples of 1, except 0 and 1 
    divsums = [1] * n  
    for div in range(2, n//2 + 1):  # Corrected end-of-range
        for i in range(2*div, n, div):
            divsums[i] += div  # Sum up divisors for number i
    divsums[0] = 0  # Make sure that 0 is not counted
    return [i for i, divsum in enumerate(divsums) if divsum > i]

result = abundant_numbers(28123)

This runs quite fast, many factors faster than the translation of your algorithm to numpy.

Note that you had a bug in your code. round(n/2) as the range-end can miss a divisor. It should be n//2+1.