Collatz Conjecture

From ProofWiki
Jump to navigation Jump to search

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.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Collatz_Conjecture&oldid=603979"