Looking for a verification or refutation my attempted proof of why the Collatz conjecture is probably false.

267 Views Asked by At

Most people think that the Collatz conjecture is true, but I think that I can prove the opposite.

Let's make two functions, $f(x)$ and $g(x)$.

$f(x) = $ The amount of numbers that can be solved in x steps.
$g(x) = $ The amount of numbers that can be solved in x or less steps.

What we see is that x of the numbers that can be solved in x steps or less is a power of 2. This means that the percentage of numbers that is a power of 2 and that can be solved in x or less steps is $$\dfrac{x}{g(x)}$$.

If the collatz conjecture would be true, it would mean that as $x \rightarrow \infty$, the distribution of powers of 2 in $g(x)$ would be the same as the distribution of powers of 2 in all numbers and thus:

$$\dfrac{x}{g(x)}=\dfrac{x}{2^x}$$

Now let's take a close look at the relationship between $f(x)$ and $g(x)$.

We see that as $x \rightarrow \infty$: $\dfrac{f(x)}{f(x-1)}=a$, where a is a constant smaller than 2 and greater than 1.

This means that: $$g(x) = \sum\limits_{i=0}^{x-1} a^x = \dfrac{a^x-1}{a-1}$$

Using our earlier equation we get: $$\dfrac{a^x-1}{a-1}=2^x$$

Multiplying both sides by $a-1$: $$a^x-1=(a-1)2^x$$

Since $x \rightarrow \infty$, we can ignore the $-1$: $$a^x=(a-1)2^x$$

Dividing both sides by $2^x$: $$({\dfrac{a}{2}})^x=a-1$$

Since $x \rightarrow \infty$ and $a<2$, $$({\dfrac{a}{2}})^x=0$$ and thus $a=1$

But as we just stated a is greater than 1, a contradiction.

The only thing I didnt really prove was the existance of $a$, but if you take a closer look you don't need a constant as long as the ratio is between 1 and 2, which is easy to prove.

Question. Is this attempted proof valid (probably not) and why or why not?

2

There are 2 best solutions below

6
On

You say:

if the collatz conjecture would be true, it would mean that as $x \rightarrow \infty$, the distribution of powers of 2 in $g(x)$ would be the same as the distribution of powers of 2 in all numbers and thus:

$\dfrac{x}{g(x)}=\dfrac{x}{2^x}$

This means you claim if the Collatz conjecture is true, then $g(x)=2^x$. So you claim the Collatz conjecture implies that $2^x$ numbers can be solved in $x$ or less steps, but I see no justification for this at all.

Also in latter parts the handling of "limits" is unusual. You seem to try to use "asymptotic equalities" but in ways one cannot use them.

0
On

Here is a numerical test for $g(20)$ , that means : what is the number of n such that we need at most 20 steps to arrive at 1. What I've got is the number of rows in the following table is 71, which means we have 71 odd numbers in $g(20)$. For the odd numbers with less steps than 20 we can add all multiples with perfect powers of 2 until the number of steps does not exceed 20 which gives exactly 250 additional even numbers. Finally we can also add the perfect powers of 2 up to exponent 20 (which are 20 numbers). So all in all we get 341 numbers n for which we need 20 or less steps to arrive at 1 and by this computations (modulo possibly neglected cases) $g(20)=341$ - but which is not a power of 2.


Table of the odd numbers N which need 20 or less steps to arrive at 1.

exponents in $2^{A_k}$  N    steps required to reach 1
4   0   0   0   0   0   5       5
4   1   0   0   0   0   3       7
4   3   0   0   0   0   13      9
4   3   2   0   0   0   17      12
4   3   2   1   0   0   11      14
4   3   2   1   1   0   7       16
4   3   2   1   1   2   9       19
4   3   2   1   3   0   29      18
4   3   2   1   3   1   19      20
4   3   2   1   5   0   117     20
4   3   2   3   0   0   45      16
4   3   2   5   0   0   181     18
4   3   2   7   0   0   725     20
4   3   4   0   0   0   69      14
4   3   6   0   0   0   277     16
4   3   6   2   0   0   369     19
4   3   8   0   0   0   1109    18
4   3   8   1   0   0   739     20
4   3   10  0   0   0   4437    20
4   5   0   0   0   0   53      11
4   5   1   0   0   0   35      13
4   5   1   1   0   0   23      15
4   5   1   1   1   0   15      17
4   5   1   1   3   0   61      19
4   5   1   3   0   0   93      17
4   5   1   5   0   0   373     19
4   5   3   0   0   0   141     15
4   5   5   0   0   0   565     17
4   5   5   2   0   0   753     20
4   5   7   0   0   0   2261    19
4   7   0   0   0   0   213     13
4   9   0   0   0   0   853     15
4   9   2   0   0   0   1137    18
4   9   4   0   0   0   4549    20
4   11  0   0   0   0   3413    17
4   11  1   0   0   0   2275    19
4   13  0   0   0   0   13653   19
6   0   0   0   0   0   21      7
8   0   0   0   0   0   85      9
8   2   0   0   0   0   113     12
8   2   1   0   0   0   75      14
8   2   3   0   0   0   301     16
8   2   3   2   0   0   401     19
8   2   5   0   0   0   1205    18
8   2   5   1   0   0   803     20
8   2   7   0   0   0   4821    20
8   4   0   0   0   0   453     14
8   6   0   0   0   0   1813    16
8   6   2   0   0   0   2417    19
8   8   0   0   0   0   7253    18
8   8   1   0   0   0   4835    20
8   10  0   0   0   0   29013   20
10  0   0   0   0   0   341     11
10  1   0   0   0   0   227     13
10  1   1   0   0   0   151     15
10  1   1   2   0   0   201     18
10  1   1   4   0   0   805     20
10  1   3   0   0   0   605     17
10  1   3   1   0   0   403     19
10  1   5   0   0   0   2421    19
10  3   0   0   0   0   909     15
10  5   0   0   0   0   3637    17
10  5   2   0   0   0   4849    20
10  7   0   0   0   0   14549   19
12  0   0   0   0   0   1365    13
14  0   0   0   0   0   5461    15
14  2   0   0   0   0   7281    18
14  4   0   0   0   0   29125   20
16  0   0   0   0   0   21845   17
16  1   0   0   0   0   14563   19
18  0   0   0   0   0   87381   19