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

Solution

Assumption: Both parts of the amicable pair must lie below the limit. If they straddle the limit then we ignore them.

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

Sieve Method for Finding Sum of Proper Divisors

import math
L = 10000
ds = [1]*L
for i in range(2, math.isqrt(L)):
    for j in range(i+1, L//i):
        ds[i*j]+= i+j

• L is set to 10,000, which is the limit up to which we are interested in finding amicable numbers.
• ds[] is a list initialized with 1s, where each index i will eventually contain the sum of proper divisors of i.

The nested loop calculates the sum of proper divisors for each number up to L:

1. The outer loop iterates over numbers i starting from 2 up to the square root of L. This ensures we only compute necessary divisors to avoid redundant calculations.
2. The inner loop iterates over multiples of i:
   • j starts from $i + 1$ and goes up to the largest integer j where $i \times j< L$.
   • For each pair of factors $(i,j)$, i and j are proper divisors of the product $i \times j$.
   • ds[i * j]+= i + j adds both i and j as divisors for $i \times j$, building up the sum of proper divisors for that product.

After this loop completes, ds[i] contains the sum of proper divisors for each integer i up to L.

Finding Amicable Pairs

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

• amicableNumbers[] is initialized as an empty list to store amicable pairs.
• The loop iterates through each number i from 2 up to L:
  • Condition 1: ds[i] < i checks that the sum of divisors of i (i.e., ds[i]) is less than i. This ensures we only consider each pair once, avoiding duplicates.
  • Condition 2: ds[ds[i]] == i checks that ds[i] and i are amicable. Specifically, if ds[i] is the sum of divisors of i, then ds[ds[i]] should return i for them to form an amicable pair.
  • If both conditions are True, ds[i] and i form an amicable pair, so [ds[i], i] is added to amicableNumbers[].

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 21

HackerRank extends the limit to $1\le N\le10^5$ and runs up to a thousand test cases in less than a second. This requires us to pre-calculate the sum of divisors.

Last Word