What loops are possible when doing this function to the rationals? What loops are possible when doing this function to the rationals?
Let's define this function on a simplified fraction $\frac{a}{b}$.
$$f\left(\frac{a}{b}\right)=\frac{a+b}{b+1}$$
I started this with $f(\frac{2}{3})=\frac{5}{4}$ then i did the function again and got this sequence of numbers $\frac{2}{3},\frac{5}{4},\frac{9}{5},\frac{7}{3},\frac{5}{2},\frac{7}{3},\dots$ I saw that is starts to loop with $\frac{7}{3},\frac{5}{2}$
Another loop is $\frac{1}{1}$, a one cycle.
Another loop I found was $\frac{2}{1},\frac{3}{2},\frac{5}{3}$.
My first question is: from starting from any rational number does it all ways end in a loop or does it ever go to infinity? And my second question is: what sizes of loops are possible?
If the three loops I stated are the only loops prove it
Dark made a post related What are the possible loops when doing this a type of function to the rationals?
 A: Here is a modification of @Steven Stadnicki's proof. The novel contribution of this answer is justifying the reduction step in Steven's solution through the use of a suitable partial order on the set of lattice points.
Step 1. Settings and Useful Observations
Let $\mathbb{N}_1 = \{1, 2, 3, \dots\}$ denote the set of positive integers and define $\mathsf{Red} : \mathbb{N}_1^2 \to \mathbb{N}_1^2$ by
$$ \mathsf{Red}(a, b) = \frac{(a,b)}{\gcd(a,b)}. $$
Also, we equip $\mathbb{N}_1^2$ with the partial order $\leq$ such that1)
$$ (a, b) \leq (c, d) \quad \Leftrightarrow \quad [b < d]\text{ or }[b = d \text{ and } a \leq c]. $$
The following observations are easy to prove but will be useful throughout.

*

*$\text{(P1)} \ $ $a \leq c$ and $b \leq d$ implies $(a, b) \leq (c, d)$.


*$\text{(P2)} \ $ $\mathsf{Red}(\mathrm{p}) \leq \mathrm{p}$ for any $\mathrm{p} \in \mathbb{N}_1^2$.
Step 2. Key Observation
We will identify each pair $(a,b) \in \mathbb{N}_1^2$ satisfying $\gcd(a, b) = 1$ with the simplified fraction $a/b$. Under this identification, we have
$$f(a/b) = \mathsf{Red}(a+b,b+1). $$
Now we will investigate the effect of a suitable number of iterations of $f$. By noting that either $a$ or $b$ must be odd, the following three cases exhaust all the possibilities:

*

*Case 1. Suppose that both $a$ and $b$ are odd. Then both $a+b$ and $b+1$ are even, and so,
\begin{align*}
f(a,b)
= \mathsf{Red}(a+b, b+1)
= \mathsf{Red}(\tfrac{a+b}{2}, \tfrac{b+1}{2})
\stackrel{\text{(P2)}}\leq (\tfrac{a+b}{2}, \tfrac{b+1}{2}). \tag{1}
\end{align*}


*Case 2. Suppose that $a$ is odd and $b$ is even. Then by writing $d=\gcd(a+b,b+1)$,
\begin{align*}
f^{\circ 2}(a,b)
= f(\tfrac{a+b}{d},\tfrac{b+1}{d})
= \mathsf{Red}(\tfrac{a+2b+1}{d},\tfrac{b+d+1}{d}).
\end{align*}
Since $d$ is odd, both $a+2b+1$ and $b+d+1$ are even. This means that both are divisible by $2d$, and so,
\begin{align*}
f^{\circ 2}(a,b)
= \mathsf{Red}(\tfrac{a+2b+1}{2d},\tfrac{b+d+1}{2d})
\stackrel{\text{(P2)}}\leq (\tfrac{a+2b+1}{2d},\tfrac{b+d+1}{2d})
\stackrel{\text{(P1)}}\leq (\tfrac{a+2b+1}{2},\tfrac{b+2}{2}). \tag{2}
\end{align*}
Here, the last inequality follows from the general fact that $\frac{A+Bd}{d}\leq A+B$ for all $A, B \geq 0$ and $d \geq 1$.


*Case 3. Suppose that $a$ is even and $b$ is odd. Since $d = \gcd(a+b, b+1)$ is odd, we find that $\frac{a+b}{d}$ is odd and $\frac{b+1}{d}$ is even. So by applying $\text{(2)}$ and using the inequality in the previous step,
\begin{align*}
f^{\circ 3}(a,b)
= f^{\circ 2}(\tfrac{a+b}{d},\tfrac{b+1}{d})
\stackrel{\text{(2)}}\leq (\tfrac{a+3b+d+2}{2d},\tfrac{b+2d+1}{2d})
\stackrel{\text{(P1)}}\leq (\tfrac{a+3b+3}{2},\tfrac{b+3}{2}). \tag{3}
\end{align*}
Step 3. Proof
Let $(a, b) \in \mathbb{N}_1$ satisfy $\gcd(a, b) = 1$. Then by $\text{(1)}$–$\text{(3)}$, we observe the following:

*

*If $b > 3$, then $\frac{b+3}{2} < b$, and so, a suitable number of iterations by $f$ reduces the second coordinate. This can be repeated finitely many times until the second coordinate becomes $\leq 3$.


*If $b \leq 3$ and $a > 12$, then $\frac{a+3b+3}{2} < a$, and so, a suitable number of iterations by $f$ reduces the first coordinate. Similarly as before, this can be repeated finitely many times until the first coordinate becomes $\leq 12$.


*If $a \leq 12$ and $b \leq 3$, then a suitable number of iterations by $f$ will map $(a, b)$ into another point $(a', b')$ with $a' \leq 12$ and $b' \leq 3$. So by the pigeonhole principle, iteration by $f$ will eventually fall into a cycle.


*By checking all the possible $12+6+8=26$ cases manually, we find that there are only three types of cycles:
$$ (1, 1) \qquad (5, 2), (7, 4) \qquad (2, 1), (3, 2), (5, 3) $$
This completes the proof.

1) Note that this is exactly the colexicographical order induced by the usual order on $\mathbb{N}_1$.
A: The key here is that for parity reasons, we'll always get to a 'smaller' fraction in a short, finite number of stages. Rather than fractions, I'll refer to an iteration on a pair of numbers $f:\langle a,b\rangle \mapsto \mathop{Red}(\langle a+b,b+1\rangle)$ where $\mathop{Red}()$ denotes reduction $\mathop{Red}(\langle a,b\rangle) = \langle\frac{a}{\gcd(a,b)},\frac{b}{\gcd(a,b)}\rangle $. We'll start by inducting on the value of $b$, to show that we need to only consider a small number of values of $b$ when looking for cycles. Note that $a$ and $b$ can't both be even, so there are three cases: $a=2m+1, b=2n$, $a=2m, b=2n+1$, and $a=2m+1, b=2n+1$. The third case immediately goes to $\langle a',b'\rangle$ $=\mathop{Red}(\langle 2m+2n+2,2n+2\rangle)$ $=\mathop{Red}(\langle m+n+1,n+1\rangle)$; this might reduce even further, but this is good enough for our purposes. note that $b'=n+1\lt b=2n+1$, so the value of $b$ always reduces in this case unless $b=1$.
In the case $a=2m+1, b=2n$, the map goes $\langle 2m+1, 2n\rangle$ $\mapsto \mathop{Red}(\langle 2m+2n+1, 2n+1\rangle)$ $\mapsto\mathop{Red}(\langle 2m+4n+2, 2n+2\rangle)$ $=\mathop{Red}(\langle m+2n+1, n+1\rangle)$. Here we have $b'=n+1\lt b=2n$ as long as $b\gt 2$.
Finally, in the case $a=2m, b=2n+1$, the map goes $\langle 2m, 2n+1\rangle \mapsto\mathop{Red}(\langle 2m+2n+1, 2n+2\rangle)$ $\mapsto\mathop{Red}(\langle 2m+4n+3, 2n+3\rangle)$ $\mapsto\mathop{Red}(\langle 2m+6n+6, 2n+4\rangle) = \mathop{Red}(\langle m+3n+3, n+2\rangle)$. Here, $b'=n+2\lt b=2n+1$ as long as $b\gt 3$.
Together, these mean that we can study the effects of the iteration specifically on the cases $\langle a,b\rangle: b\in \{1,2,3\}$; any larger $b$ will eventually reduce to a $b$ in this range. More specifically, we have the cases $\langle a, 1\rangle$, $\langle 2m+1, 2\rangle$, and $\langle 2m, 3\rangle$ to study. I'm going to use a different form of induction on these cases, based on the value of $a+b$.
Let's start with the case $\langle a,1\rangle$. If $a$ is odd, then we have $\langle 2m+1, 1\rangle \mapsto \langle m+1, 1\rangle$; here $a'+b'=m+2$ will always be less than $a+b=2m+2$. If $a$ is even, then we have the case $\langle 2m, 1\rangle$; by the logic above, this maps to $\mathop{Red}(\langle m+3, 3\rangle)$. We get a smaller value for the sum as long as $a+b=2m+1\gt a'+b'=m+6$, or in other words as long as $m\gt 5$ (i.e., $a\gt 10$).
Next up, we have the case $\langle 2m+1, 2\rangle$; by the logic above, this maps to $\mathop{Red}(\langle m+3, 2\rangle)$. Since $a'+b'=m+5\lt a+b=2m+3$ as long as $m\gt 2$, we can see that any pair $\langle a,2\rangle$ with $a$ an odd number greater than $5$ will yield  new pair with a smaller sum.
Finally, we have the case $\langle 2m, 3\rangle$; once again, using the logic above we see that this will map to $\mathop{Red}(\langle m+6, 3\rangle)$. Here we have $a+b=2m+3\gt a'+b'=m+9$ as long as $m\gt 6$, or in other words $a\gt 12$.
Putting this all together, we can see that cases of the form $\langle a,b\rangle$ with $b\leq 3$ always yield another case of similar form with smaller $a$ as long as $a\gt 12$; this leaves only a finite number of values to check, which yields the loops that have already been found.
