Grind Report 21

Problem 21

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).

If d(a) = b and d(b) = a, where a != b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

*WARNING: This contains the solution!*

By now I am pretty comfortable working with divisors and prime numbers. The proper divisors are just the divisors minus the number itself. So basically all we had to do was find and add up all of the divisors and then subtract the number to get the proper divisors. Easy enough!

There are two way to speed up this algorithm of obtaining the sum of the proper divisors. One we already have encountered a few times, which is that the highest value we need to look at is the square of the number. This is because all divisors numbers greater than the square of the number can be determined using the lower divisors, which is simply the number divided by the lower divisor.

The other trick is that if the number is odd then all divisors must be odd, therefor only odd numbers need to be considered. This little trick actually cuts off 1/4 of the algorithm and is really easy to implement. This was a quick and simple solution.

#include <iostream>
#include <math.h>

using std::cout;

const int TARGET = 10000;

int sumofproperdivisors(int n)
{
 int sum = 0;
 //calculate the square of n
 int square = sqrt((float)n);
 //determine how much to increment by each
 int increment = n % 2 + 1;
 //iterate through all numbers that are less than the sqrt(n)
 //since n * n is the largest the smallest of the two can be
 for (int i = 1; i <= square; 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 the i == n / i (which would mean i == square)
   if (i != square)
    sum += n / i;
  }
 }
 //remove n since it was added when i == 1
 sum -= n;
 return sum;
}

int main()
{
 int amicablesum = 0;
 for (int i = 4; i < TARGET; ++i)
 {
  int b = sumofproperdivisors(i);
  //determine if it is a new amicable pair
  //standard check plus since i != b this means that every pair
  //will be encountered twice so simply only accept one of them (aka i > b)
  if (sumofproperdivisors(b) == i && i != b && i > b)
   amicablesum += i + b; //add the pair to the total sum
 }
 cout << amicablesum;
}

*saved game*