An interesting bijection $\varphi: \mathbb{N}^+ \to \mathbb{Q}^+$

[elim]

Define $\sigma: n \mapsto (p_n, q_n)$ as follows:

$\quad\quad\quad \sigma(n) = (p_n, q_n)= \begin{cases} (1,1), & n = 1, \\ (p_{ \frac{n}{2}}, \; p_{\frac{n}{2}} + q_{\frac{n}{2}}), & 2\mid n > 1, \\ (p_{\lfloor \frac{n}{2} \rfloor} + q_{\lfloor \frac{n}{2} \rfloor}, \; q_{\lfloor \frac{n}{2} \rfloor}), & 2\nmid n > 1\end{cases}$

and $\: \displaystyle{\quad \varphi(n) = \frac{p_n}{q_n} = \begin{cases} 1, & n = 1, \\ \frac{\varphi( \frac{n}{2} )}{1 + \varphi(\frac{n}{2})}, & 2 \mid n > 1 \\ 1 + \varphi(\lfloor \frac{n}{2} \rfloor), & 2 \nmid n > 1\end{cases}}$

Where $\lfloor x \rfloor$ is the integer part of $x$.

Here are some examples:

$\sigma(1) = (1,1),\, \sigma(2) = (1,2),\, \sigma(3) = (2, 1),\, \sigma(4) = (1,3),\, \sigma(5) = (3,2),\, \sigma(6) = (2,3),\, \sigma(7) = ..$

$\displaystyle{\varphi(1) = 1,\,\varphi(2) = \frac{1}{2},\, \varphi(3) = 2,\, \varphi(4) = \frac{1}{3},\, \varphi(5) = \frac{3}{2},\, \varphi(6) = \frac{2}{3},\, \varphi(7) = 3,\, \varphi(8) = \frac{1}{4}, \ldots}$

We need to prove that
$\quad\quad\;$ (a) $\varphi$ is surjective: $\varphi(\mathbb{N}^+) = \mathbb{Q}^+$
$\quad\quad\;$ (b) $\varphi$ is injective: $(\varphi(m) = \varphi(n)) \implies (m = n)$

Proof (a) Let $\displaystyle{M = \{m \in \mathbb{N}^+ \mid \forall p \in \mathbb{N} \cap (0, m)\; (\gcd(p,m) = 1) \implies \bigg( \frac{p}{m}, \frac{m}{p} \in \varphi(\mathbb{N}^+)\bigg)\}}$
$\quad\quad\quad\quad$ Clearly $1 \in M$. Assume $\mathbb{N}^+ \ni k < m \implies k\in M$ for some $m > 1$ and

$\quad\quad\quad\quad\, 1\le p < m,\, \gcd(p,m) = 1.$ Then $p, m -p \in M$ and $\gcd(p, m-p) = 1.\quad$ Thus

$\quad\quad\quad\quad$ $\displaystyle{\varphi(k) = \frac{p}{m - p},\, \varphi(k') = \frac{m -p}{p}}$ for some $k,\; k'$ and so $\displaystyle{\varphi(2k) = \frac{p}{m},\,\varphi(2k' + 1) = \frac{m}{p}}$
$\quad\quad\quad\quad$ Therefore $m \in M$. Which means $M = \mathbb{N}^+$ and so $\displaystyle{\varphi(\mathbb{N}^+) = \mathbb{Q}^+ = \left\{\frac{p}{q} \mid p,\,q \in \mathbb{N}^+\right\}}$
$\quad\quad\;$ (b) Let $K = \{k \in \mathbb{N}^+ \mid (\varphi(m) = \varphi(n)) \wedge (m,n \le k) \implies (m = n)\}$, then $1\in K$.
$\quad\quad\quad\quad$ Suppose $j > 1,\;$ and $\; i < j \implies i \in K$. If $\varphi(j) = \varphi(l) = a$ for some $l \le j$, then
$\quad\quad\quad\quad\, 0< a \ne 1,\; j \equiv i \mod 2$ by the definition of $\varphi$ and $j > 1$. Hence
$\displaystyle{\quad\quad\quad\quad\, a < 1 \implies \varphi(j/2) = \frac{a}{1 - a} =\varphi(l/2) \underset{\frac{j}{2} < j}{\implies} j/2 = l/2 \implies j = l}\quad$ and
$\displaystyle{\quad\quad\quad\quad\, a >1 \implies \varphi\left(\frac{j - 1}{2}\right) = a - 1 =\varphi\left(\frac{l - 1}{2}\right) \implies \frac{j -1}{2} = \frac{l - 1}{2}\implies j = l}$

$\quad\quad\quad\quad$So $K = \mathbb{N}^+$. In other words, $\;\forall m,n \in\mathbb{N}^+\, (\varphi(m) = \varphi(n))\implies (m = n). \quad\square$

[elim]

Remark It is quite interesting: why it's not in the standard analysis text?

[elim]

Code:

def nr(n):
        if n == 1:
                return [1,1]
        r = nr(n/2)
        if n % 2 == 0:
                return [r[0], r[0] + r[1]]
        else:
                return [r[0] + r[1], r[1]]

def rn(x, y = 1):
        if isinstance(x,list):
                if len(x) != 2:
                        return
                r = x
                if (isinstance(r[0],int) and isinstance(r[1],int)) != True:
                        return
                if (r[0] == r[1] and r[0] > 1) or r[0] < 1 or r[1] < 1:
                        return
        else:
                r = [x,y]
                if (isinstance(x,int) and isinstance(y,int)) != True:
                        retrun
                if x < 1 or y < 1 or (x == y and x > 1):
                        return
        if r[0] == r[1]: return 1
        if r[0] < r[1]: return 2*rn(r[0],r[1] -r[0])
        if r[0] > r[1]: return 1 + 2*rn(r[0] - r[1],r[1])

[elim]

The following shows that when $n = 1172, q$ reaches $3$ digit the first time. And it's not $100$.
   

[elim]

$\quad\quad$ This is to say that, start with $p_1 = q_1 = 1$, the reproduction(multiplication) pattern \[\begin{matrix} \frac{p}{q} \\ \swarrow \quad\quad \searrow \\ \frac{p}{p+q} \quad\quad \frac{p+q}{q} \end{matrix}\] $\quad\quad$ generates all positive rationals $\frac{p_n}{q_n}\;(\gcd(p_n,q_n) = 1)$.
$\quad\quad$ And different hereditary paths determine different rationals.

Generation	Member
1	$\frac{1}{1}$
2	$\frac{1}{2} \quad\quad\quad\quad\quad\quad \frac{2}{1}$
3	$\frac{1}{3}\quad\quad\quad \frac{3}{2}\quad\quad\quad \frac{2}{3}\quad\quad\quad \frac{3}{1}$
4	$\quad \frac{1}{4}\quad\: \frac{4}{3}\quad\: \frac{3}{5}\quad\: \frac{5}{2}\quad\: \frac{2}{5}\quad\: \frac{5}{3}\quad\: \frac{3}{4}\quad\: \frac{4}{1}$
$\cdots$	$\cdots \cdots$