# Attempting Collatz conjecture using inverse function

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.

• 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$). – Justin Benfield Jan 7 '17 at 4:03
• @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? – akm Jan 7 '17 at 4:15
• 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. – Justin Benfield Jan 7 '17 at 4:18
• @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? – akm Jan 7 '17 at 4:27
• 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. – Justin Benfield Jan 7 '17 at 4:29