Prove this sequence takes every rational number Given the sequence $a_1 = 0$ and $a_{n+1} = \dfrac{1}{2 \cdot\lfloor{a_n}\rfloor-a_n+1}$ and $p,q\in \mathbb N$ and coprime find $x$ so that $a_x = \dfrac{p}{q}$. I do not even know where would you start with a problem like this.
 A: Observation: $a_k<1$ iff $k$ is odd.
Lemma: If $a_{2n}$ = $a_n$+1.
Proof: By induction. $a_2 = 1 = 1+a_1$. Further suppose $a_{2(n-1)}=a_{n-1}+1$. Denote $x=2\lfloor a_{n-1}\rfloor-a_{n-1}+1$. Then
$$a_n=\frac 1x,$$
$$a_{2n-1} = \frac 1{x+1},$$
$$a_{2n} = \frac 1{2\cdot0-\frac1{x+1}+1} = \frac1{\frac{x}{x+1}}=\frac{x+1}{x}=1+\frac 1x = a_n+1.$$
Lemma proved.
Now consider a rational number and the following process with it. While it is greater than or equal to one, subtract one from the number. Otherwise apply the recurrent formula $x\to\frac1{1-x}$. In every application of the formula, the denominator decreases, so we will get eventually to the number 0.
We can follow the process backwards and assign elements $a_k$ to it. We start with $0=a_1$. When we add one to the value, we just jump from $a_k$ to $a_{2k}$. In the other case (after application of $\frac1{1-x}$), we are on an even index $a_k$. So $a_{k-1}$ is odd, so $a_k = \frac1{1-a_{k-1}}$. Since the function $\frac1{1-x}$ is injective, $a_{k-1}$ is the next value in the reverted sequence.
At the end, we reach the original rational number together with its position in the sequence.
