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.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ProjectEuler_21
{
    internal class Program
    {
        private static int[] GetFactors(int num)
        {
            List factors = new List { 1, num };
            int root = (int)Math.Sqrt(num);

            for (int i = 2; i <= root; i++)
            {
                if (num % i == 0)
                {
                    factors.Add(i);
                    factors.Add(num / i);
                }
            }

            return factors.Distinct().OrderBy(i => i).ToArray();
        }

        private static int GetFactorsSum(int num)
        {
            int[] factors = GetFactors(num);
            int sum = 0;

            // don't include the actual num in the sum
            for (int i = 0; i < factors.Length - 1; i++)
            {
                sum += factors[i];
            }

            return sum;
        }

        private static void Main(string[] args)
        {
            Dictionary cache = new Dictionary();
            List amicableNumbers = new List();
            int amicableCount = 0;

            Stopwatch sw = new Stopwatch();
            sw.Start();
            for (int i = 9999; i > 0; i--)
            {
                int factorSum = 0;

                if (!cache.ContainsKey(i))
                {
                    factorSum = GetFactorsSum(i);
                    cache[i] = factorSum;
                }
                else
                {
                    factorSum = cache[i];
                }

                if (!cache.ContainsKey(factorSum))
                {
                    cache[factorSum] = GetFactorsSum(factorSum);
                }

                if (cache[factorSum] == i && i != factorSum)
                {
                    amicableCount++;
                    amicableNumbers.Add(i);
                    amicableNumbers.Add(factorSum);
                }
            }
            sw.Stop();

            amicableNumbers = amicableNumbers.Distinct().OrderBy(i => i).ToList();

            Console.WriteLine("Number of amicable numbers under 10000: {0}\r\nSum of amicable numbers: {2}\r\nAmicable Numbers: {3}\r\nElapsed time: {1} ms", amicableCount, sw.ElapsedMilliseconds, amicableNumbers.Sum(), string.Join(", ", amicableNumbers));
        }
    }
}