Problem 21: Amicable numbers

Problem:

Please find the problem here.

Solution:

Finally, we got another problem that feel like more number theoretic. A straightforward implementation would be checking, for each number i under 10000, if the SumOfProperDivisor(SumOfProperDivisor(i)) == i, and if so, add it to the sum, and that's all.

Therefore the problem becomes computing sum of proper divisor, turn out it is easier to consider the sum of divisor first. The sum of divisor, like the divisor function we encountered in problem 12, is multiplicative. Just like in proving the divisor function is multiplicative, we use the one to one correspondence between the a divisor of pq and the divisor of p, divisor of q pair. Now group the pairs by the first component we can see the sum and be factorized and we can see the sum of divisor function is multiplicative. The sum of divisor function for a prime power is simply a geometric series and is easily evaluated. 

The last twist in the problem is the SumOfProperDivisor(SumOfProperDivisor(i)) part. Turn out SumOfProperDivisor(i) can be larger than i (which are called abundant numbers), so we need to evaluate more SumOfProperDivisor(i) to its max to make sure we don't index out of bound.

Without further ado, here is the code:

namespace Euler
{
    using System;
    using System.Collections.Generic;
    using System.Linq;

    internal static partial class Program
    {
        public static void Problem021()
        {
            Dictionary<int, int> d = new Dictionary<int, int>();
            d.Add(1, 0);
            for (int i = 2; i <= 10000; i++)
            {
                d.Add(i, SumOfProperDivisor(i));
            }
            long maxSumOfDivisorWithin10000 = d.Values.Max();
            for (int i = 10001; i <= maxSumOfDivisorWithin10000; i++)
            {
                d.Add(i, SumOfProperDivisor(i));
            }
            Console.WriteLine(AmicableNumbers(d).Aggregate((x, y) => x + y));
        }

        private static IEnumerable<int> AmicableNumbers(Dictionary<int, int> d)
        {
            for (int i = 2; i <= 10000; i++)
            {
                if (d[d[i]] == i & i != d[i])
                {
                    yield return i;
                }
            }
        }

        private static int SumOfProperDivisor(int i)
        {
            return SumOfDivisor(i) - i;
        }

        private static int SumOfDivisor(int i)
        {
            var groupedFactors = BruteForceFactor(i).ToList();
            return groupedFactors.Select(kvp => (Power(kvp.Item1, kvp.Item2 + 1) - 1) / (kvp.Item1 - 1)).Aggregate((x, y) => x * y);
        }

        private static int Power(int x, int y)
        {
            if (y == 0)
            {
                return 1;
            }
            else if (y == 1)
            {
                return x;
            }
            else
            {
                int r = Power(x, y / 2);
                return y % 2 == 0 ? r * r : r * r * x;
            }

        }
    }
}

We could have optimized the factoring by eliminating trials using the Sieve_of_Eratosthenes. The idea is, instead of crossing out the number, we compute the power and store the information along. So at the end of the sieve, we got all factorizations we will need. It don't bother me to optimize right now as the performance of the previous code is fine.

Note that we reused the BruteForceFactor routine from problem 12.

Answer: 31626