Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

history | excerpt history