From Makarov's Selected problems in real analysis
Let $r_n$ be defined as follows\begin{cases} r_1=1 & \\ r_{2k}=1+r_k \\ r_{2k+1}=\frac{1}{r_{2k}} & \end{cases} Prove that $r_n: \mathbb N\setminus{\{0\}}\to \mathbb Q_+\setminus{\{0\}}$ is a bijection
I've proved via induction that $r_n$ is injective. I've also noticed that $\forall n, r_{2^n}=n+1$.
But I can't prove that $r_n$ is surjective. It's trivial to note that every rational of the form $\frac{1}{k+1}, \frac{k+2}{k+1}, \frac{k+1}{k+2},\frac{2k+3}{k+2}$ has a preimage. This goes on and on, but proving that every rational has a preimage seems tricky.
We have $r_m \leqslant 1 \iff m \equiv 1 \pmod{2}$.
Suppose the set $E$ of positive rationals that don't occur in the sequence were nonempty. Choose an $r = \frac{a}{b}$ with minimal denominator from $E$. We know that $b > 1$ since $r_{2^{n-1}} = \frac{n}{1}$ for all $n$.
If $r < 1$, then $\frac{1}{r} = \frac{b}{a}$ has smaller denominator than $r$, hence by minimality, $\frac{1}{r} = r_m$ for some $m$. Since $\frac{1}{r} > 1$, it follows that $m = 2k$ for some $k$, and then $r = \frac{1}{r_{2k}} = r_{2k+1}$, contradicting the assumption.
So $r > 1$ [since $1$ evidently occurs]. Then let $q = \lfloor r\rfloor$ and $s = \frac{a - qb}{b}$. Then $0 < s < 1$, so by what we already have shown, there is a $k$ with $s = r_{k}$. But then
$$r_{2^q\cdot k} = 1 + r_{2^{q-1}\cdot k} = 2 + r_{2^{q-2}\cdot k} = \dotsc = q + r_{2^{q-q}\cdot k} = q + r_k = q+s = r,$$
again contradicting the assumption. Hence $E = \varnothing$.
So far, so good. But if we look a little closer, we see that there is a connection between the [simple] continued fraction expansion of a rational, and the binary expansion of its index in the sequence. Since a rational number $r > 0$ has two simple continued fraction expansions, one ending with $1$, and the other with an integer $> 1$ (with the exception of $r = 1$, for which both simple continued fraction expansions, $[1]$ and $[0,1]$ end in $1$), let's normalise and always choose the continued fraction expansion ending with $1$, and for $r = 1$ choose the expansion $[1]$. Let us denote the map associating each rational $r > 0$ with its index in the sequence with $i$, so
$$r_{i(r)} = r,\quad i(r_m) = m.$$
Let $r = [a_0,a_1,\dotsc,a_n]$, and suppose $r\neq 1$, so $n > 0$. Then we have
$$r = a_0 + \frac{1}{[a_1,\dotsc,a_n]},$$
and thus
$$i(r) = 2^{a_0} \cdot i\biggl(\frac{1}{[a_1,\dotsc,a_n]}\biggr).$$
If $n = 1$, i.e. $r = a_0 + 1 = [a_0,1]$, then it stops here. Otherwise, we have
$$0 < \frac{1}{[a_1,\dotsc,a_n]} < 1$$
and therefore
$$i\biggl(\frac{1}{[a_1,\dotsc,a_n]}\biggr) = 1 + i([a_1,\dotsc,a_n]).$$
Then
$$i([a_1,\dotsc,a_n]) = 2^{a_1}\cdot i\biggl(\frac{1}{[a_2,\dotsc,a_n]}\biggr),$$
and so on. Thus, the binary expansion of $i([a_0,a_1,\dotsc,a_n])$ ends with $a_0$ zeros, preceded by a $1$, then $a_1-1$ zeros, a $1$, $a_2-1$ zeros, …, a $1$, then $a_{n-1}-1$ zeros, and finally another $1$. Wrapping it up:
$$i([a_0,\dotsc,a_n]) = \sum_{k = 0}^{n-1} 2^{b_k},$$
where
$$b_k = \sum_{j = 0}^k a_j.$$
A quick example:
$$\frac{355}{113} = [3,7,15,1],$$
so $i\bigl(\frac{355}{113}\bigr) = 2^3 + 2^{10} + 2^{25}$. Check:
\begin{align} r_{2^{15}} &= 16\\ r_{2^{15}+1} &= \frac{1}{16}\\ r_{2^{7}(2^{15}+1)} &= 7 +\frac{1}{16} = \frac{113}{16}\\ r_{2^{22} + 2^{7} + 1} &= \frac{16}{113}\\ r_{2^{25} + 2^{10} + 2^{3}} &= 3 + \frac{16}{113} = \frac{355}{113}. \end{align}