# 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.

## Failed Proof

Aiming for a contradiction, suppose that for some $n \in N$, there does NOT exist any $i \in \N$ such that the sequence $S_i = 1$.

From the Well-Ordering Principle, this hypothetical sequence $\sequence {S_k}$ must have a smallest element.

Let $a = S_k$ be the smallest element of this hypothetical sequence.

We know that $a$ can not be even because:

 $\ds S_k$ $=$ $\ds 2 r$ $\ds S_{k + 1}$ $=$ $\ds r$

which contradicts our assertion that $a$ was the smallest element in the sequence.

We also know that $a \not \equiv 1\pmod 4$ because:

 $\ds S_k$ $=$ $\ds 4 r + 1$ $\ds S_{k + 1}$ $=$ $\ds 3 \paren {4 r + 1} + 1$ $\ds$ $=$ $\ds 12 r + 4$ $\ds S_{k + 2}$ $=$ $\ds 6 r + 2$ $\ds S_{k + 3}$ $=$ $\ds 3 r + 1$ $\ds$ $<$ $\ds S_k$

Because $S_{k + 3} < S_k$, this contradicts our assertion that $a$ was the smallest element in the sequence.

When $a \equiv 3 \pmod 4$, we obtain

 $\ds S_k$ $=$ $\ds 4 r + 3$ $\ds S_{k + 1}$ $=$ $\ds 3 \paren {4 r + 3} + 1$ $\ds$ $=$ $\ds 12 r + 10$ $\ds S_{k + 2}$ $=$ $\ds 6 r + 5$ $\ds S_{k + 3}$ $=$ $\ds 3 \paren {6 r + 5} + 1$ $\ds$ $=$ $\ds 18 r + 16$ $\ds S_{k + 4}$ $=$ $\ds 9 r + 8$
but we can go no further because the parity of $S_{k + 4}$ depends on $r$.

The results here are inconclusive.

We now have that if $a = S_k$ is the smallest element of our hypothetical sequence, then $a$ must reside in the residue class of $3$ (modulo $4$).

Let us now see if we can improve our filter for $a$ by removing additional residue classes from contention.

Inspecting the set of residue classes modulo $16$, we focus our attention on $3$ (modulo $16$), $7$ (modulo $16$), $11$ (modulo $16$) and $15$ (modulo $16$).

We know that $a \not \equiv 3 \pmod {16}$ because:

 $\ds S_k$ $=$ $\ds 16 r + 3$ $\ds S_{k + 1}$ $=$ $\ds 3 \paren {16 r + 3} + 1$ $\ds$ $=$ $\ds 48 r + 10$ $\ds S_{k + 2}$ $=$ $\ds 24 r + 5$ $\ds S_{k + 3}$ $=$ $\ds 3 \paren {24 r + 5} + 1$ $\ds$ $=$ $\ds 72 r + 16$ $\ds S_{k + 4}$ $=$ $\ds 36 r + 8$ $\ds S_{k + 5}$ $=$ $\ds 18 r + 4$ $\ds S_{k + 6}$ $=$ $\ds 9 r + 2$ $\ds$ $<$ $\ds S_k$

Because $S_{k + 6} < S_k$, this contradicts our assertion that $a$ was the smallest element in the sequence.

Just like $3$ (modulo $4$) shown above, the results for $7$ (modulo $16$), $11$ (modulo $16$) and $15$ (modulo $16$) are inconclusive.

We now have the following:

If a counterexample to the Collatz Conjecture exists, then such a counterexample would require a sequence with a smallest element.

This smallest element could only reside in the following residue classes:

(modulo $4$): $3$

(modulo $16$): $7$, $11$, $15$

(modulo $64$): $7$, $15$, $27$, $31$, $39$, $47$, $59$, $63$

(modulo $256$): $27$, $31$, $47$, $63$, $71$, $91$, $103$, $111$, $127$, $155$, $159$, $167$, $191$, $207$, $223$, $231$, $239$, $251$, $255$

As we can see, (modulo $4^n$), there are $\approx 2^{1.5 \paren{n - 1} }$ residue classes where $a$ could reside.

This means we have a Cantor set-esque filter which allows our hypothetical smallest element $a$ to reside in an ever dwindling proportion of the possible residue classes (that is, $\dfrac {2^ {1.5 \paren {n - 1} } } {4^n}$).

Just like the Cantor set and just like prime numbers, at increasing values of $n$, we get an ever increasing set of something (what remains of the Cantor set, prime numbers and in this case, candidate residue classes where $a$ could reside).

However, the proportion of the item of interest relative to all possible values heads towards zero.

And we've proved nothing.

Math is hard.

## 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.