Krdytkyu

What is the benefit of looking at the binary representation of the collatz conjecture. I know that it makes the computation easier because there is really one operation involved which is multiplying by 3. And then we simply shift the resulting binary number to the right if it hast Least significant bit (lsm) = 0

Does this offer a faster algorithm (complexity wise) ?

I know that the normal algorithm for collatz doesn't have an upper bound using Big Oh notation. (It's not analysable).

It is natural to consider (and analyze) the Collatz map not as an operation on numbers but on strings. Most obvious candidates are the strings representing the numbers in bases $2$, $3$, and $6$. In base $6$ the Collatz map works like a cellular automaton, i.e., can be computed for the different digits "in parallel". The reason for this is the following: $>:!2$ and $>times3$ are the same in base $6$; furthermore the resulting carries have no long-range effects in this base. (Note that for multiplications or divisions in some base you usually have to work from the left or from the right and cannot decide on a particular digit until all digits to the left or to the right of it have been worked out and the remaining carry is determined.)

I don't know much about the second part of the question (speed of the algorithm in terms of complexity), but one advantage of the binary representation is that your "win" condition is clearly represented:

"Does every natural number eventually reach the binary string $100dots 0$? "

We can go a step or two further. Notice that if the string $n = 100dots 0$ appears, then the previous step was a string (of length one less than $n$) of the form

begin{align}
n-1 = 11dots1
end{align}

Multiplying by 3 in binary is the same as multiplying by the string $11$, which is the same as multiplying by $10 + 1$ and so we notice that

begin{align}
n-1 &= 11dots1\
implies frac{n-1}{3} &= 1010dots 101
end{align}

where I have been lazy about indicating the length of the strings. We can then go further by padding with an arbitrary number of zeros:

begin{align}
2^k(frac{n-1}{3}) = 1010dots10100dots00
end{align}

which means that the next step after this replaces the trailing $100dots00$ part by $011dots11$:

begin{align}
2^k(frac{n-1}{3}) - 1 = 1010dots10011dots11
end{align}

and thereafter things get more complicated. One might argue that these patterns don't particularly get us far, but at the very least they don't appear as clearly in base 10, so perhaps there's some value in investigating binary.

I like the idea of pursuing base 6 as mentioned in Christian Blatter's answer, although one disadvantage is that the price of simplifying our "step-by-step" computations is that our "win" condition becomes more obscured: the end goal is to reach the numbers $2^k$ and in base 6 their string representations don't follow a particularly "nice" pattern (or at least I don't think they do, maybe I'm wrong?)

Perhaps roughly: base 6 may be advantageous in seeking to disprove the conjecture, while base 2 may be advantageous in seeking to prove the conjecture.

(A lot of what I wrote was inspired by/confirmed by this post )