17. Amicable numbers

The obvious approach to this problem is to examine each pair of values between 1 and the maximum and see if the sums of their proper divisors equal each other. There are two problems with this method.

First, there are a lot of pairs of values. If the maximum number is 100,000, then there are 100,000 numbers that can be paired with 99,999 other numbers, making a total of 100,000 × 99,999 = 9,999,900,000, or almost 10 billion pairs to consider.

The second problem is that this technique would recalculate the sum of each value's divisors every time it considered that value. For 100,000 numbers, that means finding and adding divisors almost 20 billion times, once for both values in every pair.

To solve the first problem, you can change the question slightly. Instead of asking whether a pair is amicable, you could ask, for a given value, what other value would be its pair if it has one. For example, when you consider the value 123, you would add its divisors {1, 3, 41} to get 1 + 3 + 41 = 45. You would then examine the value 45 and add that number's divisors {1, 3, 5, 9, 15} to get 1 + 3 + 5 + 9 + 15 = 33. This result, 33, is not the original value, 123, so the two numbers 123 and 45 are not amicable.

This greatly reduces the number of calculations we need to make. Instead of examining almost 10 billion pairs, we only examine 100,000 values and their potential pairs, making this around 200,000 calculations instead of 20 billion.

We can even reduce the second problem somewhat by pre-calculating each number's sum of divisors. We know that we will need to calculate every value's sum at least once, so we won't be performing any extra calculations by pre-calculating those values. That will also allow us to avoid calculating the sum for the second value in each potential pair, so we save roughly half of those calculations.

These two enhancements give us the following method for finding amicable pairs:

// Find amicable numbers <= max.
private List<List<long>> FindAmicablePairs(long max)
{
    // Get the array of sums.
    long[] sums = GetSumsOfDivisors(max);

    // Look for pairs.
    List<List<long>> pairs = new List<List<long>>();
    for (int value = 1; value <= max; value++)
    {
        long sum = sums[value];
        if ((sum > value) && (sum <= max) && (sums[sum] == value))
        {
            List<long> pair = new List<long>();
            pair.Add(value);
            pair.Add(sums[value]);
            pairs.Add(pair);
        }
    }
    return pairs;
}

The method first calls the GetSumsOfDivisors method, which is described shortly, to build an array of every value's sum of divisors. It then loops through the values between 1 and the maximum number. For each value, the code looks up the value's sum of divisors to find its potential pair. It then compares the pair's sum with the current value. If the two match, then this is an amicable pair.

The code performs two other tests before it accepts the pair. First, it checks that the second value is greater than the original value. This prevents the code from deciding that a number is its own pair. (The definition of amicable numbers says that they are two different numbers.)

This test also ensures that we find each pair only once. For example, the program won't find the pair {220, 284} and then later find {284, 220}.

The second test also ensures that the second number in the potential pair is no greater than the maximum value. This guarantees that it is small enough to lie within the sums array, so we can look at its sum without causing an IndexOutOfRange exception.

The following code shows the GetSumsOfDivisors method:

// Calculate the sums of the divisors of numbers between 1 and max.
private long[] GetSumsOfDivisors(long max)
{
    // Make room for the sums.
    long[] sums = new long[max + 1];

    // Fill in the sums.
    for (long i = 1; i <= max; i++)
        sums[i] = GetProperDivisors(i).Sum();

    // Return the result.
    return sums;
}

This method creates an array to hold the sums and then loops through the values. It calls the GetProperDivisors method (which was used in the previous solution) for each value, adds the divisors, and saves the result in the sums array.

This technique is fast enough that the program can examine the first one million numbers for amicable pairs in just a few seconds. The two tricks here are to invert the problem so that we only need to examine the numbers once instead of looking at all of the pairs of numbers, and storing pre-calculated values so that we don't need to calculate them multiple times.

Download the AmicableNumbers example solution to see additional details.