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$.
Supposed Proof
The Collatz sequence consists of instances of a single odd term interspersed by one or more even terms.
The sequence grows if and only if there is only a single even term between two successive odd terms.
Consider the following sequences:
\(\ds \) | \(\) | \(\ds 31 \to 94 \to 47\) | \(\ds 2051 \to 6154 \to 3077\) | The ratio between the last and first terms is $1.5$ | ||||||||||
\(\ds \) | \(\) | \(\ds 41 \to 124 \to 62 \to 31\) | \(\ds 233 \to 700 \to 350 \to 175\) | Here the ratio is $0.75$ | ||||||||||
\(\ds \) | \(\) | \(\ds \) | \(\ds 2429 \to 7288 \to 3644 \to 1822 \to 911\) | Now it is $0.3785$ |
For a sufficiently large set of $3$ term sequences, approximately $50 \%$ will have one even term and $50 \%$ will have two or more even terms.
Let N = 4k+1 Then 3*n + 1 = 12*k + 4 This is always divisible by 4
Let N = 4k+3 Then 3*n + 1 = 12*k + 10. This is never divisible 4.
The 4*k + 1 term can possibly be divided by any power of two.
Then, a priori the last statement logical. There is no feature in the construction
of a Collatz Sequence that favors 4*k + 3 over 4*k + 1.
Consider the following equations
(3*N + 1)/2 = 1.5*N + 1/2 (3*N + 1)/4 = 0.75*N + 1/4 (3*N + 1)/8 = 0.3875*N + 1/8 (3*N + 1)/16 = 0.19375*N + 1/16 " " " " " " " " " (3*N + 1)/(2^x) = (3*N)/(2^x + 1/(2^x)
This shows the rate of gain/loss based on the divsibility of the 3n+1 term.
A priori, 4*k+1 & 4*k+3 are equally probable.
The net result for a partial or completed sequence ts;
last odd term = first odd term *1.5^A*0.75^B*0.3875^C*0.1875^D* ...
A, B, C, D represent the number of occurrences of each divisibility
This equation has very many terms,but for the purposes of this discussion; only three or four are required.
QUESTION: What is the relative ratio between A, B, C & D necessary to achieve minimal growth?
If B = 200, C = 100, D = 50; what must A be?
1.5 A = 591 1.1747192942496588E+104* 0.75 B = 200 1.0286145857915894E-25* 0.375 C = 100 2.5300364191868604E-43* 0.1875 D = 50 4.4674901453521685E-37= 1.3657687020517226
Ans. A = 591
Even Terms Ratio No. of Terms Net Gain or Loss $1$ $1.5$ $100$ $4.065611775352152 \times 10^{17}$ $2$ $0.75$ $50$ $5.663216564269376 \times 10^{-7}$ $3$ $0.3785$ $50$ $8.003762476146784 \times 10^{-22}$
Total loss: $1.8428214850660864 \times 10^{-10}$
Perhaps $200$ terms is not a "sufficiently large" set. It could be $200$ googols. Then the ratio would be $10^{-20}$ googols.
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$