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.

Running time: 140ms

Assessment: Like some of the other problems, I had to read this a few times before I really understood it.

import java.util.ArrayList;
import java.util.Iterator;

public class Problem021
{
	private static int MSum;
	private static int NSum;
	
	private static int sumList(ArrayList<Integer> list)
	{
		int sum = 0;
		
		for (Iterator<Integer> iter = list.iterator(); iter.hasNext();)
		{
			sum += iter.next();
		}
		
		return sum;
	}
	
	private static ArrayList<Integer> createList(int n)
	{
		// Creates a list of integers that evenly divide into n excluding n itself
		long root = Math.round(Math.sqrt(n)) + 1;

		ArrayList<Integer> test = new ArrayList<Integer>();
		test.add(1);
		
		for (int i = 2; i <= root; i++)
		{
			if (n % i == 0)
			{
				test.add(i);		// Add the divisor & its complement
				test.add(n/i);
			}
		}
		
		return test;
	}
	
	private static boolean isAmicable(int n)
	{
		/*** If n's divisors form an amicable set, return true ***/

		// Create a list of n's proper divisors
		ArrayList<Integer> NList = new ArrayList<Integer>(createList(n));		
		
		// Sum n's proper divisors (NSum)
		NSum = sumList(NList);
		
		// Create list of NSum's proper divisors (MList)
		ArrayList<Integer> MList = new ArrayList<Integer>(createList(NSum));
		
		// Sum m's proper divisors (MSum)
		MSum = sumList(MList);
		
		if ((MSum == n) && (MSum != NSum))
			return true;	
		
		return false;
	}
	
	public static void main(String[] args)
	{
		long begin = System.currentTimeMillis();
		
		int sum = 0;
		for (int i = 0; i < 10000; i++)
		{
			if (isAmicable(i))
			{
				sum += NSum;
			}
		}
		
		System.out.println(sum);
		
		long end = System.currentTimeMillis();
		System.out.println(end-begin + "ms");
	}
}