Project Euler 21 Problem Statement

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 ab, 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

Project Euler 21: Amicable numbers pendantThis problem’s description can lead to some confusion because we want to sum amicable numbers – not amicable pairs – below some limit. 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.

By finding a fast way to sieve the sum of proper divisors we both solve this problem and he more challenging HackerRank version.

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

L = 10000
ds = [1]*L
for i in xrange(2, int(L**0.5)):
	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.

Note: 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)

HackerRank version

The HackerRank Project Euler 21 version extends the limit from 10,000 to 100,000 and runs up to a thousand test cases in less than a second.

Python 2.7 Source

Last Word

Some other results

Sum of amicable numbers < Limit (Pypy on Dell i5-3450)
Limit Run Time
Seconds
Result
104 0.008 31626
105 0.012 852810
106 0.042 27220963
107 0.975 649734295
108 15.6 11526067720
2 x 108 32.2 32292177807