Challenge 14: Longest Collatz Sequence

[andrew-field]

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.

[andrew-field]

I started with a brute force method. I now keep track of how many sequences can be skipped because the starting number has appeared in a previous sequence and hence the sequence that would be generated would be shorter than the current maximum. This currently skips about 70% of all the possible sequences.

This could be further improved by keeping a record of the length of the sequence generated from each number after it has been calculated for the first time to further reduce the number of repeat calculations.

[andrew-field]

My previous implementation kept track of how many sequences can be skipped because the starting number appeared in a previous sequence and hence the new sequence would be necessarily shorter. This was refactored to have a concurrent design and to make it simple/easy to read, though it no longer has this fine tuning and calculates every sequence. Still, the first half of all the sequences starting under 1'000'000 will appear as part of a longer sequence starting in the second half, so the first 50% can be skipped.