## Project Euler: Problem 14 – Longest Collatz sequence

#### Problem 14:

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

#### Idea:

Nothing jumped out at me other than using a brute-force method starting at 999,999. Implement the algorithm in the problem and keep track of the chain length, and when you find a longer chain, save the chain length and the starting number that generated it.

After solving, I realized the efficiency could be improved if I kept track of the chain lengths for each number below 1,000,000 and when the chain for a number landed on a previously encountered number, I just add that number’s chain length to the current chain length for the original number.

I.E.
16 = chain length of 4;
13 → 40 → 20 → 10 → 5 → 16 (stop, 16 is known)
4 (chain length of 16) + 6 (current chain length of 13) = 10 (chain length of 13)

However, even the brute-force method finished in under a second on my computer. While both memory and cpu cycles are in abundant supply (relatively), I see no point is making the problem harder than it needs to be.

```int answer = -1;
int chain = 0;

for(int i = 999999; i > 0; i--) {
int tmpChain = 1;
long tmp = i;
while(tmp > 1) {
if(tmp % 2 == 0) {//if even
tmp = tmp/2;
} else {         //if odd
tmp = (tmp*3)+1;
}
tmpChain++;
}
if(tmpChain > chain) {
chain = tmpChain;