Does every such sequence enter into a loop?

277 Views Asked by At

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?

1

There are 1 best solutions below

1
On BEST ANSWER

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