0
$\begingroup$

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).

$\endgroup$
4
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Wondering: what do we mean by "carries" in the sense that "carries have no long-range effects in this base"? $\endgroup$ – Jonathan Rayner Nov 22 '18 at 10:35
  • $\begingroup$ @JonathanRayner: See my edit. Hope it's clearer now. $\endgroup$ – Christian Blatter Nov 22 '18 at 10:46
  • $\begingroup$ What's :2 and what context uses that notation? I get that a zero-filled left shift is x6 and that multiplying by 3 is equal to doing this left shift and then dividing by 2, but how does this map to an automaton? Is it just output[i] = input[i]//2 + input[i-1]%2 $\endgroup$ – GenTel Feb 13 at 2:10
  • 1
    $\begingroup$ @GenTel: $:2$ means "divide by $2$". This is the same thing as "multiply by$3$ and divide then by $6$". When the numbers are written in base $6$ the second operation is "dummy". I suggest you do some Collatz examples in base $6$ and then see how it works. $\endgroup$ – Christian Blatter Feb 13 at 8:49
0
$\begingroup$

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 $100\dots 0$? "

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

\begin{align} n-1 = 11\dots1 \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 &= 11\dots1\\ \implies \frac{n-1}{3} &= 1010\dots 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}) = 1010\dots10100\dots00 \end{align}

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

\begin{align} 2^k(\frac{n-1}{3}) - 1 = 1010\dots10011\dots11 \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 )

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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