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.
https://projecteuler.net/problem=21
Wow, can numbers really be friendly with each other? Apparently, that’s a thing too. I guess amicable numbers are more like acquaintances than friends. Anyway, this problem builds on Euler #12, which asked for the number of divisors of a number. That, in turn, builds on Euler #3, which asks for the largest prime factor. The prime factorization of a number is intimately tied to this problem.
This problem is asking for the sum of proper divisors. We saw in Euler #12 how to count the proper divisors. Counting the proper divisors is easy – just add 1 to all of the exponents in the prime factorization then multiply them together. Summing the proper divisors is a bit more involved. The Cartesian product of all prime factors and their powers needs to be taken.
For example, 1800 has the prime factorization of 2^3 \times 3^2 \times 5^2. For each prime factor raised to a power a, create a set of descending exponents, i.e. (p^{a}, p^{a-1}, ..., p^1, p^0). Expanding 2^3 becomes (2^0, 2^1, 2^2, 2^3). Do this for all prime factors. 1800 now has the sets (1, 2, 4, 8), (1, 3, 9), and (1, 5, 25).
Taking the Cartesian product of these three sets returns all proper divisors including the number in question. This works because the Cartesian product produces all possible combinations of the sets. Imagine a number as a big Lego structure. The prime factorization deconstructs this structure down to its constituent bricks. The Cartesian product reassembles these bricks in various ways.
Some of the work has already been done. prime_factorization_with_exponents was written to assist in solving Euler #12. It returns a dictionary with prime numbers as keys and exponents as the values. Now, let’s write get_all_proper_divisors.
def get_all_proper_divisors(n): """Returns all proper divisors of n as a list e.g. 12 becomes [1, 2, 3, 4, 6]""" exponents = prime_factorization_with_exponents(n) sets = [] for prime in exponents: max_exponent = exponents[prime] sets.append([prime**exponent for exponent in range(0, max_exponent + 1)]) cartesian = product(*sets) return sorted([math.prod(group) for group in cartesian][0:-1]) # the last element is n itself
d(n) from the problem statement now can be written rather easily:
def find_sum_of_proper_divisors(n):
"""Returns the sum of all proper divisors of n"""
return sum(get_all_proper_divisors(n))
It’s straightforward to iterate through numbers up to a limit. The only gotcha here is perfect numbers. These numbers are equal to the sum of their proper divisors.
def find_amicable_numbers(n): """Returns all amicable numbers up to n as a list""" amicable_numbers = [] for i in range(n): if i in amicable_numbers: # Skip over numbers already known to be amicable continue amicable_candidate = find_sum_of_proper_divisors(i) if i != amicable_candidate: # Exclude perfect numbers if i == find_sum_of_proper_divisors(amicable_candidate): amicable_numbers.append(i) amicable_numbers.append(amicable_candidate) return amicable_numbers
The answer is now just sum(find_amicable_numbers(10000) which outputs 31626.