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