Produce an explicit bijection between rationals and naturals? I remember my professor in college challenging me with this question, which I failed to answer satisfactorily: I know there exists a bijection between the rational numbers and the natural numbers, but can anyone produce an explicit formula for such a bijection?
We will first find a bijection $h_{+}:\mathbb Z^+\to \mathbb Q^+$. From there, we easily get a bijection $h:\mathbb Z\to \mathbb Q$ by defining: $$h(n)=\begin{cases}h_{+}(n)&amp;n&gt;0\\
0&amp;n=0\\
-h_{+}(-n)&amp;n&lt;0
\end{cases}$$

From there, we can use any of the bijections $\mathbb N\to\mathbb Z$ to get our bijection between $\mathbb N$ and $\mathbb Q$. (We'll need a specific such bijection below, $s$.)

Now, every positive integer can be written uniquely as $p_1^{a_1}p_2^{a_2}\cdots$, where the $p_1=2,p_2=3,p_3=5,\dots$ is the sequence of all primes, and the $a_i$ are non-negative integers, and are non-zero for only finitely many $i$s.

Similarly, every positive rational number can be written uniquely as $p_1^{b_1}p_2^{b_2}\cdots$ where the $b_i$ are integers and only finitely many of the $b_i$ are non-zero.

So define $s:\mathbb N\to\mathbb Z$ (where we take $\mathbb N$ to include $0$):

$$s(n)=
(-1)^n\left\lfloor\frac{n+1}{2}\right\rfloor
$$

The sequence $s(0),s(1),s(2),s(3),\dots$ would be $0,-1,1,-2,2\dots$, and this is a bijection from $\mathbb N$ to $\mathbb Z$. The only properties we really need for $s$ is that $s$ is a bijection and $s(0)=0$.

Then for any $n=p_1^{a_1}p_2^{a_2}\cdots\in\mathbb Z^+$, define $$h_{+}(n)=p_1^{s(a_1)}p_2^{s(a_2)}\cdots $$

This then defines our bijection $h_{+}:\mathbb Z^+\to \mathbb Q^{+}$.

A potientially interesting feature of $h_+$ is that it is multiplicative - that is, if $\gcd(m,n)=1$ then $h_{+}(mn)=h_+(m)h_{+}(n).$
This is a bijection between the Stern-Brocot tree and the tree of Natural numbers. 
Every left node is given by $ L_n = [2 P_n ] $ and every right one by $ R_n= [2 P_n +1 ]$ where $P_n $ is the value of the parent node and $P_0=[1]$.
We have the sequence of transformations $ P_n \rightarrow [ L_n  , R_n  ]$,    $L_n \rightarrow P_{n+1}$,  $R_n \rightarrow P^\prime_{n+1}$ .

In list notation for the tree (count the brackets) this is

$$ n = 1 \mapsto
[1,[2],[3]]
$$

$$n = 2  \mapsto [1,[2,[4], 
      [5]],
   [3,[6],
      [7]]]
$$
$$
n = 3  \mapsto [1,[2,[4,[8],[9]],[5,[10],[11]]],[3,[6,[12],[13]],[7,[14],[15]]]]
$$
and so on.