Do we know of any Collatz theorem involving similar functions. For example what do we know about iterations of:

$$ f(x) = \begin{cases} \dfrac{x + 1}{2} \text{, if } x \text{ is odd}. \\ 2x + 1, \text{ if } x \text{ is even}.\end{cases} $$

Since this one doesn't involve $3$ maybe it is easier to solve? Why isn't this one the lowest hanging fruit rather than the $3x +1$ problem?


$$ f(1) = 1 \\ f(2) = 5 \to 3 \to 2 \to \dots \\ f(4) = 9 \to 5 \dots \\ f(6) = 13 \to 7 \to 4 \to \dots $$

So one of the finite number of conjectured cycles would be $5 \to 3 \to 2$.

  • 2
    $\begingroup$ I think this can be solved by analysing the binary expansion...? $\endgroup$ – Trebor Mar 26 '19 at 2:08
  • 1
    $\begingroup$ Why $\pm$? If it’s just minus, the two things are mutually inverse, and all numbers pair off. I guess you just want +? $\endgroup$ – rschwieb Mar 26 '19 at 2:10
  • 2
    $\begingroup$ You might want to check your definition here. The $-$ sign obviously oscillates (e.g. 4, 9, 4, 9, ...) and the $+$ sign just increases by 1 each time (e.g. 4, 9, 5, 11, ...). $\endgroup$ – eyeballfrog Mar 26 '19 at 2:10
  • $\begingroup$ @eyballfrog, it's $+$ yes. It has finite cycles just like Collatz. $4, 9, 5, 11, 6, 13, 7, 4$. 🍌😹 $\endgroup$ – Shine On You Crazy Diamond Mar 26 '19 at 2:12
  • $\begingroup$ Perhaps this answer of mine (image) is interesting: mathoverflow.net/a/200126/7710 It looks at the generalization of $3x+1$ to $mx+1$ $\endgroup$ – Gottfried Helms Mar 26 '19 at 8:30

The Collatz conjecture is interesting because it is hard. If you use the $-1$ version, every even $x$ goes to $2x+1$, which goes back to $x$, so we can just say every pair $(2k, 4k+1)$ is a cycle including $(0,1)$ and be done.

Even for the $+1$ version, every doubling is followed by a divide by $2$, which might be followed by another divide by $2$, so numbers can't grow much beyond twice the start. There is a cycle $(2,5,3)$ which everything except $1$ seems to fall into. We can prove this by considering what happens to numbers of the form $4k$ and $4k+2$. A number of the form $4k$ goes to $8k+1$, which then goes to $4k+1$. A number of the form $4k+1$ goes to $2k+1$ which then goes to $k+1$, so any large number gets divided by $2$ in a few steps. We can expand this to show every number except $1$ goes to the $(2,5,3)$ cycle.

The multiplication by $3$ in the Collatz conjecture is just right to balance the up steps and the down steps if you consider the chances of odd numbers in a row. If you increase the multiplier most numbers will go off to infinity. If you decrease it, all numbers fall into a small cycle and we can prove that. Chaos lives on the boundary between two or more well behaved regions.


If $x$ is even, then $f(x)=2x+1$ is odd. So $$f(f(x))=\frac{(2x+1)+1}{2}= x+1,$$ which is also odd. So $$ f(f(f(x))) = \frac{(x+1)+1}{2} =\frac{x}{2}+1 \leq x.$$ Thus no matter wheter $x$ is even or odd at the beginning, the number will always become smaller after a couple of iterations. Thus there is no number $x$ for which the series tends to infinity.


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.