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