Project Euler 21: Evaluate the sum of all amicable pairs under 10,000

Project Euler 21 Problem Description

Project Euler 21: 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.

Analysis

This problem’s description can lead to some confusion because we want to sum amicable numbers below some limit and not amicable pairs. For a limit of 10000 it’s no problem and most solutions add the pairs found and are quickly rewarded with a correct answer. But there is something nefariously hidden in this over simplified exercise. Let me fist show you a list of amicable numbers below 11000 from OEIS A259180:

220, 284, 1184, 1210, 2620, 2924, 5020, 5564, 6232, 6368, 10744, 10856

Well, for 10000 we can easily calculate pairs because both pairs of an amicable set are well below 10000. But what if we want amicable numbers below 5200? Most programs listed in the forum would fail to provide a correct answer because 5020 can only be found if its complement 5564 is also found and 5200 isn’t deep enough to find both.

A better method

To prevent this potential problem, we calculate sums of proper divisors for integers beyond the intended search limit to make sure we collect all the amicable numbers for a correct sum.

Here’s a solution that solves this dilemma, answers the more advanced HackerRank version of this problem, and provides a fast way to sieve the necessary sum of proper divisors.

Initialize a list, ds[], to all ones, L elements long and fill it by sieving the sum of proper divisors. The primary i loop only needs to reach the square root of L to stay within the limit (10000 in this case)

from math import sqrt
L = 10000
ds = [1]*L
for n in xrange(2, int(sqrt(L))):
	ds[n*n]+= n
for i in xrange(2, int(sqrt(L))):
	for j in xrange(i+1, L//i):
		ds[i*j]+= i+j

Filter from the list ds[] amicable pairs by appending ds[i] and i to the list an[]. Remember numbers qualify as amicable pairs if the meet the criteria: If d(d(a)) = a, where d(a) < a.
Adding a list ([ds[i], i]) to another list (an[]) is the same as appending.

an = []
for i in xrange(2, L):
	if ds[i] < i and ds[ds[i]] == i: an+= [ds[i], i]

Sum amicable numbers from the list an[] that are less than L1. Keep mindful of a reasonable search limit for the depth of sums of proper divisors before rehearsed.

L1 = int(input("Limit? "))
print "Amicable sum <",L1,"=", sum(a for a in an if a<L1)

The HackerRank Project Euler 21 version extends the limit fro 10,000 to 100,000 and runs up to a thousand trials at once in less than a second.

This program and method
solves all test cases for
Project Euler 21 on HackerRank

Project Euler 21 Solution

Afterthoughts

• Some other results