# The Worst Case of the Collatz Conjecture

Is $2^x-1$ the worst case scenario of the Collatz Conjecture? Do these numbers generally produce the longest alternating chains? If so, if a highest bound of the length of chains of $2^x-1$ is found, is the does this mean that the Collatz Conjecture will be proved?

• What do you mean by $x^2-1$ being a "scenario" ? And what do you mean by "alternating chain" ? – Ewan Delanoy Oct 29 '17 at 13:44
• What do you mean by worst case? Among small numbers, $27$ takes a long time to get to $1$ and it is not of the form $x^2-1$. – paw88789 Oct 29 '17 at 13:45
• Obviously if they are the worst, but have an upper bound, and we can show all that, then the Collatz Conjecture will be proven. But do note that being 'generally' the worst (i.e 'tend' to get longer chains than other numbers) is pretty vague and certainly not good enough for an actual proof. – Bram28 Oct 29 '17 at 13:47
• So, to make your suggested proof strategy hard, I suppose you could try to show that for any $n$, the chain produced by $n^2-1$ is always longer (or at least as long as) the chains produced by any of the numbers between $(n-1)^2$ and $n^2-1$. Did you check if this is true for some small $n$? E.g paw88789 mentions $27$ as a pretty bad case ... is $31$ worse than $27$? – Bram28 Oct 29 '17 at 13:54
• P.s. Did you maybe mean $2^n-1$ instead of $n^2-1$? Given the very nature of the algorithm of the Collatz Conjecture, the $2^n-1$ would at least seem to have some initial conceptual plausibility, whereas from that viewpoint there doesn't seem to be anything special about numbers of the form $n^2-1$ – Bram28 Oct 29 '17 at 14:23

Wether or not the mersenne primes in the form $2^n-1$ have any special connection to the Collatz trajectories or not, you are not the first to reasearch this approach and it is worth taking a closer look at.

Here are two others I found who have either uploaded or published their work:

Jonas Kaiser put Collatz trajectories in matrix form. He talks about Primes and Mersenne primes much later into his article.

Gottfried Helms has also explored this topic.

I personally have not looked too much into this approach to give any educated recommendations. One of my thoughts after thinking about it is it may be possible the mersenne primes represent different upper limits and are out of order (So 31 is not necessarily a limit for 27?).

First of all, from the perspective of the algorithm behind the Collatz conjecture, there doesn't seem to be any initial conceptual reason to think why numbers of the form $n^2-1$ would be 'special'. Intuitively, it would at least make some initial sense if you considered numbers of the form $2^n-1$ (in fact, that's how I kept reading your your formula when contemplating and answering your question initially! Funny how the brain works ...) ... is that what you maybe meant as well?

Anyway, check Wikipedia's page on the Collatz Conjecture: especially look at the sequence of "Numbers with a total stopping time longer than that of any smaller starting value ...":

$1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, …$

Other than $1,3$ I do not seem any numbers of the form $n^2-1$, so at least glancing at those initial numbers it does not seem numbers of the form $n^2-1$ are particularly bad.

Likewise, other than $1,3,7$ I do not seem any numbers of the form $2^n-1$, so it does not seem numbers of that form are particularly bad either.

• $7$ is not of the form $x^2-1$ either. – hmakholm left over Monica Oct 29 '17 at 14:04
• @HenningMakholm Sheesh! I kept thinking $2^n-1$ .... – Bram28 Oct 29 '17 at 14:14
• @Bram28 thanks for correcting me! Yes I meant 2^x-1...that was a typo. I have already made changes to my original post. – LOL Nov 1 '17 at 21:36

One of the things to note about Collatz sequence is when you write the number $n$ as $n = m + 2 ^ k$ then the first $j$ operations on the Collatz sequence of $n$, where $j \leq k$ is exactly the first $j$ operations on m.

Which means a sequence of $k$ operations repeat exactly as prefix for every $2^k$. Now the intuition tells you thats exactly how binary numbers work too. To clarify the operations I mean is $M = (3n+1)/2$ and $D = n/2$.

[[M, D, M, D, M, D, M, D, M, D, M, D, M, D, M, D], [D, M, D, M, D, M, D, M, D, M, D, M, D, M, D, M], [M, M, D, D, D, M, D, M, D, M, D, M, D, M, D, M], [D, D, M, D, M, D, M, D, M, D, M, D, M, D, M, D], [M, D, D, D, M, D, M, D, M, D, M, D, M, D, M, D], [D, M, M, D, D, D, M, D, M, D, M, D, M, D, M, D], [M, M, M, D, M, D, D, M, D, D, D, M, D, M, D, M], [D, D, D, M, D, M, D, M, D, M, D, M, D, M, D, M], [M, D, M, M, M, D, M, D, D, M, D, D, D, M, D, M], [D, M, D, D, D, M, D, M, D, M, D, M, D, M, D, M], [M, M, D, M, D, D, M, D, D, D, M, D, M, D, M, D], [D, D, M, M, D, D, D, M, D, M, D, M, D, M, D, M], [M, D, D, M, D, D, D, M, D, M, D, M, D, M, D, M], [D, M, M, M, D, M, D, D, M, D, D, D, M, D, M, D], [M, M, M, M, D, D, D, D, M, D, D, D, M, D, M, D], [D, D, D, D, M, D, M, D, M, D, M, D, M, D, M, D], [M, D, M, D, D, M, D, D, D, M, D, M, D, M, D, M], [D, M, D, M, M, M, D, M, D, D, M, D, D, D, M, D], [M, M, D, D, M, M, D, M, D, D, M, D, D, D, M, D], [D, D, M, D, D, D, M, D, M, D, M, D, M, D, M, D], [M, D, D, D, D, D, M, D, M, D, M, D, M, D, M, D], [D, M, M, D, M, D, D, M, D, D, D, M, D, M, D, M], [M, M, M, D, D, D, D, M, D, D, D, M, D, M, D, M], [D, D, D, M, M, D, D, D, M, D, M, D, M, D, M, D], [M, D, M, M, D, D, M, M, D, M, D, D, M, D, D, D], [D, M, D, D, M, D, D, D, M, D, M, D, M, D, M, D], [M, M, D, M, M, M, M, M, D, M, D, M, M, D, M, M], [D, D, M, M, M, D, M, D, D, M, D, D, D, M, D, M], [M, D, D, M, M, D, M, D, D, M, D, D, D, M, D, M], [D, M, M, M, M, D, D, D, D, M, D, D, D, M, D, M], [M, M, M, M, M, D, M, D, M, M, D, M, M, M, D, M], [D, D, D, D, D, M, D, M, D, M, D, M, D, M, D, M], [M, D, M, D, M, M, D, D, M, M, D, M, D, D, M, D], [D, M, D, M, D, D, M, D, D, D, M, D, M, D, M, D], [M, M, D, D, D, D, M, D, D, D, M, D, M, D, M, D], [D, D, M, D, M, M, M, D, M, D, D, M, D, D, D, M], [M, D, D, D, M, M, M, D, M, D, D, M, D, D, D, M], [D, M, M, D, D, M, M, D, M, D, D, M, D, D, D, M], [M, M, M, D, M, M, D, D, D, M, M, D, D, M, M, D], [D, D, D, M, D, D, D, M, D, M, D, M, D, M, D, M], [M, D, M, M, M, M, M, D, M, D, M, M, D, M, M, M], [D, M, D, D, D, D, D, M, D, M, D, M, D, M, D, M], [M, M, D, M, D, M, D, D, D, M, M, M, D, M, D, D], [D, D, M, M, D, M, D, D, M, D, D, D, M, D, M, D], [M, D, D, M, D, M, D, D, M, D, D, D, M, D, M, D], [D, M, M, M, D, D, D, D, M, D, D, D, M, D, M, D], [M, M, M, M, D, M, D, M, M, D, M, M, M, D, M, M], [D, D, D, D, M, M, D, D, D, M, D, M, D, M, D, M], [M, D, M, D, D, D, M, M, M, D, M, D, D, M, D, D], [D, M, D, M, M, D, D, M, M, D, M, D, D, M, D, D], [M, M, D, D, M, D, D, M, M, D, M, D, D, M, D, D], [D, D, M, D, D, M, D, D, D, M, D, M, D, M, D, M], [M, D, D, D, D, M, D, D, D, M, D, M, D, M, D, M], [D, M, M, D, M, M, M, M, M, D, M, D, M, M, D, M], [M, M, M, D, D, M, M, M, M, D, M, D, M, M, D, M], [D, D, D, M, M, M, D, M, D, D, M, D, D, D, M, D], [M, D, M, M, D, M, D, M, D, D, D, M, M, M, D, M], [D, M, D, D, M, M, D, M, D, D, M, D, D, D, M, D], [M, M, D, M, M, D, D, D, M, M, D, D, M, M, D, M], [D, D, M, M, M, M, D, D, D, D, M, D, D, D, M, D], [M, D, D, M, M, M, D, D, D, D, M, D, D, D, M, D], [D, M, M, M, M, M, D, M, D, M, M, D, M, M, M, D], [M, M, M, M, M, M, D, D, D, M, M, D, M, M, M, D], [D, D, D, D, D, D, M, D, M, D, M, D, M, D, M, D]]

Thats for the first $64$ numbers. I considered the sequence to be never ending (repeating between 1-2-1-2-1-2-...).

If you note unlike binary numbers the bit pattern seem to be chaotic if I can say. But there is definitely a pattern to it. Suppose, you want to know what is the $4$ bit prefixes, then we take the $3$ bit prefix and we can build the 4 bit prefixes like follows. if $n$ is even then $D$ followed by the 3-bit prefix of $n/2$ if $n$ is odd then $M$ followed by the 3-bit prefix of $(3n+1)/2$ modulo $2^3$. Its pretty obvious when you write the number as $n = m + 2^k$.

Now when does the sequence ends? Suppose, for every $n$ if we could prove that above operation reaches a fixed point, we are done. And when it reaches a fixed point, every $m$ in the sequence of $n$ will be $\leq 2^k$ for some $k$. I guess that's why $2^k - 1$ seemed special I suppose.

EDIT: To clarify, if we could prove every suffix of a $n$ is in all sequences of $2^k - 1$ for some $k$ then that term has no diverging trajectory.