Project Euler #23 Non-abundant sums

I'm having trouble optimizing the Project Euler problem number 23 :

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

Here's some explanation of my code :

First we find and store all possible abundant numbers below 28123 because the maximum integer we are going to look for is 28123. It could be a little bit better if we write 28123 - 12 because that's the biggest combination we need to get anyway but I left it with 28123 so it's more readable.

private const int max = 28123;
List AbundantNumbers = new List();
        for (int i = 12; i  i)
            {
                AbundantNumbers.Add(i);
            }
        }

This is the method that returns the sum of all proper divisor of the current number :

private static int GetProperDivisor(int input)
    {
        int sum = 1;
        for (int i = 2; i <= input / 2; i++)
        {
            if (input%i == 0)
            {
                sum += i;
            }
        }
        return sum;
    }

Next we create a List that will hold our valid numbers (numbers that cant be written as sum of 2 abundant numbers)

```
List resu

• The performance issue you are experiencing is primarily because of this unnecessary operation in the loop:

GetAbundantNumbers(i, AbundantNumbers);

You have already calculated all abundant numbers up to 28123 already in the first loop in main. If you want to need to check against numbers less than a specific value (i.e. as an optimization), you can always apply a predicate / range check etc.

• The second loop, where you determine whether two numbers aren't the sum of two abundant numbers can be optimized. There is a bit of a trick here (other than checking just those abundant numbers less than your candidate value).

To check whether a number n is the sum of two abundants (can we call these two numbers x and y?), we need only check if the abundants collection contains both x and n - x. This is more easily expressed by refactoring and separating the determination of 'sum of two abundants' vs the adding them to the collection:

private static bool IsNumberTheSumOfTwoValuesInCollection(int n, 
     ICollection collection)
{
    foreach (var x in collection.Where(c => c < n))
    {
        if (collection.Contains(n - x))
        {
            return true;
        }
    }
    return false;
}

Some other feedback:

-
IMO it would be more correct to call the function GetProperDivisor as GetSumOfProperDivisors, and int abudantNumber = GetProperDivisor(i); would thus be more readable as int sumOfDivisors = GetSumOfProperDivisors(i)

-
Although 'correct' (in the sense that PE states this as fact), it feels a bit dirty to assume a starting value of 12 when looking for abundant numbers - starting from 1 won't really add much to the execution time.

-
You could consider replacing the brute forcing of all Proper Divisors of a number with a more efficient approach (although even the brute forcing will hardly noticable with an upperbound of 20k) e.g. as described here, which uses the permutations of all of the prime factors of the number.

-
Try choose the most appropriate data structure for holding data, e.g. for storage of values which are guaranteed to be unique, I would favour using a Hashset<> over a List<>

-
You'll probably want to extract a helper function to determine the 'abundance' of a number (i.e. Deficient, Abundant, or Perfect), as Perfect numbers crop up more than once on PE.

-
Similarly, I would extract a helper method to return the ProperDivisors of an number as IEnumerable (or HashSet) by itself - summing of proper divisors can be done as an afterthought by using .Sum() on the enumerable.

-
Some other code observations

You've split the declaration of th

private static readonly List allAbundantNumbers = new List();

away from its usage and population - I would move it to a local, and pass it as a parameter elsewhere.

Stylistic, but if you embrace LINQ, you can significantly reduce the LOC
e.g. How about this for the Abundant number generation :)

var allAbundantNumbers =
    new HashSet(
        Enumerable.Range(1, max)
            .Where(i => GetSumOfProperDivisor(i) == i));

Here's a non-LINQ refactoring:

private const int max = 28123;

private static void Main()
{
    HashSet abundantNumbers = new HashSet();
    for (int i = 1; i  i)
        {
            abundantNumbers.Add(i);
        }
    }

    List results = new List();
    for (int i = 1; i  collection)
{
    foreach (int x in collection.Where(c => c < n))
    {
        if (collection.Contains(n - x))
        {
            return true;
        }
    }
    return false;
}

private static int GetSumOfProperDivisors(int input)
{
    int sum = 1;
    for (int i = 2; i <= input / 2; i++)
    {
        if (input % i == 0)
        {
            sum += i;
        }
    }
    return sum;
}

StackExchange Code Review Q#124986, answer score: 3