Just to make sure I am up to date with this problem. I know (or I think I do) that it is not yet proven that there are no non-trivial cycles for the collatz sequence (please correct me if I am wrong). But have we already reduced this problem to finding a non-trivial cycle? i.e. if we suppose that there are no non-trivial cycles at all, is it already proven that with this assumption the Collatz conjecture holds? As far as I can see in the literatures, even this is not shown (i.e. we can reduce the problem to proving whether there are no non-trivial cycles). But I may be wrong, so please correct me if I am wrong.

Edit: Most of my knowledge are on par with Lagarias annotated bibliography and I believe it has been a few years since this literature review.

  • 5
    $\begingroup$ A priori, the Collatz conjecture could fail in two ways: a non-trivial cycle or a Collatz sequence tending to infinity. As far as I know, both possibilities are still open. $\endgroup$ – Andreas Blass Aug 3 '14 at 22:40
  • $\begingroup$ I can only confirm what Andreas Blass has written. The Wikipedia article on the Collatz conjecture is usually kept up-to-date: en.wikipedia.org/wiki/Collatz_conjecture. $\endgroup$ – Stefan Kohl Aug 3 '14 at 22:47
  • 3
    $\begingroup$ With respect to Lagarias' bibliography: on February 12, 2012, when he updated his bibliography for the last time so far, Lagarias has written to me: "I am happy to hear about other articles but I have run out of energy for updating the annotated bibliography from 2010 -- on." -- I think this is quite a pity, and it would certainly be good if the further maintenance of this valuable bibliography would be passed on to somebody else, rather than just letting it become a document of purely historical interest by the time. $\endgroup$ – Stefan Kohl Aug 4 '14 at 9:16
  • $\begingroup$ @Stefan agreed! $\endgroup$ – Jose Capco Aug 4 '14 at 11:38

The page http://www.ericr.nl/wondrous/index.html lists numerous records and data related to the Collatz problem, and was updated recently (only about two month ago).

It explictly lists as open the problem:

Conjecture 1a : (weak 3x+1 conjecture) No integer N is divergent.

(There divergent has the natural meaning means that the sequence of iterations diverges.)

It is thus possible that there is no other cycle but the known one, yet still the conjecture fails as there might be divergent elements. Thus, the reduction asked about in OP is not known.

(To be very precise let me add that it could be theoretically possible there is some result that shows: if there were divergent elements there'd be other cycles, so that the above could be open while the reduction in OP still known, yet neither do I know such a result nor does it seem natural.)

  • $\begingroup$ The "cycle" and the "divergence"-problem are likely unrelated. In the $5x+1$-problem we have cycles, and likely most trajectories diverge. In the $3x+1$-problem where we did not yet find any indication of a divergent trajectory, we have nontrivial cycles in the negative numbers. $\endgroup$ – Gottfried Helms Mar 15 '15 at 13:00

It might be a nice illustration of the general behaviour of increasing/decreasing by iterations from a purely statistical view.
Consider some number odd number $a_0$ Then in the $mx+1$-problem, $a_1 = (ma_0+1)/2^A$ and the likelihood of $ma_0+1$ having $2^A$ as factor is just $1/2^A$. From this the likelihood, $ p(a_1 \ge a_0)$ can be computed. This can then be iterated to, say, $N$-iterations and the probability $ \mu_N = p(a_N \ge a_0)$ can be computed the obvious way.

Probabilities $ \mu_N $ are between $0..1$; and the curves for different problem-parameters $m$ are not much detailful. So I also did a transform $y_{m,N} = \tanh^{-1}( 2\mu_{m,N}-1)$. Here are the curves for the transformed probabilities: bild

I've inserted also the fictive "4x+1"-curve although that problemparameter $m=4$ does not make sense in reality. We see, that all curves except that of $m=3$ and $m=4$ increase, that means, the probability that $a_{m,N} \ge a_{m,0}$ for increasing number of iterations tends to $1$ for all problemparameters $m \ge 5$
Moreover, I find it amazing, that the increase of the $y$-values are asymptotically linear with the number of iterations (but didn't investigate this further).

Important remark: Of course, the statistical view does not "see" exceptional cases like occurence of cycles, if their number is small. For instance, in the $5x+1$-problem we actually we know a few cycles, but without that few exceptions statistically the trajectories of most numbers $a_{5,0}$ seem to diverge. This view can only give the "big picture".


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.