Project Euler Problem 21: Amicable Numbers

The source code for this problem can be found here.

Problem Statement

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 \neq 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\).

Solution Discussion

Pre-compute \(d(n)\) for all \(n\) in our search space and then iterate over \(n\) searching for \(d(n) = m\) and \(d(m) = n\) where \(n \neq m\). Compute the sum of all such \((n, m)\).

Note

the pre-computation of \(d(n)\) for an increasing \(n\) can be drastically sped up by using sieving techniques. An alternative, but inferior, method would be to find the divisors of increasing values of \(n\) via factorisation.

Solution Implementation

from lib.numbertheory.sieve import divisors_sieve


def solve():
    """ Compute the answer to Project Euler's problem #21 """

    # Pre-compute d(n) for all n in [2, 9999]
    target = 10000
    divisor_counts = divisors_sieve(target - 1, proper=True, aggregate="sum")
    d_vals = {n + 1: div_count for n, div_count in enumerate(divisor_counts)}
    del d_vals[1]  # divisors_sieve covers the closed interval [1, target - 1], remove d(1)

    # Identify amicable numbers
    amicable_numbers = set()
    for n, d_n in d_vals.items():
        if d_n in d_vals and d_vals[d_n] == n and n != d_n:
            amicable_numbers.add(n)
            amicable_numbers.add(d_n)

    # Sum all amicable numbers
    answer = sum(amicable_numbers)
    return answer


expected_answer = 31626
solutions.problem21.solve()

Compute the answer to Project Euler’s problem #21