Project Euler Solution 21: Amicable numbers

This is part of the Project Euler series, this is about Problem 21: Amicable numbers. It is about numbers where the sum of the proper divisors of the sum of the proper divisors is the number itself.

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

First we need to get all the divisors of a number. For this we use the get_prime_factors function from Solution 5: Smallest multiple. Then we have the prime factors and their multiplicities. We need to build all possible products of these prime factors. For this I build up a tuple with (1, factor) for each factor that is contained there, including repetitions. I can then build all potential divisors by building the product of all these tuples and doing all possible combinations of either 1 or that factor. For this I use itertools.product.

def get_all_divisors(number: int) -> set[int]:
    prime_factors = get_prime_factors(number)
    pairs = [
        (1, factor)
        for factor, multiplicity in prime_factors.items()
        for _ in range(multiplicity)
    ]
    if not pairs:
        return {1}
    divisors = {
        functools.reduce(lambda a, b: a * b, combination)
        for combination in itertools.product(*pairs)
    }
    divisors.remove(number)
    return divisors

I need to remove the number itself, otherwise it wouldn't be the set of proper divisors.

Next I can just loop over all number up to 10,000 and check whether the divisor sum for the divisor sum is the same as the original number. And as the two number needs to be different, we also need to exclude these pairs.

def solution() -> int:
    divisor_sums = {
        number: sum(get_all_divisors(number)) for number in range(1, 10_000)
    }
    sum_of_amicable = 0
    for number, divisor_sum in divisor_sums.items():
        if divisor_sum >= 10_000:
            continue
        if divisor_sums[divisor_sum] == number and number != divisor_sum:
            sum_of_amicable += number
    return sum_of_amicable

That gets the solution in 328 ms, so it's fast enough.