Skip to content
August 10, 2011 / oop123

Project Euler #95 – Java

You can see the problem here: Problem #95.

Since I am getting stuck on one of Project Euler’s problem (a bug somewhere I can’t find), I decided to find another (an easy) problem to do – voila, problem 95.

Part 1: Getting the number’s sum of divisors

This is very easy: just use a sieve to accumulate the sums.

final int SIZE = 1000000;

//initialize all the sums
int[] sums = new int[SIZE + 1];
Arrays.fill(sums, 1);
for (int i = 2; i <= SIZE / 2; i++) {
	for (int j = i + i; j <= SIZE; j += i) {
		sums[j] += i;
	}
}

Part 2: Solving the problem

A dynamic programming approach to this problem makes solving it a breeze. First, we create an integer array chainNum to store any calculated amicable chain lengths. chainNum can also store -1s to indicate a number cannot form a chain. Then we just loop from 1 to 1,000,000 and attempt to make an amicable chain with each number. If we found a number cannot form an amicable chain, we will update the corresponding index in chainNum with -1. Also, when we found an amicable chain, chainNum will be updated accordingly with the chain’s length.

//***** initalize chainNum *****
//-1 means no chain exists for the number
//0 means we haven't calculated the chainNum yet
int[] chainNum = new int[SIZE + 1];
chainNum[1] = -1;
chainNum[2] = -1;
chainNum[3] = -1;
chainNum[4] = -1;

//***** finding all the chainNum *****
for (int i = 5; i <= SIZE; i++) {
	if (chainNum[i] != 0) continue; //skip numbers that has been tested
	List<Integer> chain = new ArrayList<Integer>();
	chain.add(i);
	int next = sums[i];

	while (true) {
		//if the chain fails, update chainNum
		if (next > SIZE || chainNum[next] != 0) {
			for (Integer n : chain) chainNum[n] = -1;
			break;
		}

		//if the a chain is found, update chainNum
		int index = chain.indexOf(next);
		if (index >= 0) {
			//there may be numbers that leads to the chain but is not actually contain by the chain
			for (int j = 0; j < index; j++) chainNum[chain.get(j)] = -1;
			for (int j = index; j < chain.size(); j++) chainNum[chain.get(j)] = chain.size();
			break;
		}

		chain.add(next);
		next = sums[next];
	}
}

//***** just search for the largest chain number *****
int answer = 0;
int largest = 0;
for (int i = 2; i <= SIZE; i++) {
	if (chainNum[i] > largest) {
		largest = chainNum[i];
		answer = i;
	}
}
System.out.println(answer);

Runs in around 800 milliseconds on my computer. Surprisingly easy. CU

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: