# Does every such sequence enter into a loop?

I was playing around with number sequences and came across the following interesting type of sequences of positive rational numbers: The sequence starts with any rational number $$x_1$$. Each subsequent term $$x_n$$ is defined by $$x_n=\frac{a+b}{a+1}$$ when the previous term in simplest form is $$x_{n-1}=\frac{a}{b}$$, where a and b are coprime.

Any sequence in which any term $$x_i$$ can be written in either of the following forms: $$\frac{a}{1}, \frac{1}{b}$$ will have every subsequent term be $$x_{j>i}=1$$. This result is trivial.

Every other sequence that I tried that didn't converge into the above result or one of the following loops: $$...\frac{3}{2},\frac{5}{4},\frac{3}{2},\frac{5}{4},...$$ or $$...\frac{29}{18},\frac{47}{30},\frac{77}{48},\frac{125}{78},\frac{29}{18},\frac{47}{30},\frac{77}{48},\frac{125}{78},...$$.

Is there any way of proving that every starting point for such a sequence will enter into loop or of predicting what loop will be entered?

• There's another length-22 loop starting from $\frac{97}{60}$, and possibly others. Starting from $\frac{5}{18}$, the sequence doesn't appear to ever repeat. Nov 5, 2019 at 23:06
• Probably you had to write $$x_n = \dfrac{a+b}{b+1},$$ where $x_{n-1}=\dfrac{a}{b}$. Nov 6, 2019 at 16:12
• @Oleg567: No, I didn't. If you look at the examples of loops I gave, you would see that I wrote it correctly. Nov 6, 2019 at 22:39
• @Moko19: If so, then many numbers of the form $\frac{1}{b}$ are candidates to generate sequence without loops: $\frac{1}{44}; \frac{1}{80}; \frac{1}{104}; \frac{1}{128}; \frac{1}{134}; \ldots$. And many other rational numbers: $\frac{5}{12}; \frac{13}{16}; \frac{15}{16}; \frac{17}{6}; \frac{5}{18}; \ldots$ Example of sequence generated by $\frac{1}{44}$: $\frac{1}{44}, \frac{45}{2}, \frac{47}{46}, \frac{31}{16}, \frac{47}{32}, \frac{79}{48}, \frac{127}{80}, \frac{207}{128}, \frac{335}{208}, \frac{181}{112}, \frac{293}{182}, \frac{475}{294}, \frac{769}{476}, \frac{249}{154}, \ldots$ Nov 7, 2019 at 6:52
• (continuation): $..., \frac{249}{154}, \frac{403}{250}, \frac{653}{404}, \frac{1057}{654}, \frac{1711}{1058}, \frac{2769}{1712}, \frac{4481}{2770}, \frac{2417}{1494}, \frac{3911}{2418}, \frac{6329}{3912}, \frac{10241}{6330}, \frac{16571}{10242}, \frac{26813}{16572}, \frac{43385}{26814}, \frac{70199}{43386}, \frac{22717}{14040}, \frac{36757}{22718}, \frac{59475}{36758}, \frac{96233}{59476}, \frac{51903}{32078}, \frac{83981}{51904}, \frac{45295}{27994}, \frac{73289}{45296}, \frac{23717}{14658}, \frac{38375}{23718}, \frac{62093}{38376}, \frac{100469}{62094}, \frac{162563}{100470}, \ldots$ Nov 7, 2019 at 6:55

Comments have mentioned that many such sequences seem to never become eventually periodic (based on computing a "large" number of terms). Here's a possible approach to proving this.

Consider the following recursion on ordered pairs of positive integers: $$(a_{k+1},b_{k+1}) = (a_k+b_k,a_k+1),\quad k=1,2,3,...$$ in which the initial pair $$(a_1,b_1)$$ determines the whole sequence.

Claim: If it happens that $$(a_1,b_1)$$ is such that $$a_k, b_k$$ are coprime for all $$k$$, then the sequence $$\left({a_k\over b_k}\right)_k$$ is one of your sequences $$(x_k)_k$$ with $$x_1={a_1\over b_1}$$, and hence $$\lim_{k\to\infty}x_k=\lim_{k\to\infty}{a_k\over b_k}=\varphi,$$ where $$\varphi={1+\sqrt{5}\over 2}=1.618...$$ is the Golden Mean.

Proof of Claim: The first part is clear, because if all $$a_k, b_k$$ are coprime then every $${a_k\over b_k}$$ is an irreducible fraction, so starting with $$x_1={a_1\over b_1}$$, no reduction occurs in any iteration of your mapping. Furthermore, by inspection of the recursion it is readily seen that $$(a_k,b_k)=(G_{k+1}-1,G_k)$$, where $$G_k=(a_1+1)\,F_k+b_1\,F_{k-1}$$, and $$F_k$$ is the $$k$$th Fibonacci number.Then $${a_k\over b_k}= {G_{k+1}-1\over G_k} = {F_{k+1}\over F_k}{(a_1+1)+b_1\,{F_{k}\over F_{k+1}}-{1\over F_{k+1}} \over (a_1+1)+b_1\,{F_{k-1}\over F_{k}} }\to \varphi{(a_1+1)+b_1\,{1\over \varphi}-0 \over (a_1+1)+b_1\,{1\over \varphi} }=\varphi$$ using the known fact that $${F_{k+1}\over F_k}\to\varphi.$$

Therefore, proving the following conjecture would establish that some of your sequences never enter a cycle:

Conjecture 1: There exist initial pairs $$(a_1,b_1)$$ such that $$a_k, b_k$$ are coprime for all $$k$$ (and hence $$\lim_{k\to\infty}{a_k\over b_k}=\varphi$$). (I suspect that there are infinitely many such initial pairs.)

For example, with $$(a_1,b_1)=(5,12),$$ computations show that all $$(a_k,b_k)$$ are coprime for $$1\le k\le 10^6.$$ (Thus, no reductions occur in generating the first $$10^6$$ terms of your sequence starting with $$x_1={5\over 12}$$.)

EDIT: Conjecture 1 has since been proven, as it is a consequence of this answer. (That there are infinitely many such pairs also follows from this.)

For example, $$x_1={5\over 12}$$ is one of the proven cases for which no reductions occur among the terms in the sequence $$(x_1,x_2,x_3,...)=({5\over 12},{17\over 6},{23\over 18},...).$$ But there are infinitely many other values of $$x_1$$ giving the same tail of this sequence $$(x_2,x_3,...).$$ This is due to the easily-proved fact that the set of possible predecessors of $${a\over b}$$, with $$a\perp b$$, is $$\left\{{m\,b-1\over m\,(a-b)+1}: m\ge 1, \ \ (m\,b-1)\perp (m\,(a-b)+1)\right\}$$ using "$$\perp$$" to abbreviate "coprime to". Thus, $$x_2={17\over 6}$$ has the infinite set of predecessors $$\left\{{m\,6-1\over m\,11+1}: m\ge 1, \ \ (m\,6-1)\perp (m\,11+1)\right\}=\left\{{5\over 12},{11\over 23},{23\over 45},... \right\},$$ any one of which can be taken as the initial value $$x_1$$. (A less trivial conjecture, not yet proven, is that there are infinitely many $$x_1$$ whose orbits converge to $$\varphi$$ without reductions, the orbits being disjoint from one another. Examples appear to include $${5\over 12},{17\over 36},{29\over 90},{41\over 84}.$$)

NB: By a "predecessor" of $$q$$, I mean a positive rational $$p$$ such that $$f(p)=q,$$ where $$f$$ is your transformation. It's notable that any set of predecessors must be either empty or infinite:

1. $$q$$ has no predecessor iff $$q\lt 1$$.
2. $$q$$ has infinitely many predecessors iff $$q\ge 1$$.

I suspect that every sequence generated by iterating your mapping either converges to $$\varphi$$ or eventually enters one of infinitely many finite cycles:

Conjecture 2: The set of positive integer pairs (and hence the positive rationals) is partitioned into infinitely many disjoint subsets $$S_0,S_1,S_2,\ldots,$$ where \begin{align} S_0&=\{(a_1,b_1): {a_k\over b_k}\to \varphi \}\\ S_i&=\{(a_1,b_1): {a_k\over b_k}\to \text{cycle}_i \},\quad i=1,2,3,...\\ \end{align} and $$\text{cycle}_1,\text{cycle}_2,\text{cycle}_3,...$$ are infinitely many disjoint cycles, each having finitely many elements.

If the latter conjecture holds, then each of your rational sequences can be seen as "trying to converge to $$\varphi$$" and either succeeding, or failing by eventually entering a finite cycle whose elements only approximate $$\varphi$$ ("convergence interruptus" :).

For reference, here are six of the cycles (found using Sage), showing their min and max values truncated to 8 decimal digits:

length  min(cycle)  max(cycle)  cycle
------  ----------  ----------  -----
1       1           1           
2       1.25        1.5         [3/2, 5/4]
4       1.56666666  1.61111111  [29/18, 47/30, 125/78, 77/48]
22      1.60204081  1.61792452  [97/60, 899/556, 511/316, 1339/828, 2167/1340, 4953/3062, 3507/2168, 6995/4324, 5675/3508, 3061/1892, 8015/4954, 4323/2672, 343/212, 157/98, 361/224, 413/256, 555/344, 255/158, 827/512, 223/138, 585/362, 947/586]
65      1.61763236  1.61803395  [4003/2474, 444783/274892, 95221/58850, 114893/71008, 249293/154072, 134455/83098, 532089/328850, 628045/388154, 424733/262500, 655665/405224, 405223/250442, 687233/424734, 388153/239892, 719675/444784, 1111967/687234, 154781/95660, 1060889/655666, 860939/532090, 1016199/628046, 328849/203240, 114437/70726, 1799201/1111968, 3907515/2414978, 2911169/1799202, 4710371/2911170, 7621541/4710372, 274891/169892, 2414977/1492538, 12331913/7621542, 19953455/12331914, 32285369/19953456, 10447765/6457074, 6477/4004, 9147/5654, 11273/6968, 12917/7984, 5653/3494, 10481/6478, 14801/9148, 7983/4934, 29515/18242, 18241/11274, 6967/4306, 50287/31080, 53863/33290, 67435/41678, 47757/29516, 77273/47758, 100265/61968, 33289/20574, 154071/95222, 131655/81368, 87153/53864, 81367/50288, 61721/38146, 141017/87154, 41677/25758, 61967/38298, 109113/67436, 176549/109114, 31079/19208, 250441/154782, 162233/100266, 262499/162234, 213023/131656]
39      1.61803357  1.61803398  [3870813/2392294, 949209361/586643648, 1535853009/949209362, 240962139/148922792, 2188491115/1352561894, 1776025085/1097643868, 2485062371/1535853010, 957889651/592008362, 2507787665/1549898014, 1352561893/835929222, 1340305127/828354124, 3541053009/2188491116, 1145908825/708210602, 6263107/3870814, 16397029/10133922, 10133921/6263108, 26530951/16397030, 42927981/26530952, 60615283/37462306, 113414667/70094120, 69458933/42927982, 37462305/23152978, 160144081/98974486, 98077589/60615284, 158692873/98077590, 98974485/61169596, 389884931/240962140, 183508787/113414668, 256770463/158692874, 259118567/160144082, 419262649/259118568, 415463337/256770464, 586643647/362565714, 672233801/415463338, 678381217/419262650, 70094119/43320548, 1097643867/678381218, 362565713/224077934, 1549898013/957889652]

phi = 1.6180339887...

• I've asked a question about proving Conjecture 1. Nov 10, 2019 at 19:35