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$