# 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

## Leave a Reply