A sequence containing all positive rational numbers. Question: Consider the following sequence $\{a_n\}_{n=1}^{\infty}$ defined as $a_1=1$ and for $n\ge1$ $a_{2n}=a_{n}+1$ and $a_{2n+1}=\dfrac{1}{a_{2n}}$. Show that the sequence has all positive rational numbers exactly once.
So far: In $a_n$ if $n$ is even $a_n>1$, and if $n>2$ is odd then $a_n<1$. If we can show that all positive rational numbers greater than $1$ are terms of the subsequence $a_{2n}$ we will be done. If $p/q$ is a positive rational in lowest form and $p>q$ then we have to show its a term of the subsequence. How can I do that? 
Well I did prove the uniqueness of them, say $a_m=a_n$ and $m\neq n$ for the minimum $m+n$, its easy to see equality will hold if either both $m,n$ are even or both odd, from this we will get a contradiction to minimality assumption of $m,n$.
Please give some hints to proceed from here. If you have alternate solutions do share.  What are some other sequences like this which cover the rationals/irrationals?
Thanks a lot!
 A: Hint: Indeed, use continued fractions and also the binary expansion of the index. 
Take a positive rational number. Consider its continued fraction.  Use pebbles (zeroes) for the partial quotients and reverse the fraction bars into ones. Reverse the sequence of zeroes and ones thus obtained and prepend a one. You got the binary expansion of the index of the term that equals that number
A: You can do it by induction on the denominator.
I am going to write $f(m)=a_m$, because putting complicated formulae in subscripts is ugly.
First, show that $f(m)>1$ if and only if $m$ is even.
If your rational number is $\frac{p}{1}$ for some integer $p$, then $f(2^p)=p$.
Now, assume it is true for all rationals $\frac{p}{q}$ with $q<Q$. Let $P$ be another positive integer relatively prime to $Q$.
Applying the division algorithm, write $P=Qx+r$ where $x\geq 0$ and $0\leq r<Q$. If $r=0,$ then $Q$ divides $P$, which means they are not relatively prime of unless $Q=1$, which is already covered. So we can assume $0<r<Q$.
Now, by the induction hypothesis, we know that $\frac{Q}{r}=f(m)$ for some $m$, since $0<r<Q$. Since $\frac{Q}{r}>1$, we have that $m=2n$ for some $m$. 
The last step, which I'll let you fill in, is to show that:
$$f(2^x(m+1))=\frac{P}{Q}$$
