Project Euler #23 Non-abundant sums

Question

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<int> AbundantNumbers = new List<int>();
        for (int i = 12; i <= max; i++)
        {
            int abudantNumber = GetProperDivisor(i);
            if (abudantNumber > 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<int> results = new List<int>();

Next we have our algorithm that will determine whether a number can be written as sum of 2 abundant numbers :

        for (int i = 1; i < max; i++)
        {
            GetAbundantNumbers(i, AbundantNumbers);
            int count = allAbundantNumbers.Count(t => i != t);
            if (count == allAbundantNumbers.Count)
            {
                results.Add(i);
            }
        }

It will loop through all possible integers 1 - 28123 and check which one is valid by constantly updating the list allAbundantNumbers with new values, but only the ones that were previously not added, using the method GetAbundantNumbers :

    private static void GetAbundantNumbers(int input, IList<int> inputArray)
    {
        int ending = inputArray.IndexOf(input);
        if (ending == -1)
        {
            return;
        }
        for (int i = ending; i < ending + 1; i++)
        {
            for (int j = 0; j < ending + 1; j++)
            {
                if (!allAbundantNumbers.Contains(inputArray[i] + inputArray[j]))
                {
                    allAbundantNumbers.Add(inputArray[i] + inputArray[j]);
                }
            }
        }
    }

What we are doing here is we take the current integer as parameter (input) and we check if it's in the allAbundantNumbers list. If it's there we take the index of that, else we return that means we have already checked that number so no need of double checking. If we haven't met that number yet we start looping and add all possible sum's of that number and the previous abundant numbers.

        for (int i = ending; i < ending + 1; i++)
        {
            for (int j = 0; j < ending + 1; j++)
            {
                if (!allAbundantNumbers.Contains(inputArray[i] + inputArray[j]))
                {
                    allAbundantNumbers.Add(inputArray[i] + inputArray[j]);
                }
            }
        }

After we have updated our list of abundant numbers sums we count from how much sums the current integer is different :

int count = allAbundantNumbers.Count(t => i != t);

If it's different than all of the current values we add it to the list of valid results :

            if (count == allAbundantNumbers.Count)
            {
                results.Add(i);
            }

That's how the code works, it gives the correct result, however it's really slow, I'm looking forward for any refactoring/optimizations concerning the overall performance of the code also any code style errors should be noted. Here's the full code :

internal class Program
{
    private const int max = 28123;
    private static readonly List<int> allAbundantNumbers= new List<int>();
    private static void Main()
    {
        List<int> AbundantNumbers = new List<int>();
        for (int i = 12; i <= max; i++)
        {
            int abudantNumber = GetProperDivisor(i);
            if (abudantNumber > i)
            {
                AbundantNumbers.Add(i);
            }
        }
        List<int> results = new List<int>();
        for (int i = 1; i < max; i++)
        {
            GetAbundantNumbers(i, AbundantNumbers);
            int count = allAbundantNumbers.Count(t => i != t);
            if (count == allAbundantNumbers.Count)
            {
                results.Add(i);
            }
        }
        Console.WriteLine(results.Sum());
        Console.ReadKey();
    }

    private static void GetAbundantNumbers(int input, IList<int> inputArray )
    {
        int ending = inputArray.IndexOf(input);
        if (ending == -1)
        {
            return;
        }
        for (int i = ending; i < ending + 1; i++)
        {
            for (int j = 0; j < ending + 1; j++)
            {
                if (!allAbundantNumbers.Contains(inputArray[i] + inputArray[j]))
                {
                    allAbundantNumbers.Add(inputArray[i] + inputArray[j]);
                }
            }
        }
    }

    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;
    }
}

Answer 1

• 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<int> 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<int> allAbundantNumbers = new List<int>();

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<int>(
        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<int> abundantNumbers = new HashSet<int>();
    for (int i = 1; i <= max; i++)
    {
        int sumOfDivisors = GetSumOfProperDivisors(i);
        if (sumOfDivisors > i)
        {
            abundantNumbers.Add(i);
        }
    }

    List<int> results = new List<int>();
    for (int i = 1; i < max; i++)
    {
        if (!IsNumberTheSumOfTwoValuesInCollection(i, abundantNumbers))
        {
            results.Add(i);
        }
    }

    ... Assert.AreEqual(THE_SECRET_ANSWER, results.Sum());
}

private static bool IsNumberTheSumOfTwoValuesInCollection(int n,
     ICollection<int> 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;
}

Answer 2

I find it quite hard to follow your approach. There's a static field allAbundantNumbers which is updated by a static method GetAbundantNumbers whose variable names are virtually meaningless; this update method is called in a loop; and the contents of allAbundantNumbers are used each time round the loop. It would definitely help to have more meaningful names, and might also help if the accumulator (allAbundantNumbers, but should probably be called something like sums because it seems to contain sums of two abundant numbers) were passed into the update method and back out.

You asked about performance. There are a couple of basic observations:

1. Look at:

   int count = allAbundantNumbers.Count(t => i != t);
   if (count == allAbundantNumbers.Count)
   

   This could be rewritten as

   if (allAbundantNumbers.Any(t => i == t))
   

   which would be slightly more obvious, although no faster. However, if you change the type of allAbundantNumbers to one which permits fast membership tests (e.g. HashSet<int>) then there's a speedup available:

   if (allAbundantNumbers.Contains(i))
   

2. In the update method, you have

   if (!allAbundantNumbers.Contains(inputArray[i] + inputArray[j]))
   {
       allAbundantNumbers.Add(inputArray[i] + inputArray[j]);
   }
   

   Again, you're doing membership tests with a type which is worst-case for membership tests. (In fact, if allAbundantNumbers were a HashSet then the explicit Contains check would be unnecessary, although Add would still do an implicit one). But also note that you're accumulating larger sums than necessary. Since inputArray is sorted, you could break out of the inner loop once the sum exceeds max.

An approach which I would find easier to follow and which would be along the same lines as yours (nested loop) would be to ditch allAbundantNumbers entirely and replace it with a bool[1 + max]. Then loop over the sums as

var sumExists = new bool[1 + max];
for (int i = 0; i < AbundantNumbers.Count; i++)
{
    for (int j = i; j < AbundantNumbers.Count; j++)
    {
        var sum = AbundantNumbers[i] + AbundantNumbers[j];
        if (sum > max) break;
        sumExists[sum] = true;
    }
}

And then a simple loop over numbers from 1 to max can test whether the sum exists and if not can add it to a running total.