English Project Euler Problem 14 The Longest Collatz Sequence

English Project Euler Problem 14 The Longest Collatz Sequence

The following recurrence sequence is defined for positive integers:

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

By applying the above rule and starting from 13, we produce the following sequence:

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

It can be seen that this sequence, starting at 13 and ending at 1, contains 10 terms. Although it has not yet been proven (Collatz Problem), it is believed that all starting numbers will eventually arrive at 1.

Which starting number under one million produces the longest chain?

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