Consider the function

$$f(n)=\begin{cases}n/2&\mbox{if }n\mbox{ is even}\\3n+1&\mbox{otherwise}\end{cases}.$$

Starting from any positive integer $x_0$, we can iterate the sequence $x_1=f(x_0)$, $x_2=f(x_1)$, and so on, with $x_n=f^n(x_0)$. The Collatz conjecture is a famous unsolved problem that claims that the sequence eventually reaches $1$ for any starting value $x_0$.

We can separate the steps of the sequence into "even" and "odd" moves, based on whether $x_n$ is even or odd. This leads us to the following, much easier conjecture:

There is no divergent Collatz sequence such that $x_n\bmod 2$ is periodic.

(This does not rule out the possibility of a nontrivial cycle; here I am talking only about sequences that go to infinity.) Can we show this?


Any sequence of parities corresponds to specific composition of the two possible linear transformations, hence to a transformation of the form $n\mapsto \frac{3^an+b}{2^c}$ with non-negative integers $a,b,c$. For this to produce an integer, it must be the case that $2^c\mid 3^an+b$, i.e., $n$ must be in one specific residue class modulo $2^c$. As we can consider several periods instead of one, it follows that $n$ must be in a specific residue class modulo $2^{kc}$ for every $k\in\Bbb N$. This means that there can be only one such $n$. But then $\frac{3^an+b}{2^c}$ must be the same number and hence the sequence does not diverge.

  • $\begingroup$ Does this result imply that, supposing there were some cycle or sequence diverging to infinity, the limit point of the iterated function $f(x)=3x+2^{\nu_2(x)}$ would either be irrational over $\Bbb Z_2$ or diverge by $\lvert\cdot\rvert_2$? If that question even makes sense? Because I'm pretty sure we know that limit to be $0$ for all integer inputs in which case we would have a contradiction. $\endgroup$ – user334732 Oct 6 '18 at 18:52

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.