Spoiler alert: This post contains spoilers for Project Euler.
Problem 14
Longest Collatz Sequence
Background
The Collatz Conjecture is famously easy to understand but a proof has eluded mathematics. The conjecture says that for any starting integer, the Collatz Sequence will eventually return to 1. This has been proven for all numbers up to
Approach
We'll visit each number less than 1,000,000 but, we don't need to calculate the full sequence if along the way we re-visit a number that we've seen before. A cache will allow us to store the sequence length for any numbers we've already come across.
For instance, imagine the next starting number is 8. Since 8 is even we divide by 2. The resulting 4 is a number we will have visited already. Instead of re-calculating the next steps (4 -> 2 -> 1), we look up cache[4] and see that the length was 3.
This helps to avoid a lot of unnecessary computation.
JS Solution
Conclusion
The number less than 1,000,000 with the longest Collatz sequence is . That sequence has a length of 525 steps.
The forums discuss a small speedup that I missed - it's not necessary to test any starting number less than 500,000.
Example: 400,000 cannot be the start of the longest sequence because doubling it gives 800,000 which is also under a million. The Collatz Sequence starting at 800,000 is exactly 1 step longer than the sequence that starts at 400,000.
Said another way: Every number less than 500,000 can be doubled and you'll find a sequence of exactly one more step in length.
It's also true that the starting number with the longest sequence is more likely to be odd than even for any given ceiling. That simply follows from the fact that odd numbers are tripled (and 1 is added) while even numbers are halved.
That's not a guarantee though, so we can't skip checking all of the even numbers.