6
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Misha Lavrov
    Nov 5, 2019 at 23:06
  • $\begingroup$ Probably you had to write $$x_n = \dfrac{a+b}{b+1},$$ where $x_{n-1}=\dfrac{a}{b}$. $\endgroup$
    – Oleg567
    Nov 6, 2019 at 16:12
  • $\begingroup$ @Oleg567: No, I didn't. If you look at the examples of loops I gave, you would see that I wrote it correctly. $\endgroup$
    – Moko19
    Nov 6, 2019 at 22:39
  • $\begingroup$ @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 $ $\endgroup$
    – Oleg567
    Nov 7, 2019 at 6:52
  • $\begingroup$ (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 $ $\endgroup$
    – Oleg567
    Nov 7, 2019 at 6:55

1 Answer 1

Reset to default
2
$\begingroup$

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...
$\endgroup$
1
  • $\begingroup$ I've asked a question about proving Conjecture 1. $\endgroup$
    – r.e.s.
    Nov 10, 2019 at 19:35

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.