3
$\begingroup$

We know that there are two possibilities to disprove the Collatz Conjecture.

  • We find a nontrivial cycle.

  • We find a sequence that diverges to $\infty$

A non-constructive disproof is imaginable as well. I am particular interested in the cycles that have been ruled out.

I read the questions and answers about the Collatz conjecture in MSE. I would like to learn.

What is the longest cycle that has been ruled out until now? For example, is it possible to prove that there is no cycle of $10 ^ {1000} $ (or otherwise)?

I present an example for negative integer number that best describes the definition of the length of the cycle.

$$17 → −50 → −25 → −74 → −37 → −110 → −55 → −164 → −82 → −41 → −122 → −61 → −182 → −91 → −272 → −136 → −68 → −34 → −17$$

So, we have $\large 7$ odd-value cycle length.

But here, Collatz Conjecture doesn't include negative number.

$\endgroup$
  • 2
    $\begingroup$ You may want to look at this:en.wikipedia.org/wiki/Collatz_conjecture $\endgroup$ – Vinyl_cape_jawa Feb 23 at 16:25
  • $\begingroup$ @Vinyl_coat_jawa I know . $k=68$? $\endgroup$ – Learner Feb 23 at 16:26
  • $\begingroup$ What is the problem with the question? $\endgroup$ – Learner Feb 23 at 16:40
  • $\begingroup$ @Peter wiki is the oldest source. $\endgroup$ – Learner Feb 23 at 17:15
  • 1
    $\begingroup$ @Learner I highly doubt that there is a better result. Wikipedia updates such articles usually quite soon after a new discovery. $\endgroup$ – Peter Feb 23 at 17:16
4
+25
$\begingroup$

The following link asserts an improvement on Eliahou’s lower bound on cycle lengths: p. 13 in the slides of T. Ian Martiny’s talk The author gives a lower bound for a cycle length to be 10, 439, 860, 591.

Update (redux): I read the slides too hastily. The result rules out ranges of cycle lengths: a cycle length must admit the representation $$ 630 138 877a + 10 439 860 591b + 103 768 467 013c $$ where $a,b,c$ are non-negative integers, $b>0$, and $ac=0$. (Thanks--again--for the clarification and keeping me honest, G. Helms)

$\endgroup$
  • 2
    $\begingroup$ Unfortunately, the question of the OP is "what is the longest cycle that is ruled out?" due to the title of the question. I've recently found that the cycle with $N=127940101513462006853$ odd steps can be ruled out based on $a_{min}>87 \times 2^{60}$ (using a very simple method). This is so far the longest (except for the $m$-cycles with small $m$ which are disproven for any length). I write this although I think the OP means actually that what you've in fact answered... $\endgroup$ – Gottfried Helms Feb 27 at 7:58
  • $\begingroup$ @rukhin then the numerical value $10,439,860,591$ should be recomputed and increased using the better yoyo@home convergence test maximum at $1.003 \times 10^{20} \approx 87 \times 2^{60}$. $\endgroup$ – mbjoe Feb 27 at 15:53
  • 1
    $\begingroup$ @rukhin - just a minor doubt: you say "can include arbitrarily large integers". Do you really mean arbitrarily ? And with "integers" do you mean elements of a cycle (what I call $a_k$) or lengthes-of-nontrivial-cycles (what I call $N$)? The reason why I ask is that I think for both parameters there are upper bounds existent. $\endgroup$ – Gottfried Helms Mar 8 at 8:05
1
$\begingroup$

According to this and, since according to the same site convergence has been computer tested up to $1.003 \times 10^{20}$ by a yoyo@home project (see also this and click "Start" to order from highest to lower number checked), the minimum cycle length should be by now 9,283,867,937. This length is computed counting all sequence steps for both odd and even values, and with one step only from odd $x$ to the following $(3x+1)/2$.

The yoyo guys claim it is 17 billion (search here for "Collatz: Search finished"), however I think Eric Roosendaal is more trustworthy. Maybe this value refers to a double step for odd $x$: $x \to 3x+1 \to (3x+1)/2$.

$\endgroup$
  • $\begingroup$ mbjoe - please see my extended answer giving some much larger numbers $N$ of odd steps for which the existence of general cycles is disproved. $\endgroup$ – Gottfried Helms Feb 25 at 2:59
  • 2
    $\begingroup$ I think the OP should clarify the question. My answer would be fitted for a question like "what is the minimum length of a possible cycle?", because it excludes all cycles lengths below 9,283,867,937. But if one makes some assumption on properties of the cycle, or specific cycle length, there are bigger cycle lengths which have been ruled out, as @Gottfried Helms explained. $\endgroup$ – mbjoe Feb 25 at 9:31
  • $\begingroup$ @mbjoe Example: We have $\large 7$ odd value cycle length for $−17 → −50 → −25 → −74 → −37 → −110 → −55 → −164 → −82 → −41 → −122 → −61 → −182 → −91 → −272 → −136 → −68 → −34 → −17$ $\endgroup$ – Learner Feb 25 at 10:18
  • $\begingroup$ yes, that reformulation of the focus towards the smallest would be helpful... and I think is most likely also intended. $\endgroup$ – Gottfried Helms Feb 25 at 11:25

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.