Problem 23: Non-abundant sums

Problem:

Please find the problem here.

Solution:

As we have already explained in Problem 21, it is easy to tell if a number is abundant by computing the sum of proper divisor function. Since we are given that every number larger than 28123 can be written as sum of two abundant numbers, so we don't have to consider any of the abundant numbers larger than that.

So we first creating a set of all abundant numbers less than 28124 (turn out there are around 7,000 of them), then we create the set of all abundant number sums. Finally, we evaluate all the number below 28124 and test if they're sum of abundant number, that's all.

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

    internal static partial class Program
    {
        public static void Problem023()
        {
            List<int> abundantNumbers = new List<int>();
            for (int i = 2; i <= 28124; i++)
            {
                if (IsAbundantNumbers(i))
                {
                    abundantNumbers.Add(i);
                }
            }

            HashSet<int> abundantSums = new HashSet<int>();
            foreach (int abundantNumber1 in abundantNumbers)
            {
                foreach (int abundantNumber2 in abundantNumbers)
                {
                    abundantSums.Add(abundantNumber1 + abundantNumber2);
                }
            }

            long answer = (1 + 23) * 23 / 2;
            for (int i = 24; i < 28124; i++)
            {
                if (!abundantSums.Contains(i))
                {
                    answer += i;
                }
            }
            Console.WriteLine(answer);
        }

        private static bool IsAbundantNumbers(int i)
        {
            return SumOfProperDivisor(i) > i;
        }
    }
}

Note that the code reused the SumOfProperDivisor function in Problem 21.

Answer: 4179871