Collatz conjecture If the function $f(n)$ is applied recursively enough number of times on any positive integer $n$, then unity will always be reached. \begin{align*} f(n) &= \left\{ \begin{array}{ll} n/2 &\text{if }n \bmod2=0 \\ 3n+1 &\text{if }n \bmod2=1 \end{array} \right.\\ \strut\\ \end{align*}

It is an unproven problem. This question explores various approaches to attack the problem. It seems following approach is not discussed there.

Start with unity and apply the inverse function $g(n)$ recursively. Visualize each positive integer as a node and each iteration as a path. To prove the conjecture, one has to show that every node will be reached eventually. To disprove the conjecture, one has to show that there exist at least one node which will never be reached. \begin{align*} g(n) &= \left\{ \begin{array}{ll} 2n &\text{if }n \bmod2=0 \\ (n-1)/3 &\text{if }n \bmod2=0 \hspace{5pt} \& \hspace{5pt} n \bmod3=1 \\ 2n &\text{if }n \bmod2=1 \end{array} \right.\\ \strut\\ \end{align*} Note that while $f(n)$ is a one to one function, $g(n)$ is not.

What work has been done using this approach? Also, if you can comment or throw some insight on the approach, it will be appreciated.

  • 1
    $\begingroup$ I looked into this approach myself, the problem is that the length of the sequence from $n$ to $1$ is not bounded a priori hence you can never prove that it will eventually find $1$ (equivalently from $1$ that you can generate $n$ via the mentioned function), nor can you prove the converse (that it can't eventually reach $1$). It is interesting to note that you can prove that numbers of certain forms will converge to $1$ (e.g. all numbers of the form $32n+23$ will eventually reduce to $1$). $\endgroup$ – Justin Benfield Jan 7 '17 at 4:03
  • $\begingroup$ @JustinBenfield I didn't get the part "hence you can never prove that...". While the problem is not proved, has it been proved that it is unprovable? $\endgroup$ – akm Jan 7 '17 at 4:15
  • $\begingroup$ I should specify, never prove in that way that it will eventually find 1. The Collatz conjecture itself has not been shown to be unprovable, but the generalized version of the conjecture (where the 3, and the 2, (and 1?) are arbitrary natural numbers instead. Has been shown to be undecidable. $\endgroup$ – Justin Benfield Jan 7 '17 at 4:18
  • $\begingroup$ @JustinBenfield if it can be shown that starting with any odd number will eventually dip below the number at least once, then half the problem is solved. other half is that there is only one loop 4 2 1. have you attempted this or can you throw some light on this? $\endgroup$ – akm Jan 7 '17 at 4:27
  • 1
    $\begingroup$ That would actually prove the conjecture as that new lowest value would again be subject to the proved dip to a still lower value. The idea of looking at the problem in reverse has been studied, see: en.wikipedia.org/wiki/Collatz_conjecture Other formulations of the conjecture section where it discusses the Collatz graph. $\endgroup$ – Justin Benfield Jan 7 '17 at 4:29

I've done a lot of work around this, and it is too much to present it here. But you may look at an older discussion, beginning at the Main page

A couple of people have tried to make progress using this inverse problem, but when one formulates its deeper properties mathematically then the same formulae occur as when you formulate the original poblem, especially when looking at the "cycle"-problem (obviously, well - isn't it?)

When I looked at the generalized problem, using negative integers as well, and other multiplicators, say 5x+1, 7x+1, then I came to the formulation, that the full set of integer numbers can -or cannot- be generated having one or more "nests" as basic cycles from where then the generation starts and finally covers all integers. (I began to use the term "roots" when the basic number is a single one, like 1 or -1 and the term "nests" when there is a cycle of basic numbers (like -5,-7 or -17,...,-17) from where an infinite tree can be generated)


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.