Does every positive rational number appear once and exactly once in the sequence $\{f^n(0)\}$ , where $f(x):=\frac1{2 \lfloor x \rfloor -x+1} $

Question

Consider the map $f:\mathbb Q^+ \to \mathbb Q^+$ defined as $f(x):=\dfrac1{2 \lfloor x \rfloor -x+1} , \forall x \in \mathbb Q^+$ ; then is the function

$g:\mathbb Z^+ \to \mathbb Q^+$ defined as $g(n):=f^n(1)=\underbrace{(f \circ f \circ \ldots f}_{n \text{ times}})(1)$ a bijection? That is, do the iterates of $f()$ hit all positive rationals?

Answer 1

As Henning noted in the comments,

$$\begin{align*} f\left(\frac{p}q\right)&=\frac1{2\left\lfloor\frac{p}q\right\rfloor-\frac{p}q+1}\\ &=\frac{q}{2q\left(\frac{p-(p\bmod q)}q\right)-p+q}\\ &=\frac{q}{p+q-2(p\bmod q)}\;. \end{align*}$$

If we let $p_0=q_0=1$ and define $p_n$ and $q_n$ by the recurrences

$$\begin{align*} p_{n+1}&=q_n\\ q_{n+1}&=p_n+q_n-2(p_n\bmod{q_n})\;, \end{align*}\tag{1}$$

clearly $g(n)=\frac{p_n}{q_n}$. Note that we can eliminate $q_n$ and reduce $(1)$ to

$$p_{n+1}=p_{n-1}+p_n-2(p_{n-1}\bmod{p_n})\;,$$

with initial conditions $p_0=p_1=1$.

An easy induction shows that $p_{2n}>p_{2n+1}$ for $n>0$, and $p_{2n+1}<p_{2n+2}$ for $n\ge 0$.

If $n>0$ is even, then by the induction hypothesis $p_{n-1}<p_n$, so $$p_{n+1}=p_{n-1}+p_n-2p_{n-1}=p_n-p_{n-1}<p_n\;.\tag{2}$$

If $n$ is odd, then $p_{n-1}>p_n$; let $p_{n-1}=kp_n+r$, where $k\ge 1$ and $0\le r<p_n$. Then $$p_{n+1}=p_{n-1}+p_n-2(p_{n-1}\bmod{p_n})=(k+1)p_n-r\ge 2p_n-r>p_n\;.$$

Let $r_0=1$, and define $r_n$ by the recurrence

$$\begin{align*} r_{2n+1}&=r_n\\ r_{2n+2}&=r_n+r_{n+1}\;. \end{align*}\tag{3}$$

Clearly $r_0=r_1=p_0=p_1=1$. Suppose that $r_k=p_k$ for $k\le 2n+1$. Then

$$\begin{align*} p_{2n+2}&=p_{2n}+p_{2n+1}-2(p_{2n}\bmod{p_{2n+1}})\\ &=r_{2n}+r_{2n+1}-2(r_{2n}\bmod{r_{2n+1}})\\&=r_{n-1}+2r_n-2\big((r_{n-1}+r_n\big)\bmod{r_n}\big)\\ &=r_{n-1}+2r_n-2(r_{n-1}\bmod{r_n})\\ &=r_n+\big(p_{n-1}+p_n-2(p_{n-1}\bmod{p_n})\big)\\ &=r_n+p_{n+1}\\ &=r_n+r_{n+1}\\ &=r_{2n+2}\;, \end{align*}$$

and $r_{2n+3}=r_{n+1}=r_{2n+2}-r_n=r_{2n+2}-r_{2n+1}=p_{2n+2}-p_{2n+1}=p_{2n+3}$ by (2). Thus, $r_n=p_n$ for all $n\ge 0$.

For $n\ge 1$ let $a_n=r_{n-1}=p_{n-1}$. Then $a_1=1$, and it follows from $(3)$ that

$$a_{2n}=r_{2n-1}=r_{n-1}=a_n$$

and

$$a_{2n+1}=r_{2n}=r_{n-1}+r_n=a_n+a_{n+1}$$

and hence that $\langle a_n:n\in\Bbb Z^+\rangle$ is the sequence defined in this question. In my answer to that question I showed that if $q_n=\frac{a_{n+1}}{a_n}$ for $n\in\Bbb Z^+$, the sequence $\langle q_n:n\in\Bbb Z^+\rangle$ is a bijection from $\Bbb Z^+$ to $\Bbb Q^+$, and the rational numbers $q_n$ are just the reciprocals of the numbers $g(n)$.