Problem C
Hailstone Sequences

Given an integer $n$, its hailstone sequence is constructed in the following way. First, the integer $n$ is itself added as the first number of the sequence. The following procedure is then repeated. If the last integer $a$ added to the sequence is even, we add $\frac{a}{2}$ to the sequence. If it is odd, we add $3a + 1$ to the sequence. Whenever the integer $1$ is added to the sequence, the procedure concludes and the sequence generated is the hailstone sequence of $n$.

For example, with $n = 7$, we get the sequence

\[ 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 \]

This has length $17$.

It is unknown if the hailstone sequence is finite for every positive integer $n$. Proving whether this is the case or not is known as the $3n + 1$ problem, or the Collatz conjecture. It has been proven that the longest sequence among all $n \le 10^{12}$ has length 1349.

Given an integer $n$, determine the length of its hailstone sequence.


The input consists of an integer $n$ ($1 \le n \le 10^{12}$).


Output a single integer – the length of the sequence.

Sample Input 1 Sample Output 1
CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in