Is Collatz' conjecture the only stable solution of its type?

Question

The Collatz Conjecture is well known with the sequence

$$f(n) = \begin{cases} n/2 &;\text{if } n \equiv 0 \pmod{2}\\ k\,n+1 &; \text{if } n\equiv 1 \pmod{2} \end{cases}$$

and $k=3$; the sequence converging $1$ (so called oneness).

Is there any conjecture/theorem on whether the sequence would converge for any other value of $k$; or could it be shown that the sequence diverges for values of $k$ other than $3$?

By convergence here I mean that the sequence after finite steps ends with a stable fixed number such as in case of Collatz it is the case with the number $1$.

Append: In the mean time I wrote out a conjecture on this over here >>>, for those who might be interested.

Answer 1

Here are some pictures for your/our intuition. I graphed the trajectories for initial values $x=5,15,25,...$ for the first $256$ steps of $x_{k+1}=(5x_k+1)/2^A$.
To get the curves to a meaningfully visual interval I show logarithmic scales. The pictures show how most trajectories begin to diverge (not really a safe indication of what characteristic the infinite curves really have) but some show cycling already at early iteration indexes $k$ .

I find $2$ cycles besides the "trivial" one.

---

$x=5,15,25,35,...,95$ detail of the first few iterations . At the bottom we see the "trivial" cyle (brown curve):

---

$x=5,15,25,35,...,95$ first $2^8 = 256$ iterations. At later iteration-indexes $k$ a first "non-trivial" cycle occurs (red line):

---

$x=105,115,125,135,...,195$ first $2^8 = 256$ iterations .

---

$x=205,215,225,235,...,295$ first $2^8 = 256$ iterations . Here a second "non-trivial" cycle becomes visible:

---

$x=205,215,225,235,...,295$ first $2^{11} = 2048$ iterations
It seems really that all trajectories which are divergent up to iteration $k=256$ are also divergent up to iteration $k=2048$ . In general: I doubt that there are "later" cycles:

---

Answer 2

It can be shown that for $k=5$ the sequence can "converge" to other numbers rather than $1$:

$$13\to 66\to 33\to 166 \to 83 \to 416\to 208\to 104\to 52\to 26\to 13.$$

Answer 3

I find the following formalism helpful for my own understanding of the problem, so I think I'll add this here too. To have this transformation generalized let's write: $$ T_M(x) = (M \cdot x+1) / 2^A \qquad \small \text { where A equals the exponent at 2 in the numerator }$$ and we look only at the odd numbers (because all even numbers can be seen as "trivially" dealt with.
For easier notation I like also to write it in this form $$ a_{k+1}= {M \cdot a_k +1 \over 2^{A_k}}$$ or, for linear writing, using consecutive letters instead of numerical indexes $$ b = {M\cdot a +1 \over 2^A}, c={M\cdot b +1 \over 2^B }, \text{ and so on} $$ Then to have a one-step-cycle we must have the result equalling the input $$ b = {M\cdot a +1 \over 2^A} =a$$ and obviously we must have $$ 2^A =M + \frac 1a $$ To have such a one-step-cycle on the number $a$ we must have that $M$ is a mersenne number $M=2^A-1$ and because of its simpliness it usually denotes the "trivial cycle". $M=3,7,15,31,...$ are such mersenne numbers and they allow "trivial cycles". If we allow negative integers, then for $a =-1$, we have a similar pattern, only that the allowed $M$ ar $M=3,5,9,17,...$. For $ |a| \ne 1$ the expression $ \frac 1a$ would introduce fractional values and thus other one-step-cycles are not possible.

To look at two-step-cycles it suffices to look at the generalization $$ b\cdot c = {M\cdot a +1 \over 2^A}\cdot {M\cdot b +1 \over 2^B} = b \cdot a$$ It is too complicated for the place here to discuss this in generality. But to show one helpful pattern I'll show this for $M=3$ and $M=5$

For $M=3$ we get $$ bc = {3a+1 \over 2^A}\cdot {3b+1 \over 2^B} = ba $$ Rearranging gives $$ 2^{A+B} = (3+ {1 \over a})\cdot (3+{1 \over b}) $$ We see immediately, that the rhs can only fall in the interval $9 .. 16$ (where $16$ can only occur if $a=1$ and thus for the trivial case). But there is no other exact power of 2 in this interval, so the lhs-part cannot be satisfied.
If we allow negative integers we get instead $$ 2^{A+B} = (3- {1 \over a})\cdot (3-{1 \over b}) $$ which covers now the interval $4..9$. It gives for $4$ the trivial cycle in the negatives, and for $a=5,b=7$ another solution compatible with the lhs which means thus a two-step cycle (and we must not forget that the sign must reverted to the negatives).

For $M=5$ this looks like $$ 2^{A+B} = (5+ {1 \over a})\cdot (5+{1 \over b} ) $$ The range for the rhs is now $25..36$ and there is only one number (=32) compatible with the lhs. The smallest numbers for a $M=5$ cycle are $1$ and $3$ . We try these numbers $$ 2^{A+B} = (5+ {1 \over 1})\cdot (5+{1 \over 3} )=6\cdot {16 \over 3} =32 $$ Bingo!
So we just found the smallest cycle-length for the $M=5$-problem. Now again in the negative integers integ $$ 2^{A+B} = (5- {1 \over a})\cdot (5-{1 \over b} ) $$ The range for the rhs is 16..25 where 16 indicates the trivial cycle in the negatives. There is not other perfect power of 2 in that interval, so no 2-step-cycle in the negatives for the $M=5$ problem.

---

This expositions for the one- and for the two-step cycles can generalized for multistep-cycles in the obvious way. However, with more steps the view at it through the modular glasses does not lead very far. But there is another tool (which leads to another numbertheoretic tool with which finally R.Steiner proved the non-existence of the "1-cycle" (arbitrary many steps with exponents $A=1$, and only one exponent $B \gt 1$)): we arrange the $M$'s out of the rhs getting $$ {2^S\over M^N} = (1+{1 \over M\cdot a})\cdot (1+{1 \over M\cdot b}) \cdots $$ where I denote the sum-of-exponents (=number of divisions by 2) as $S$ and the number of steps (=number of multiplications by 3 = number of parentheses on the rhs) as $N$ Now with high $a,b,c,...$ on the rhs and high $M$ this is very near to 1, in many cases much nearer than the quotient on the lhs, and one can look at the approximation of $2^S / M^N$ for many $N$ and discover a trend which suggest a required minimal cycle length for a set of integers all larger than its minimal element $a$

Answer 4

Perhaps you have noticed it works for other $m$ and $q$ in the form:

$$ f(n) = \begin{cases} n/m & \text{if } n \equiv 0 \mod m \\ (m+1)n + m-1 & \text{if } n \equiv 1 \mod m \\ \cdots \\ (m+1)n + m-q & \text{if } n \equiv q \mod m \end{cases} $$

for all integers $q$ and $m$, where $ 0 < q < m$.

-TJL

Answer 5

I think the replies provided are fantastic yet I can reply in more of a layman's observations than a graph. In fact I am wishing to learn how to present data in graphs.

I have observed the cycle in many dynamic systems. We can expand the Collatz by a generic form (my notation so pardon this) [A(X)+Y,X/2] Where in Collatz A = 3 and Y = 1 and the [] are used here to denote iteration. Again my notation so if that is bad form please let me know.

It turns out that there is a "Cycle" of the odd Y for all Odd Y. So 3(x)+3 has a cycle on that 3 and so on.

Recently I posted on MathStackExchange about what happens if we change the grouping of the Collatz Form and we do this [(X+Y)*A,X/2] In some cases there is a cycle on the multiplier and in some cases it is a divergent system. Interesting is the output for X is a member of {2,3} in that the sequences look similar to what we see in [3X+1,X/2]

With Dynamic Unary an entire class of numbers exists that are all cycles. For example with parity reference b0 and a length of 32 bits there are 67,108,864 of these dynamic integers where each "Cycle" has 64 elements. also interesting is that each 67,108,864 when each of the 64 32 bit unsigned integers are added up each cycle's sum is the same as all others. I call these dynamic integers ( they are spinning) but a case could be made to call them Quantum Numbers rather then extend the QBit concept to QByte and so on. Google Introduction to Dynamic Unary or follow this link http://arxiv.org/abs/1405.2846

I hope I have been helpful. I do enjoy this subject.