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:

solutions.problem21.solve()