12
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ At least, we have two obvious properties: for even $k$ the sequence can diverge, for $k=1$ the sequence always converges. I think it's possible to show that for $k\ge 5$ the sequence can diverge. $\endgroup$ – TZakrevskiy Aug 9 '13 at 17:16
  • $\begingroup$ I don't know if there are explicit examples of divergence for larger (odd) $k$, but there are heuristic arguments in favor of divergence; see terrytao.wordpress.com/2011/08/25/… for more details. $\endgroup$ – Steven Stadnicki Aug 9 '13 at 17:46
  • $\begingroup$ @al-Hwarizmi Just so - if you read the argument before that point, though, you'll see why for the $3n+1$ problem the expectation is that the average size of an iterant 'should' decrease over time, while for the $5n+1$ (and larger) problems the average size 'should' increase. $\endgroup$ – Steven Stadnicki Aug 9 '13 at 18:14
  • $\begingroup$ You may be interested in this arXiv paper. $\endgroup$ – DaBler Aug 7 at 11:42
9
$\begingroup$

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.$$

$\endgroup$
11
$\begingroup$

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):
picture

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


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


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


$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:
picture


$\endgroup$
3
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Hey just came across this and was wondering if you had a source? I'm guessing there's no proof since it would be in some sense "generalized Collatz" but would be very interested :) $\endgroup$ – William May 5 '18 at 17:50
  • $\begingroup$ I did not have a source, but instead just programmed different sequences to see the convergence, and it so happened to work out. However I should contribute any help to Bart Goddard, a professor of mine. $\endgroup$ – TeeJ Lockwood Aug 28 at 16:53
1
$\begingroup$

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.

$\endgroup$

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.