Collatz Conjecture

Conjecture

"Collatz Conjecture" from the webcomic XKCD

Let $f: \N \to \N$ be the mapping defined on the natural numbers as follows:

$\forall n \in \N: \map f n = \begin{cases} n / 2 & : n \text { even} \\ 3 n + 1 & : n \text { odd} \end{cases}$

For any given value of $n$, let the sequence $\sequence {S_k}$ be defined:

$\forall k \in \N: S_k = \begin{cases} n & : k = 0 \\ \map f {S_{k - 1} } & : k > 0 \end{cases}$

The Collatz conjecture is:

For all $n \in N$, there exists some $i \in \N$ such that sequence $S_i = 1$.

That is, by repeatedly applying the rule: half it if even, otherwise multiply it by $3$ and add $1$ to any natural number, eventually you will reach $1$.

Also known as

The rule half it if even, otherwise multiply it by $3$ and add $1$ can sometimes be seen referred to as the Syracuse algorithm.

Examples

The following are instances of integer sequences generated from certain integers by the Collatz process.

$17$: $12$ steps

$17 \to 52 \to 26 \to 13 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$

$27$: $111$ steps

$27 \to 82 \to 41 \to 124 \to 62 \to 31 \to 94 \to 47 \to 142 \to 71 \to 214 \to 107 \to 322 \to$

$161 \to 484 \to 242 \to 121 \to 364 \to 182 \to 91 \to 274 \to 137 \to 412 \to 206 \to 103 \to$

$310 \to 155 \to 466 \to 233 \to 700 \to 350 \to 175 \to 526 \to 263 \to 790 \to 395 \to 1186 \to$

$593 \to 1780 \to 890 \to 445 \to 1336 \to 668 \to 334 \to 167 \to 502 \to 251 \to 754 \to 377 \to$

$1132 \to 566 \to 283 \to 850 \to 425 \to 1276 \to 638 \to 319 \to 958 \to 479 \to 1438 \to 719 \to$

$2158 \to 1079 \to 3238 \to 1619 \to 4858 \to 2429 \to 7288 \to 3644 \to 1822 \to 911 \to 2734 \to$

$1367 \to 4102 \to 2051 \to 6154 \to 3077 \to 9232 \to 4616 \to 2308 \to 1154 \to 577 \to 1732 \to$

$866 \to 433 \to 1300 \to 650 \to 325 \to 976 \to 488 \to 244 \to 122 \to 61 \to 184 \to 92 \to$

$46 \to 23 \to 70 \to 35 \to 106 \to 53 \to 160 \to 80 \to 40 \to 20 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1$

Progress

As of $7$th March $2017$, all numbers up to $2^{60}$ have been tested, and all end in $1$.

Source of Name

This entry was named for Lothar Collatz.

Sources

• 1986: David Wells: Curious and Interesting Numbers ... (previous) ... (next): $27$
• 1997: David Wells: Curious and Interesting Numbers (2nd ed.) ... (previous) ... (next): $27$