Questions tagged [collatz-conjecture]

The Collatz conjecture asserts that every positive integer, when iterated over the function:

$$ f(n) = \begin{cases} \frac n2 & \text{if $n$ is even} \\\ 3n+1 & \text{if $n$ is odd} \end{cases} $$

will eventually be transformed to the cycle $1 \to 4 \to 2 \to 1$.

For example, $7 \to 22 \to 11\ \to 34 \to 17 \to 52 \to 26 \to 13 \to 40 \to \dots \to 5 \to 16 \to \dots \to 1$.

The Collatz conjecture has been verified for $n\le 19\cdot 2^{58}$ [Mathworld].

It may be generalized in multiple ways:

• One way is to increase the domain on which it is defined, for example to the integers or real numbers. In the former case, it is conjectured that it eventually reaches one of $4$ cycles:

  1. $1 \to 4 \to 2 \to 1$,
  2. $-1 \to -2 \to -1$,
  3. $-5 \to -14 \to -7 \to -20 \to -10 \to -5$,
  4. $−17 \to −50 \to −25 \to −74 \to −37 \to −110 \to −55 \to −164 \to −82 \to −41 \to −122 \to −61 \to −182 \to −91 \to −272 \to −136 \to −68 \to −34 → −17, $

  This is sometimes called the generalized Collatz conjecture.

• Another way is to change the definition to something of the form $$ f(n) = \begin{cases} \frac n2 & \text{if $n$ is even} \\\ an+b & \text{if $n$ is odd} \end{cases} $$ for fixed constants $a$ and $b$.