Return to Answer

Another way to speed this up is to keep a record of all the sum of divisors seen so far in a dictionary (by using a caching decorator on the function, like functools.lru_cache) and realize that you only need a single loop if you make this a generator and use the fact that a number is amicable if \$d(d(a)) = a\$ and \$d(a) \neq a\$:

import math
from functools import lru_cache

@lru_cache(None)
def sum_div(n):
    # Taken from AJNeufeld's answer
    total = 1
    for x in range(2, int(math.sqrt(n) + 1)):
        if n % x == 0:
            total += x
            y = n // x
            if y > x:
                total += y
    return total

def amicable_numbers(limit):
    for a in range(limit):
        b = sum_div(a)
        if a != b and sum_div(b) == a:
            yield a
            yield b

print(sum(set(amicable_numbers(10000))))
    

This runs in a bit more than 4 milli-seconds on my computer.

Here I used a set to avoid double counting, but I also could have used the fact that amicable numbers always come in pairs by definition and divided the sum by two. But this could have run afoul if one half of the pair is above the limit. In other words, for limit = 250 it would have yielded the wrong result.

Another way to speed this up is to keep a record of all the sum of divisors seen so far (by using a caching decorator on the function, like functools.lru_cache) and realize that you only need a single loop if you make this a generator and use the fact that a number is amicable if \$d(d(a)) = a\$ and \$d(a) \neq a\$:

import math
from functools import lru_cache

@lru_cache(None)
def sum_div(n):
    # Taken from AJNeufeld's answer
    total = 1
    for x in range(2, int(math.sqrt(n) + 1)):
        if n % x == 0:
            total += x
            y = n // x
            if y > x:
                total += y
    return total

def amicable_numbers(limit):
    for a in range(limit):
        b = sum_div(a)
        if a != b and sum_div(b) == a:
            yield a

print(sum(amicable_numbers(10000)))
    

This runs in a bit more than 4 milli-seconds on my computer.

This runs in a bit more than 3 milli-seconds on my computer.

with Timer("amicable numbers"):
    print(sum(set(amicable_numbers(10000))))

This runs in a bit more than 4 milli-seconds on my computer.

with Timer("amicable numbers"):
    print(sum(set(amicable_numbers(10000))))
# XXXXX  # I don't want to give away the correct answer
# amicable numbers: 4.1ms

Another way to speed this up is to keep a record of all the sum of divisors seen so far in a dictionary (by using a caching decorator on the function, like [functools.lru_cache][1]) and realize that you only need a single loop if you make this a generator and use the fact that a number is amicable if \$d(d(a)) = a\$ and \$d(a) \neq a\$:

import math
from functools import lru_cache

@lru_cache(None)
def sum_div(n):
    # Taken from AJNeufeld's answer
    total = 1
    for x in range(2, int(math.sqrt(n) + 1)):
        if n % x == 0:
            total += x
            y = n // x
            if y > x:
                total += y
    return total

def amicable_numbers(limit):
    for a in range(limit):
        b = sum_div(a)
        if a != b and sum_div(b) == a:
            yield a
            yield b

print(sum(set(amicable_numbers(10000))))  # need `set` to avoid double counting
    

Here I used a set to avoid double counting, but I also could have used the fact that amicable numbers always come in pairs by definition and divided the sum by two. But this could have run afoul if one half of the pair is above the limit. In other words, for limit = 250 it would have yielded the wrong result. [1]: https://docs.python.org/3/library/functools.html#functools.lru_cache

Another way to speed this up is to keep a record of all the sum of divisors seen so far in a dictionary (by using a caching decorator on the function, like functools.lru_cache) and realize that you only need a single loop if you make this a generator and use the fact that a number is amicable if \$d(d(a)) = a\$ and \$d(a) \neq a\$:

import math
from functools import lru_cache

@lru_cache(None)
def sum_div(n):
    # Taken from AJNeufeld's answer
    total = 1
    for x in range(2, int(math.sqrt(n) + 1)):
        if n % x == 0:
            total += x
            y = n // x
            if y > x:
                total += y
    return total

def amicable_numbers(limit):
    for a in range(limit):
        b = sum_div(a)
        if a != b and sum_div(b) == a:
            yield a
            yield b

print(sum(set(amicable_numbers(10000))))
    

Here I used a set to avoid double counting, but I also could have used the fact that amicable numbers always come in pairs by definition and divided the sum by two. But this could have run afoul if one half of the pair is above the limit. In other words, for limit = 250 it would have yielded the wrong result.

As for timing the runtime, I usually either prefer using ipythons magic command %timeit, or writing a small context manager:

from time import perf_counter

class Timer:
    def __init__(self, name=""):
        self.name = name

    def __enter__(self):
        self.start = perf_counter()

    def __exit__(self, *args):
        runtime = perf_counter() - self.start

        # get it in nice units
        units = ["s", "ms", "μs"]
        for unit in units:
            if runtime > 1:
                break
            runtime *= 1000

        if self.name:
            print(f"{self.name}: {runtime:.1f}{unit}")
        else:
            print(f"{runtime:.1f}{unit}")

Which you can use like this:

with Timer("amicable numbers"):
    print(sum(set(amicable_numbers(10000))))

Note that this will not be more precise than micro-seconds due to the time it takes to run the context manager.