Project Euler Problem 21 Solution

Project Euler & HackerRank Problem 21 Solution

Amicable numbers
by {BetaProjects} | MAY 17, 2009 | Project Euler & HackerRank

Project Euler Problem 21 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 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 add 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 an accepted answer. But there is something nefariously hidden in this over simplified exercise. Let me first 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 Project Euler forum would fail to give a correct answer because 5020 can only be found if its complement 5564 is also found and a search limit of 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 answer. An amicable pair that exceed our search limit is considered suitable.

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

We begin by initializing 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 our limit, L (11000 in this case – enough to find the next pair outside our limit of 10000).

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

Then, filter from the list, ds[], amicable pairs by appending ds[i] and i to the list an[]. Remember, for numbers to qualify as amicable pairs they must meet the criteria 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 range(2, L):
    if ds[i] < i and ds[ds[i]] == i: an+= [ds[i], i]

Finally, sum amicable numbers from the list an[] that are less than N. Keep mindful of a reasonable search limit for the depth of sums of proper divisors long since rehearsed.

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

HackerRank version

HackerRank extends the limit from N<10,000 to 1≤N≤100,000 and runs up to a thousand test cases in less than a second. This requires us to pre-calculate the sum of divisors to a limit where both numbers of an amicable pair exceed 100,000.

Python Source Code

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