0
$\begingroup$

Collatz conjecture is generalized by the statement: "For any number greater than zero, if the number is even then divide it by 2. If the number is odd, multiply the number by 3 then add 1." The conjecture states that after following this rule ad-infinitum, the chain will eventually lead to 4, 2, 1.

Representing this in binary, then you will get 100, 10, 1 which is a really obvious pattern. It is obvious that all powers of 2 (in binary is a 1 followed by zeroes) will eventually lead to 1.

In my attempt to answer this puzzle, i tried ignoring the divide by 2 part of the rule and analyzed the result. For example, starting with n=3 we get:

3, 10, 32

In binary, that is:

11, 1010, 100000

Seeing this, and also looking at many other examples, I generalized the equation into a single line (call it eq1):

$$N_{a+1}=N_a + gp2d(N_a)$$

Where gp2d() is a function that returns the greatest power of 2 divisor of a number. With this equation, we can simplify the solution with fewer steps but in exchange will use larger numbers (though as python 3.x int is unbounded, it is irrelevant). To count the total number of steps when following the general rule, then you just need to count the calls to the eq1 and add it to the number of zeroes of the binary of the final result. For example like before, for 3, the original chain is:

3, 10, 5, 16, 8, 4, 2, 1

For a total of 7 steps. The equation eq1 was called 2 times. The number of trailing zeroes for the binary of 32, 100000, is 5. Then, 5 + 2 = 7, the number of steps required if you follow a normal step-by-step.

Now, here's my proof:

With $eq1$, any number $N_a$ will eventually lead to a number $N_a=100...0$ in binary, in other words, a power of 2.

Let's list down the proofs:

1. All numbers greater than 0 can be written as a sum of powers of 2.

Proof of this is the binary number which are basically representation of numbers as the sum of powers of 2.

2. "If the number is even then divide it by 2" is only there to minimize the value of the number. You can ignore it until the last step to do it only a single time.

When you implement this and ignore all division by 2, you will notice that for each step, the number of zeroes of the binary definitely increases by at least 1 zero for each step.

3. Looking at the modified $3n+1$ to $3N_a+gp2d(N_a)$, you will notice that adding gp2d() is just adding a 1 to the first 1 from the right of the binary form.

That is to show, for example is 10, with binary of 1010.

$$N_{a+1}= 11(1010) + 10 = 3(10) + 2$$ $$N_{a+1}= 11110 + 10 = 30 + 2$$ $$N_{a+1}=100000 = 32$$

This step is essential in converting all 1's into trailing 0's. In other words, if there is absolute proof that following eq1 will eventually produce a perfect power of 2, then there is also proof that collatz will always end in 1.

Is proving this equation relevant to the actual Collatz conjecture? Or is it not?

The python code is used:

def gp2d(n):
    '''Find the greatest power of 2 divisor of a number.'''
    t = bin(n)[::-1]
    return 2**t.index('1')

def is_collatz(n):
    '''Find if a number is a collatz number.'''
    count = 0
    d = gp2d(n)
    while d != n:
        #print("n is %i" %n) #For debugging
        n = 3*n + d
        d = gp2d(n)
        count += 1
    #print("n is %i" %n) #For debugging
    count += len(bin(n)) - 3
    return count
```
$\endgroup$
  • 2
    $\begingroup$ So instead of saying the usual If $a_n$ is odd then $a_{n+1} = 3a_{n}+1$, you seem to be saying If $a_n$ is not a power of $2$ but is a multiple of $2^k$ though not $2^{k+1}$ then $a_{n+1} = 3a_{n}+2^k$. I do not see why this leads inevitably to a power of $2$. Take for example $27$, $82$, $248$, $752$, $2272$, $6848$, $20608$. The last of these in binary is $101000010000000_2$ and all that is seems to have been achieved is a lot of digits, several of which are $1$ and little immediate prospect of things getting better $\endgroup$ – Henry Jul 22 '19 at 7:13
  • $\begingroup$ @YvesDaoust - In Edward V.'s formulation, since $10=5\times 2^1$, the next step is apparently $32=3\times 5\times 2^1 +2^1$ which will be a multiple of $2^2$ (and possibly a higher power of $2$) $\endgroup$ – Henry Jul 22 '19 at 7:18
2
$\begingroup$

You are simply re-formulating the Collatz formula, apparently without divisions. But in reality they are still there because the number that you add is the power of $2$ equal to the number of divisions that were skipped. This brings no insight on the problem.

For a computer implementation, this approach is not recommended as you are carrying useless bits, which will slow down computation for nothing.


A slightly more handy scheme is to work with odd numbers only, and the iterations

$$N_{k+1}=\text{Trim}(3N_k+1)$$ where $\text{Trim}$ discards the trailing binary zeroes. E.g. $3\to5\to1$. (This doesn't bring insight either.)


"Solutions" obtained in three lines like this have been investigated by thousands of amateurs and hundreds of professionals. The probability that you find something new that easily is zero or less.

$\endgroup$
  • $\begingroup$ @henry: I opened the option for the probability to be non-zero. $\endgroup$ – Yves Daoust Jul 22 '19 at 7:59
  • $\begingroup$ :) negative probability has been discussed, I think to remember, in a blog of John Baez ... $\endgroup$ – Gottfried Helms Jul 22 '19 at 9:07
  • $\begingroup$ @GottfriedHelms: so you mean that negative probabilities are not imaginary ? :) $\endgroup$ – Yves Daoust Jul 22 '19 at 9:17
  • $\begingroup$ Well, Yves, you remember, also reality -not only in fora as ours here- is much complex; it has real and imaginary components (and even funny ones - but that oversteps now the mathematical connotations...) $\endgroup$ – Gottfried Helms Jul 22 '19 at 9:35
  • $\begingroup$ @GottfriedHelms: I get the argument. $\endgroup$ – Yves Daoust Jul 22 '19 at 10:01
0
$\begingroup$

This step is essential in converting all 1's into trailing 0's. In other words, if there is absolute proof that following eq1 will eventually produce a perfect power of 2, then there is also proof that collatz will always end in 1.

You would have to show that you will end up with a single one.
It's true in a sense that you will shave of all trailing ones, but that's also true for 5n+1 which won't reach a power of 2 starting at 13 for example.

def gp2d(n):
    return n&-n
n=13
d = gp2d(n)
for i in range(10):
 print(format(n, "b"))
 n=5*n+d
 d=gp2d(n)

I have tried your approach but "backwards"
Instead of starting from 1, multiplying by 2 ,subtracting one, and dividing by 3 and so on,
Start from a power of 2, subtract a smaller power of 2 divide by 3 and so on

If the Collatz Conjecture is true and is equivalent to your restatement of the problem, then any N can be written like;
$$\frac{ \frac{2^{a} - 2^{b}}{3} -2^{c}}{3} - 2^{d}...$$

For a-b to be divisible by 3, a must be congruent to b mod 3
Likewise $\frac{2^{a} - 2^{b}}{3}$ must be congruent to $2^{c}$ and so on ...
No power of 2 is divisible by 3, even powers leave remainder 1, and odds leave 2

$$2^a ≢ 0 \bmod 3\\ 2^{2a} ≡ 1 \bmod 3\\2^{2a+1} ≡ 2 \bmod 3\\$$

x=y=z=r=a=b=c=g=h=0
for i in range (30):
 a = y+4
 b = y-2*x
 r = ( (1<<a)-(1<<b) )//3
 print(r,end =" ")
 g=x+x+1 < y
 x=(x+1)*g
 y+=not g
x=y=0
print()
for i in range(30):
 a = 5+y
 b = y-((z&1)+z*3)+1
 c = y-(x<<1)-(((z&1)<<1) +z*3)
 r = ( ( (1<<a)-(1<<b) )//3 -(1<<c) )//3
 print(r,end =" ")
 g=x+x+1 < y-((z+1)//2)*6 +(z&1)
 h=z < y//6 + (y+1)//6
 x=(x+1)*g
 y+=not(g|h)
 z+=h>g
 z*=g|h
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.