8
$\begingroup$

Let

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

and $k=3$ and $x_n\in\Bbb N$. Collatz conjectured for this recurrence system that starting with any $x_n^{(start)}$ the system converges to a limit cycle (an atractor, orbit) of period $3$: $$\dots\rightarrow16\rightarrow8\rightarrow4\rightarrow2\rightarrow1\to4\to2\to1$$

Independent of the above allow me conjecture the following:

Let

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

and $k=5$ and $x_n\in\Bbb N$.

(Part 1) For this recurrence system starting with any $x_n^{(start)}$ the system either

  • converges (stable) to the following limit cycle (an attractor of a repeating sequence, orbit) of period $7$: $$\dots\to16\to8\to4\to2\to1\to 6\to3\to16\to8\to4\to2\to1$$ examples for this are when we start the recurrence with one of the following integers $3$, $15$, $19$, $51$, $65$, $97$, $137$, $155$, $163$, $175$
  • or converges (stable) to a limit cycle (an attractor of a repeating sequence, orbit) of period $10$. Example: $$\dots\to13\to 66\to 33\to 166 \to 83 \to 416\to 208\to 104\to 52\to26\to 13\to \dots$$ examples for this are when we start the recurrence with one of the following integers $5$, $13$, $17$, $27$, $33$, $43$, $83$
  • or diverges (intsable, ecape to infinity)

(Part 2) Hence if the Collatz conjecture would be true then the transition from $k=3$ to $k=5$ would represent a bifurcation from one single limit cycle of period $3$ to one specific limit cycle of periods $7$ (see above) and some other limit cycles of each period $10$.

Question (1): Could you contradict the above conjecture with a counter example?

Question (2): Is this conjecture genuine or has it been stated exactly like this in literature earlier?

enter image description here citation Vaseghi 2013


At reqeust for a Heuristic below a Mathematica program that we applied at TrueNorth Research.

ClearAll[collatz];

collatz1 = 1;

collatz[n_ /; EvenQ[n]] := (Sow[n];collatz[n/2])

collatz[n_ /; OddQ[n]] := (Sow[n]; collatz[5 n + 1])

runcoll[n_] := Last@Last@Reap[collatz[n]]

runcoll[13]

you can change $13$ with any other integer.

$\endgroup$

closed as unclear what you're asking by Steven Landsburg, David White, Felipe Voloch, Qiaochu Yuan, Gerald Edgar Aug 10 '13 at 16:23

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Your "fixpoint" is not fixed : for $k=3$ it has period $3$ and for $k=5$ period $7$. And what is a "genuine conjecture" ? $\endgroup$ – BS. Aug 10 '13 at 14:04
  • 2
    $\begingroup$ I presume the OP means "original." $\endgroup$ – Noah Schweber Aug 10 '13 at 14:45
  • 1
    $\begingroup$ Meta-thread here: meta.mathoverflow.net/questions/608/collatz-question $\endgroup$ – Steven Landsburg Aug 10 '13 at 15:17
  • 2
    $\begingroup$ See math.stackexchange.com/q/14569/448 $\endgroup$ – David E Speyer Aug 10 '13 at 15:56
  • 2
    $\begingroup$ @al-Hwarizmi I agree with you that one can simply change "fixpoint" to "orbit" (of length 3 for Collatz and length 7 for your varianlt). I do not agree that the Wikipedia article supports your calling 1 a fixpoint of the Collatz function. $\endgroup$ – Andreas Blass Aug 10 '13 at 16:29
13
$\begingroup$

The reason why there should be values that escape to infinity in this case is that if one considers a so to say "random model" for the $k=3$ variant one has roughly speaking a change of the size by roughly $3/2$ half the time and a change of $1/2$ half-the time, and the product being less than $1$ one would expect a long-term decay.

By contrast, for the current variant, one has an increase by about $5/2$ half the time and a decrease of $1/2$ half the time. The product being larger than one one would expect a long term increase.

Thus, one would expect there are some values where the function will escape to infinity (so option three should occur sometimes).

Also it seems there is $17 \to 86 \to 43 \to 216 \to 108 \to 54 \to 27 \to 136 \to 68 \to 34 \to 17$.

Added: again I misunderstood the question. As it leaves opent the existence of other such cycles, and only fixes their lengths. The one in OP and the one I recall are it seems known to be the only ones of this length.

It seems feasible there are actually no others if one does not find any somewhat soon. The existence of certain cycles is excluded in a paper mentioned below.

To consider this variant is not original, for example it is mentioned in passing in a blog post by Tao The Collatz conjecture, Littlewood-Offord theory, and powers of 2 and 3 with a more sophisticated form of the argument above (for escaping values).

Also an older math.SE questions (I think not the one mentioned in comments; added: I meant the one by OP, the one by David Speyer mentioning it appeared while I edited) discusses this precise problem giving some additional information and references https://math.stackexchange.com/questions/14569/the-5n1-problem specfically to some paper of Metzger that determines which scyles of certain lengths can exist (also mentioning the one reproduced above, in addition to the one in OP).

$\endgroup$
  • $\begingroup$ Your first part is correct and it refers to my third option, that says for some starting numbers there will be escape to infinity (diverge). So there is no contradiction. I checked actually your second point a couple of days ago following my former question on Collatz on mathstackexchange and we could not find any evidence that the conjecture is not original yet, despite of your suspicion. There are also other sources such by Tao, where the divergence for some starting integers (third option) was indicated (heuristically). But a deatiled distiction in the above form we have not met yet. $\endgroup$ – al-Hwarizmi Aug 10 '13 at 15:50
  • $\begingroup$ You are right. Sorry I was sloppy in reading the question! This should not have happened. I will slightly rephrase my answer to reflect this. $\endgroup$ – user9072 Aug 10 '13 at 15:55
  • $\begingroup$ By the way, your answer brings something great up! Because if with increasing numbers the probability of escape to infinity option would increase (and it increases very fast) then the heuristic is quite trustable already with starting numbers up to 1000. Thanks! $\endgroup$ – al-Hwarizmi Aug 10 '13 at 15:59
  • $\begingroup$ Glad you found the information useful. I tried to add some more. But mainly David Speyer did the same in parallel. (Briefly I misunderstood you point again, but I hope now it is alright.) $\endgroup$ – user9072 Aug 10 '13 at 16:31
  • 2
    $\begingroup$ one minor note to care; the reference to Metzger is in German and I read it indeed now. He is regarded rather as a recreational amateur and the article has obvious faults, some of them mentioned by Speyer as well. Thanks for reference, although. $\endgroup$ – al-Hwarizmi Aug 18 '13 at 17:29

Not the answer you're looking for? Browse other questions tagged or ask your own question.