Tag Info

This tag should be used for code related to the sequences described in the Collatz conjecture.

The Collatz conjecture states that, for any positive integer $n$, the sequence $a_0, a_1, a_2, \ldots$, where

• $a_0 = n$
• $a_{i+1} = \frac{a_i}{2}$ if $a_i$ is even
• $a_{i+1} = 3 a_i + 1$ if $a_i$ is odd

… will eventually lead to a cycle 1, 4, 2, 1, 4, 2, 1, …. However, no proof is known, and no counterexample has been found for $n \le 10^{18}$.

This tag is for questions related to such sequences.

These sequences are sometimes called "hailstone sequences" because they can cycle between small and sometimes surprisingly large values before eventually arriving at 1. For example, the Collatz sequence for $n = 159487$ contains a number exceeding $2^{31}$, and would overflow a signed 32-bit integer type.

Other names for the same problem include: 3n+1 problem, Hasse's algorithm, Kakutani's problem, Syracuse algorithm, Syracuse problem, Thwaites conjecture, and Ulam's problem.