Project Euler

Problem 21: Amicable Numbers

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.

The Catch

How to find the sum of divisors of an arbitrary number x.
How to check whether a number is amicable.

The Light

Utilize the concept of finding divisors discussed in Problem 12, find the sum of all divisors. Note that the problem asks for proper divisors, which means the set of all divisors except the number itself.

The set of divisors of 8 is {1, 2, 4, 8}. The set of proper divisors of 8 is {1, 2, 4}.

Loop from 1 to 10,000. For each iteration, find the sum b of all divisors of a number n. If the sum b is greater than the number n and less than 10,000, then the number n can have its amicable pair. Treating b as another number, find the sum a of all divisors of b and if a is the same as n, then n and b are an amicable pair.

For example, while looping from 1 to 10,000, one of the iteration is the number n = 220.
Let b be the sum of all divisors of the number n, so b = 284.
Then let a be the sum of all divisors of b, so a = 220. Since a = n = 220, n and b must be an amicable pair.

The Code

public class Problem21
{
  public static void main(String[] args)
  {
    int amicableSum = 0;
	
    for(int n = 1; n < 10000; n++)
    {
      int b = sumDiv(n);
      if(b > n && b < 10000)
      {
        int a = sumDiv(b);
    	if(a == n)
    	  amicableSum = amicableSum + n + b;
      }
    }
	
    System.out.println("Amicable sum = " + amicableSum);
  }
  
  public static int sumDiv(int n)
  {
    int sum = 1; //1 is a proper divisor for all numbers
	
    for(int i = 2; i * i <= n; i++)
    {
      if(n % i == 0)
        sum = sum + i + n/i;
    }
    return sum;
  }
}