3

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?

s20081063
  • 49
  • 5
  • 2
    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
  • 1
    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
  • Sorry I meant 2^x-1 rather than x^2-1. I have already made changes to the original post. – s20081063 Nov 01 '17 at 21:32
  • @Hitler Ah, I figured! Well, like I said, just looing at small values of $n$ this approach doesn't seem promising, but maybe you just need to take on larger values of $n$. Personally I haven't really dived into the Collatz conjecture but I know plenty of people have, so I would do some further searching and see what other people have found already. And one more thing ... can you please change your username? ... I know, I know, free speech and all ... and I dislike political correctness like the next person ... but really? Hitler? – Bram28 Nov 01 '17 at 22:11
  • Thank you so much Bram28! Btw I have changed my username...sorry if it has offended you – s20081063 Nov 02 '17 at 07:49
  • If I'm understanding correctly, $2^n$ is the "best" case, a simple plunk all the way down to 1. Have you compared a few cases of $2^n - 1$ to $2^n + 1$? – Robert Soupe Mar 10 '18 at 19:34
  • I guess you are talking about longest delays? If you have checked out Roosendaal's page, he has delay records for numbers up to $2.7\times10^{17}$. Indeed I don't think anyone have found a formula for the initial number that computes the longest delay (yet) if that exists. –  Mar 12 '18 at 14:35

3 Answers3

5

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.

Bram28
  • 100,612
  • 6
  • 70
  • 118
2

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

Griffon Theorist697
  • 537
0

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.

Vinothkumar Raman
  • 199