Amicable chains

by Gilbert Keith

Today’s problem:

The proper divisors of a number are all the divisors excluding the number itself. For example, the proper divisors of 28 are 1, 2, 4, 7, and 14. As the sum of these divisors is equal to 28, we call it a perfect number.

Interestingly the sum of the proper divisors of 220 is 284 and the sum of the proper divisors of 284 is 220, forming a chain of two numbers. For this reason, 220 and 284 are called an amicable pair.

Perhaps less well known are longer chains. For example, starting with 12496, we form a chain of five numbers:

12496 → 14288 → 15472 → 14536 → 14264 (→ 12496 → …)

Since this chain returns to its starting point, it is called an amicable chain.

Find the smallest member of the longest amicable chain with no element exceeding one million.

Solution:

This one wasn’t so elegant; I tried as much as possible to be smart about the computation needed, but I missed some spots. This runs in 5 seconds, well within the time limits, but still could be better, I think.

import java.util.ArrayList;

public class Problem95 {
	static long begin = System.currentTimeMillis();
	//cache sum of divisors as you calculate them;
	static int[] DivisorSums = new int[1000000];
	//create an array of primes
	//we know that the sum of the proper factors for these is 1 anyway;
	static boolean[] arrOfPrimes = PrimeGen.genPrimeArr(1000000);
	//longestList will cache the longestList at any extent of the run;
	static ArrayList longestList  = new ArrayList();
	static long end;

	public static void main(String[] args) {

		//loop over 2 <= i < 1000000
		for (int i = 2; i < 1000000; i++) {
			boolean done = false;
			//cache i into "nextVal";
			int nextVal = i;
			//Add the list of numbers in the cycle to an arrayList.
			ArrayList arrList = new ArrayList();
			arrList.add(nextVal);
			while (!done)  {
				//cache nextVal once; this is useful if you run into a perfect number;
				int cachedNextVal = nextVal;
				nextVal = findNextVal(nextVal);
				//if nextVal is prime or if nextVal
				//is a perfect number break out;
				if ((nextVal == 0) || (nextVal == cachedNextVal)) break;
				//if nextVal was what we started with
				//then we have finished a true cycle;
				if (nextVal == i) {
					done = true;
					break;
				}
				//if nextVal is already found in the arrayList
				//eg. if you are going to cycle across a couple of
				//amicable numbers, then break;
				//example: if I = 562 or I = 1064;
				if (arrList.contains(nextVal)) break;
				//add nextVal to arrList;
				arrList.add(nextVal);
			}
			//if done never got set to true (never finished true
			//cycle) clear out the temp list of numbers
			if (!done) arrList.clear();
			// if arrList is larger in size than the longestList
			//clear out LongestList and set it equal to arrList;
			if (arrList.size() > longestList.size()) {
				longestList.clear();
				longestList.addAll(arrList);
			}
		}
		//print answer;
		System.out.println("Members of longest list - Size: "+  longestList.size());
		for (int i: longestList) {
			System.out.println("I: " + i);
		}
		end = System.currentTimeMillis();
		System.out.println("Time: " + (end-begin) + " ms");
	}

	public static int findNextVal(int i) {
		//if prime return 0
		if (arrOfPrimes[i]) return 0;
		//if we have already cached the sum of divisors, return it;
		if ((DivisorSums[i] > 0) && (DivisorSums[i] < 1000000)) return DivisorSums[i];
		//if we haven't cached it
		if (DivisorSums[i] == 0) {
			//one is always a factor, so start with a sum of 1;
			int factorSum = 1;
			//loop until you have hit all the factors unti sqrt(i)
			for (int j = 2; j * j <= i; j++) { 				//if I is divisible by j 				if (i % j == 0) { 					//if j is the square root of i, only add it once; 					if (((i/j) == j)) { 						factorSum += j; 					} 					//else add j and (i/j) 					else { 						factorSum += (j + (i/j)); 					} 				} 			} 			//if factorSum is larger than 1000000 then return 0 			//since we only care about cycles where all #s are  			//below one million. 			if (factorSum > 1000000) return 0;
			//cache the factorSum;
			DivisorSums[i] = factorSum;
			//return it;
			return factorSum;
		}
		//if we don't hit any of the above situations,
		//return zero (shouldn't hit, but a sanity check);
		return 0;
	}
}
Advertisements