# Abundant numbers

Published on 2011-07-28An abundant number is any number `n`

whose proper divisors (the integers less than `n`

by which `n`

can be evenly divided) are greater in sum than the number itself. Problem 23 asks the reader to find the sum of all numbers that cannot themselves be expressed as the sum of two abundant numbers. This includes all numbers below twenty-four (2×12, the latter being the smallest abundant number) and **no** numbers below 28,123. The latter tidbit is according to the problem text, though it has been shown that the largest number not expressible as the sum of two abundant numbers is actually 20,161.

My approach to this problem was to construct an array containing all numbers one through 20,161 and a list of all abundant numbers. I then used nested `foreach`

loops, each iterating over my list of abundant numbers to find all numbers under 20,162 that could be expressed as the sum of two abundant numbers. My first implementation featured a *list* of all integers below 20,162 from which I removed all sums of two abundant numbers, but the .Remove() method turned out to be incredibly slow. I replaced the list with an 20,162-member array in which all members were set to their index (e.g., array[21] = 21, array[935] = 935, etc.), and for every sum of two abundant numbers I found, I set the array member at that index to zero. This was considerably zippier, and I found the sum of all numbers not expressible as the sum of two abundant numbers by adding together all members of the array: those that did not meet the condition had been set to zero and thus did not affect the sum.

using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Problem023 { class Program { static void Main(string[] args) { List<int> abundantNumbers = new List<int>(); int[] possibleAnswers = new int[20162]; int divisors = 1; possibleAnswers[0] = 0; for (int i = 1; i < possibleAnswers.Length; i++) { possibleAnswers[i] = i; } for (int i = 2; i < possibleAnswers.Length; i++) { for (int j = 2; j <= Math.Sqrt(i); j++) { if (j == Math.Sqrt(i)) { divisors += j; break; } else if (i % j == 0) divisors += j + (i / j); } if (divisors > i) { abundantNumbers.Add(i); } divisors = 1; } foreach (int n in abundantNumbers) { foreach (int m in abundantNumbers) { if (n + m > possibleAnswers.Length - 1) break; else possibleAnswers[n + m] = 0; } } int runningTotal = 0; foreach (int n in possibleAnswers) runningTotal += n; Console.WriteLine("The sum of all numbers not expressible" + " as the sum of two abundant numbers is {0}", runningTotal); } } }