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.
Famous unsolved math problem here. Definitely gears toward not iterating through every single number and Collatz sequence. Key part of this algorthim is to keep track of the sequences of each number:
Consider the sequence above listed:
If we start at 26 for example,
26 results in the exact same sequence as 13, but we started from 26 instead. This is essence of this algorthim. We don't necessairly have to perform Collatz to every single number. If we hit a number that has generated a sequence, we can stop and keep track of the number of numbers in that particular sequence. For example, 13 results in 10. But, 26 would just be one more than that. However, the problem with this method is that we need to keep track of a lot of sequence. What's the maximum value in the Collatz? Not sure. What's the size of the array we must create? Not sure. I've seen to create some sort of brute force algorthim below... but still works!
Answer: 837799
Runtime: 30 seconds