Grind Report 23

Problem 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.

*WARNING: This contains the solution!*

When I first came to this problem I was not sure what approach I was going to use to solve it. I knew that I could use the sumofproperdivisors method from my problem 21 solution to check to see if a number is abundant or not. The real question was how would I know if a number could (and not) be expressed as the sum of two abundant numbers?

There are two ways to go about solving this problem.

1. Check every number and see if it can be written as the sum of two abundant numbers. (obvious approach).
2. For every abundant number, go though all abundant numbers and mark the sum of the two as a number that can be written as the sum of two abundant numbers.

My first attempt was the first way. I quickly realized that this was a huge waste of time because the abundant numbers would have to be checked several times for each number instead of only once per number. Needless to say, I moved to the second approach immediately after this discovery.

In addition to a list of abundant numbers, the second approach requires a list of all of the considered numbers. Once I to this point things became much clearer.

One issue I ran into while doing this problem is that my solution was kind of slow. It took about 20-30 seconds to find the answer, which is much longer than any of my previous solutions. After some analysis I realized that my implementation was somewhat flawed. My collection of abundant numbers was a map, which when I started made some sense, but my final solution it was completely unnecessary. When I changed it from a map to a vector it went down to about 4-5 seconds to find the answer. Much better :)

Here is my solution. I changed the sumofproperdivisors method a little and so it should be slightly faster now.

#include <iostream>
#include <vector>

using std::vector;
using std::cout;

const int MAX = 28123;

int sumofproperdivisors(int n);

int main()
{
 bool numbers[MAX + 1];
 vector<int> abundants;
 for (int i = 1; i <= MAX; ++i)
 {
  //check to see if the number is abundant
  if (sumofproperdivisors(i) > i)
  {
   //add to the list of abundant numbers
   abundants.push_back(i);
   //go through all abundant numbers and mark off the sum of the two
   for (int j = 0; j < abundants.size(); ++j)
   {
    //break if the sum of the abundant numbers is larger than the MAX
    if (i + abundants[j] > MAX)
     break;
    numbers[i + abundants[j]] = false;
   }
  }
 }

 //go through all of the numbers and add up the ones that
 //cannot be expressed as the sum of two abundant numbers
 long answer = 0;
 for (int i = 1; i <= MAX; ++i)
  if (numbers[i])
   answer += i;
 cout << answer;
}

int sumofproperdivisors(int n)
{
 int sum = 0;
 //determine how much to increment by each
 int increment = n % 2 + 1;
 //iterate through all numbers that are less than the sqrt(n)
 //since i * i is the largest the smallest of the two can be
 for (int i = 1; i * i <= n; i += increment)
 {
  //if n is evenly divisible then add i and the other number (n / i)
  //so that i * (n / i) = n
  if (!(n % i))
  {
   sum += i;
   //add the larger divisor unless i is the square of n (avoid duplication)
   if (i * i != n)
    sum += n / i;
  }
 }
 //remove n since it was added when i == 1
 sum -= n;
 return sum;
}

*saved game*