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?

  • 10
    Do you need a formula or does the picture and explanation in en.wikipedia.org/wiki/… suffice? See also en.wikipedia.org/wiki/… – lhf Oct 24 '10 at 3:10
  • I wasn't familiar with pairing functions, so let me look at that more closely. My professor insisted, though, that I come up with a formula, and of course that would also require that equivalent pairs (in the rational number sense) shouldn't get counted more than once. – Alex Basson Oct 24 '10 at 4:55
  • 1
    @lhf. Maybe you should post your comment as an answer; otherwise, it's not unlikey that this question remains unanswered. – d.t. Oct 24 '10 at 5:21
  • Could you provide a list of features that you consider legitimate to include in your formula? Often when these questions are posed, responses are met with "that doesn't count as a formula." – Douglas S. Stones Oct 24 '10 at 5:43
  • 3
    Don't know if it would count as "explicit" but every rational number occurs exactly one in the Calkin-Wilf sequence en.wikipedia.org/wiki/Calkin%E2%80%93Wilf_tree – Jyotirmoy Bhattacharya Oct 24 '10 at 6:42

We will 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)&n>0\\ 0&n=0\\ -h_{+}(-n)&n<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)=\begin{cases} 0&n=0\\ (-1)^n\left\lfloor\frac{n+1}{2}\right\rfloor&n>0 \end{cases} $$

So, the sequence would be $0,-1,1,-2,2\dots$, and this is a bijection from $\mathbb N$ to $\mathbb Z$. The only properties we 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^{+}$.

  • 5
    Why hasn't this been upvoted more? Good answer! (+1) – fancynancy Feb 16 '15 at 17:46
  • 1
    For your bijection between $\mathbb{N}$ and $\mathbb{Q}$, why have you defined it as $\rho_1$ instead of just $\eta$ or something else (I don't see anything to indicate significance of the index)? – fancynancy Feb 16 '15 at 17:52
  • 1
    @fancynancy I think just because it was a variant of $\rho$. I think the function I now call $\rho_1$ was just called $\rho$, but then I realized I needed the intermediate function, which was more "important" in some way, so I called that $\rho$ and renamed this $\rho_1$. It's just a function name. – Thomas Andrews Feb 16 '15 at 18:13
  • 1
    That's what I thought--just wanted to make sure. Thanks for clarifying. – fancynancy Feb 16 '15 at 18:17
  • 1
    Because in each case, only finitely many of the exponents can be non-zero. @RFZ – Thomas Andrews Nov 7 '17 at 22:52

We will first create a bijection from $\mathbb{N}$ to $\mathbb{Q}^{+}$ and then use this to create a bijection from $\mathbb{N}$ to $\mathbb{Q}$.

Step One: Let us first define Stern's diatomic series. This process formalizes the Stern-Brocot tree mentioned above.

$a_{1} = 1 \\ a_{2k}=a_{k} \\ a_{2k+1}=a_{k}+a_{k+1}$

To get a feel for this series, let us list out the first few terms.

$a_{1}=1 \\ a_{2}=a_{1}=1 \\ a_{3}=a_{1}+a_{2}=1+1=2 \\ a_{4}=a_{2}=1 \\ a_{5}=a_{2}+a_{3}=1+2=3 \\ a_{6}=a_{3}=2 \\ a_{7}=a_{3}+a_{4}=2+1=3 \\ a_{8}=a_{4}=1$

Now to obtain the $n^{th}$ rational number, we define $f: \mathbb{N} \rightarrow \mathbb{Q}^{+}$, by $f(n)= \dfrac{a_{n}}{a_{n+1}}$.

Let us list out the first few terms.

$f(1)= a_{1}/a_{1+1} = 1/1 \\ f(2)= a_{2}/a_{2+1} = 1/2 \\ f(3)= a_{3}/a_{3+1} = 2/1 \\ f(4)= a_{4}/a_{4+1} = 1/3 \\ f(5)= a_{5}/a_{5+1} = 3/2 \\ f(6)= a_{6}/a_{6+1} = 2/3 \\ f(7)= a_{7}/a_{7+1} = 3/1 $

This function enables us to say that the $6^{th}$ rational number is $2/3$. Moreover, this function is a bijection. For proof of this, see Theorem 5.1 here http://faculty.plattsburgh.edu/sam.northshield/08-0412.pdf.

Since $f$ is a bijection this implies that $f^{-1}$ exists. That means given a rational number we can find the corresponding natural number. For example suppose you have a fraction, say it is $1/4$. Can we determine the $n$ such that $f(n)=1/4$? The answer is a resounding yes. Given a positive rational number, $q \in \mathbb{Q}$, the $n$ such that $f(n)=q$ is found by $n=f^{-1}(q)$. This function, $f^{-1}$, is given as follows:

$f^{-1}(1)=1 \\ f^{-1}(q)= 2f^{-1} \bigg(\dfrac{q}{1-q} \bigg) ~ \text{if} ~ q<1 \\ f^{-1}(q) = 2f^{-1}(q-1)+1 ~\text{if}~ q>1$

As an example, we see from above that $f(5)={3/2}$. Let us plug $(3/2)$ into $f^{-1}$ and see if we get 5.

$f^{-1}(3/2)=2f^{-1} \bigg(\dfrac{3/2}{1-(3/2)} \bigg)+1=2f^{-1} \bigg(\dfrac{1}{2} \bigg)+1.$ A quick calculation yields that $f^{-1} \bigg(\dfrac{1}{2} \bigg)=2$ and so we get $f^{-1}(3/2)=2f^{-1} \bigg(\dfrac{1}{2} \bigg)+1=2(2)+1=5$.

Step Two: We showed there exists a bijection between $\mathbb{N}$ and $\mathbb{Q}^{+}$. We now attempt to show there exists an explicit bijection between $\mathbb{N}$ and $\mathbb{Q}$. Using the work done in Step One, it appears easier to first create a bijection between $\mathbb{Z}$ and $\mathbb{Q}$. The reason for doing so is because we have already created a bijection from the positive integers (natural numbers) to the positive rationals. So it only seems natural that by adding in the negative integers, we can map them to the negative rationals and thus obtain a bijection. We do this as follows:

$$ g(z) = \begin{cases} \dfrac{a_{z}}{a_{z+1}}, & \text{if } z>0 \\ \\ - \dfrac{a_{-z}}{a_{-(z-1)}}, & \text{if } z<0 \\ \\ 0, & \text{if } z=0 \end{cases} $$ where the $a_{i}$ term refers to the $i^{th}$ term in Stern's diatomic series.

We already referenced a proof by Northshield showing that $g(z)=\dfrac{a_{z}}{a_{z+1}}$ if $z>0$ is a bijection from $\mathbb{N} \rightarrow \mathbb{Q}^{+}$. Equivalently, we may write this as $g$ is a bijection from $\mathbb{Z}^{+}$ to $\mathbb{Q}^{+}$ for $z>0$. Now, it follows by the symmetry of the problem that $g(z)=- \dfrac{a_{-z}}{a_{-(z-1)}}$ is a bijection from $\mathbb{Z}^{-}$ to $\mathbb{Q}^{-}$ if $z<0$. That is, $g$ is a bijection between the negative integers and the negative rationals. So we have covered all the positive and negative rationals. The only element in the rationals that is not accounted for is the zero element. So we shall have the integer $0$ mapping to the rational number $0$. However, $g$ is a bijection from the integers to the rationals. We wish to find a bijection from the natural numbers to the rationals. So we shall now define the well-known bijection from the natural numbers to the integers.

$$ h(n) = \begin{cases} \dfrac{n}{2}, & \text{if }n\text{ is even} \\ -\dfrac{n-1}{2}, & \text{if }n\text{ is odd} \end{cases} $$

You may check for yourself that $h$ is a bijection. It follows that $g~\circ~ h: \mathbb{N} \rightarrow \mathbb{Q}$ is a bijection since the composition of two bijections is a bijection. Thus, we have an explicit bijection from $\mathbb{N}$ to $\mathbb{Q}$.

However, given a rational number, can we find what this rational number maps to in the set of natural numbers? Although I do not prove it, the answer is yes and is given by the following piece-wise defined function which is an extension of the function defined in Step One. We first define $g^{-1}: \mathbb{Q} \rightarrow \mathbb{Z}$ as

$$ g^{-1}(q) = \begin{cases} 2f^{-1}(q-1)+1, & \text{if } q>1 \\ 1, & \text{if } q=1 \\ 2f^{-1} \bigg(\dfrac{q}{1-q} \bigg), & \text{if } 0<q<1 \\ 0, & \text{if } q=0 \\ -2 \Bigg(f^{-1} \bigg(\dfrac{-q}{1+q}\bigg) \Bigg), & \text{if } -1<q<0 \\ -1, & \text{if } q=-1 \\ -2(f^{-1}(-q-1)+1), & \text{if } q<-1 \end{cases} $$

We now define the function $h^{-1}: \mathbb{Z} \rightarrow \mathbb{N}$ as follows:

$$ h^{-1}(z)= \begin{cases} 2z, & \text{if } z>0 \\ 1, & \text{if } z=0 \\ -2z-1, & \text{if } z<0 \\ \end{cases} $$

Then $h^{-1} \circ g^{-1}: \mathbb{Q} \rightarrow \mathbb{N}$ is the bijection we are looking for.

Preliminaries

I will use the Continued Fraction conception. First, let us consider only rationals that are less than 1. So $$q < 1, \quad q\in\mathbb{Q}$$ So every rational $q$ can be written as continued fraction: $$q = \cfrac{1}{a_1 + \cfrac{1}{a_2 +\cfrac{1}{a_3 + ...}}} := [a_1, a_2, a_3, ...]$$ Note that none of the $a_i$ is zero and for every $q\in\mathbb{Q}$ its q.f. is of finite length. Also note that we use only that kind of q.f.'s in which all numerators are 1's.

Formula

Let us construct a bijection $\Phi$ between rationals and naturals as follows: $$\Phi: q \mapsto \prod_{i=1}^{n_q}p_{i}^{a_i - 1},$$ where $n_q$ is length of q.f. for $q$ and $p_i$ is $i$th prime number. The inverse is straightforward.

Example

$$\Phi\Big(\frac{30}{43}\Big) = 2^03^15^27^3 = 25725$$ This is because $$\frac{30}{43} = \cfrac{1}{1+\cfrac{1}{2+\cfrac{1}{3+\cfrac{1}{4}}}} := [1,2,3,4]$$ And vice-versa: $$\Phi^{-1}(225) = \frac{10}{13} = \cfrac{1}{1+\cfrac{1}{3+\cfrac{1}{3}}}$$ This is because $$225 = 2^03^25^2$$


Of course this works iff there is bijection between those kind of continued fractions and rationals. But it is not too hard to prove.


P.S. I feel that I miss something. Please, verify.

  • It's very good! It provides a bijection between $\mathbb{Q} \cap (0,1)$ and the integers $>0$. Indeed, any such positive integer corresponds to an element of finite support in $\prod_{p } \mathbb{N}$. Any such element of finite support, increase by $1$ all the components up to the last $\ne 0$ element, Now compose the continued fraction from it (implicitly you use that the continued fraction does not end with $1$ as a last quotient). – orangeskid Oct 11 '17 at 16:59
  • @orangeskid, It is impossible (nonsense) for q.f. to end with 1. – LRDPRDX Oct 11 '17 at 17:55
  • @Wolfgang Very interesting, and thank you! This second example, however, confuses me. As you observe, $\frac{10}{13} := [1, 3, 3]$. So shouldn't $\Phi(\frac{10}{13}) = 2^{1-1}3^{3-1}5^{3-1} = 2^03^25^2 = 225$? – Alex Basson Oct 12 '17 at 0:50
  • @AlexBasson, Good catch! Of course, should. – LRDPRDX Oct 12 '17 at 3:13

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.

Recently I was reading some papers by Don Zagier and found this one most interesting. Here, you can get not only a satisfactory proof of the bijection, but also you will have the notion of the rational number immediately after, or before, a given number, which we don't have in Cantor's proof.

Theorem:

The map $$S(x)=\frac{1}{2\lfloor x\rfloor-x+1}$$ has the property that, among the sequence $S(0),S(S(0),S(S(S(0)),\cdots $ every positive rational numbers appears once and only once.

Therefore if we write $S^n(x)$ for $n^{th}$ iterate of $S$, then we obtain an explicit bijection $F:\mathbb{N}\to \mathbb{Q^+}$ by $F(n)=S^n(0) $. The proof is explained in the link I have mentioned above.

The method used here cobbles together parts and pieces of the Euler's totient function to create our sequence that bijectively covers all the rational numbers.

The function is implemented using the python programming language, but the interested reader can figure out what is happening by inspecting the output.

Here is the program:

#--------*---------*---------*---------*---------*---------*---------*---------*
# Desc: Define a bijection of natural numbers to the rational numbers
#--------*---------*---------*---------*---------*---------*---------*---------*

import sys
import fractions

def moreTicks(curTick):
    for k in range(1, curTick):
        if fractions.gcd(curTick, k) == 1:
            moreTicksList.append(fractions.Fraction(k, curTick))
    return curTick + 1


#--------*---------*---------*---------*---------*---------*---------*---------#
while True:#                       M A I N L I N E                             #
#--------*---------*---------*---------*---------*---------*---------*---------#
#                                  # initialize state of function machine
    step = 0
    negSide = 0
    posSide = 0
    curTick = 2
    phiList = []
    print(0, ', ', end='')

    while True:
        #print('expand by phi(n) count on working range')
        moreTicksList = []
        curTick = moreTicks(curTick)
        for i in range(negSide, posSide + 1):
            for f in moreTicksList:
                print(f + fractions.Fraction(i, 1), ', ', end='')
        for f in moreTicksList:
            phiList.append(f)
        #print("add phiList to '-' side")
        negSide = negSide - 1
        print(negSide, ', ', end='')
        for f in phiList:
            print(f + fractions.Fraction(negSide, 1), ', ', end='')
        #print("add phiList to '+' side")
        posSide = posSide + 1
        print(posSide, ', ', end='')
        for f in phiList:
            print(f + fractions.Fraction(posSide, 1), ', ', end='')
        step = step + 1
        if step == 7:
            print('...', end='')
            sys.exit()

Here is the output sequence (you can use the slider to see further out):

0 , 1/2 , -1 , -1/2 , 1 , 3/2 , -2/3 , -1/3 , 1/3 , 2/3 , 4/3 , 5/3 , -2 , -3/2 , -5/3 , -4/3 , 2 , 5/2 , 7/3 , 8/3 , -7/4 , -5/4 , -3/4 , -1/4 , 1/4 , 3/4 , 5/4 , 7/4 , 9/4 , 11/4 , -3 , -5/2 , -8/3 , -7/3 , -11/4 , -9/4 , 3 , 7/2 , 10/3 , 11/3 , 13/4 , 15/4 , -14/5 , -13/5 , -12/5 , -11/5 , -9/5 , -8/5 , -7/5 , -6/5 , -4/5 , -3/5 , -2/5 , -1/5 , 1/5 , 2/5 , 3/5 , 4/5 , 6/5 , 7/5 , 8/5 , 9/5 , 11/5 , 12/5 , 13/5 , 14/5 , 16/5 , 17/5 , 18/5 , 19/5 , -4 , -7/2 , -11/3 , -10/3 , -15/4 , -13/4 , -19/5 , -18/5 , -17/5 , -16/5 , 4 , 9/2 , 13/3 , 14/3 , 17/4 , 19/4 , 21/5 , 22/5 , 23/5 , 24/5 , -23/6 , -19/6 , -17/6 , -13/6 , -11/6 , -7/6 , -5/6 , -1/6 , 1/6 , 5/6 , 7/6 , 11/6 , 13/6 , 17/6 , 19/6 , 23/6 , 25/6 , 29/6 , -5 , -9/2 , -14/3 , -13/3 , -19/4 , -17/4 , -24/5 , -23/5 , -22/5 , -21/5 , -29/6 , -25/6 , 5 , 11/2 , 16/3 , 17/3 , 21/4 , 23/4 , 26/5 , 27/5 , 28/5 , 29/5 , 31/6 , 35/6 , -34/7 , -33/7 , -32/7 , -31/7 , -30/7 , -29/7 , -27/7 , -26/7 , -25/7 , -24/7 , -23/7 , -22/7 , -20/7 , -19/7 , -18/7 , -17/7 , -16/7 , -15/7 , -13/7 , -12/7 , -11/7 , -10/7 , -9/7 , -8/7 , -6/7 , -5/7 , -4/7 , -3/7 , -2/7 , -1/7 , 1/7 , 2/7 , 3/7 , 4/7 , 5/7 , 6/7 , 8/7 , 9/7 , 10/7 , 11/7 , 12/7 , 13/7 , 15/7 , 16/7 , 17/7 , 18/7 , 19/7 , 20/7 , 22/7 , 23/7 , 24/7 , 25/7 , 26/7 , 27/7 , 29/7 , 30/7 , 31/7 , 32/7 , 33/7 , 34/7 , 36/7 , 37/7 , 38/7 , 39/7 , 40/7 , 41/7 , -6 , -11/2 , -17/3 , -16/3 , -23/4 , -21/4 , -29/5 , -28/5 , -27/5 , -26/5 , -35/6 , -31/6 , -41/7 , -40/7 , -39/7 , -38/7 , -37/7 , -36/7 , 6 , 13/2 , 19/3 , 20/3 , 25/4 , 27/4 , 31/5 , 32/5 , 33/5 , 34/5 , 37/6 , 41/6 , 43/7 , 44/7 , 45/7 , 46/7 , 47/7 , 48/7 , -47/8 , -45/8 , -43/8 , -41/8 , -39/8 , -37/8 , -35/8 , -33/8 , -31/8 , -29/8 , -27/8 , -25/8 , -23/8 , -21/8 , -19/8 , -17/8 , -15/8 , -13/8 , -11/8 , -9/8 , -7/8 , -5/8 , -3/8 , -1/8 , 1/8 , 3/8 , 5/8 , 7/8 , 9/8 , 11/8 , 13/8 , 15/8 , 17/8 , 19/8 , 21/8 , 23/8 , 25/8 , 27/8 , 29/8 , 31/8 , 33/8 , 35/8 , 37/8 , 39/8 , 41/8 , 43/8 , 45/8 , 47/8 , 49/8 , 51/8 , 53/8 , 55/8 , -7 , -13/2 , -20/3 , -19/3 , -27/4 , -25/4 , -34/5 , -33/5 , -32/5 , -31/5 , -41/6 , -37/6 , -48/7 , -47/7 , -46/7 , -45/7 , -44/7 , -43/7 , -55/8 , -53/8 , -51/8 , -49/8 , 7 , 15/2 , 22/3 , 23/3 , 29/4 , 31/4 , 36/5 , 37/5 , 38/5 , 39/5 , 43/6 , 47/6 , 50/7 , 51/7 , 52/7 , 53/7 , 54/7 , 55/7 , 57/8 , 59/8 , 61/8 , 63/8 , ...

The sequence 'calibrates' the rational number 'tick marks' on our ideal 'measuring rod'.

Some of the theory used in the answers have applications such as cryptography, and so I started thinking about finding computer efficient algorithms.

We've seen above that once we can enumerate all the rational numbers between $0$ and $1$, we can translate these rational numbers $r$ via integer addition $m+r$ to get the whole ball of wax.

I found a method in wikipedia of generating all coprime pairs that we can plug into.

Here is the python program:

#--------*---------*---------*---------*---------*---------*---------*---------*
# Desc: Enumerate rational numbers between 0 and 1
#--------*---------*---------*---------*---------*---------*---------*---------*
import sys
from collections import deque


#--------*---------*---------*---------*---------*---------*---------*---------#
while True:#                       M A I N L I N E                             #
#--------*---------*---------*---------*---------*---------*---------*---------#
#                                  # initialize state of function machine
    step = 0
    O1 = deque()
    O1.append((2,1))
    O2 = deque()
    O2.append((3,1))
#                                  # Branch 1: (2m-n,m)
#                                  # Branch 2: (2m+n,m)
#                                  # Branch 3: (m+2n,n)
    while True:
        p = O1.popleft()
        print(str(p[1]) + '/' + str(p[0]), '', end='')
        O1.append( (2*p[0] - p[1], p[0]) )
        O1.append( (2*p[0] + p[1], p[0]) )
        O1.append( (p[0] + 2*p[1], p[1]) )        
        p = O2.popleft()
        print(str(p[1]) + '/' + str(p[0]), '', end='')
        O2.append( (2*p[0] - p[1], p[0]) )
        O2.append( (2*p[0] + p[1], p[0]) )
        O2.append( (p[0] + 2*p[1], p[1]) )        
        step = step + 1
        if step == 500:
            print('...')
            print('The first', 2*step, 'rational numbers have been enumerated.')
            print('Each queue has', len(O1), 'items to be processed.')
            sys.exit()

As time goes on the memory requirement grow. After printing the $(2 \times n)^\text {th}$ fraction, each of the two queues will contain $2 n + 1$ items.

Here is the output:

1/2 1/3 2/3 3/5 2/5 3/7 1/4 1/5 3/4 5/7 3/8 5/13 2/7 3/11 5/8 7/11 5/12 7/17 2/9 3/13 4/7 5/9 4/9 5/11 1/6 1/7 4/5 7/9 4/11 7/19 3/10 5/17 8/13 13/21 8/19 13/31 3/14 5/23 7/12 11/19 7/16 11/25 2/11 3/17 8/11 11/15 8/21 11/29 5/18 7/25 12/19 17/27 12/29 17/41 5/22 7/31 9/16 13/23 9/20 13/29 2/13 3/19 7/10 9/13 7/18 9/23 4/15 5/19 9/14 11/17 9/22 11/27 4/17 5/21 6/11 7/13 6/13 7/15 1/8 1/9 5/6 9/11 5/14 9/25 4/13 7/23 11/18 19/31 11/26 19/45 4/19 7/33 10/17 17/29 10/23 17/39 3/16 5/27 13/18 21/29 13/34 21/55 8/29 13/47 19/30 31/49 19/46 31/75 8/35 13/57 14/25 23/41 14/31 23/51 3/20 5/33 12/17 19/27 12/31 19/49 7/26 11/41 16/25 25/39 16/39 25/61 7/30 11/47 11/20 17/31 11/24 17/37 2/15 3/23 11/14 15/19 11/30 15/41 8/27 11/37 21/34 29/47 21/50 29/69 8/37 11/51 18/31 25/43 18/41 25/57 5/28 7/39 19/26 27/37 19/50 27/71 12/43 17/61 29/46 41/65 29/70 41/99 12/53 17/75 22/39 31/55 22/49 31/69 5/32 7/45 16/23 23/33 16/41 23/59 9/34 13/49 20/31 29/45 20/49 29/71 9/38 13/55 13/24 19/35 13/28 19/41 2/17 3/25 10/13 13/17 10/27 13/35 7/24 9/31 18/29 23/37 18/43 23/55 7/32 9/41 15/26 19/33 15/34 19/43 4/23 5/29 14/19 17/23 14/37 17/45 9/32 11/39 22/35 27/43 22/53 27/65 9/40 11/49 17/30 21/37 17/38 21/47 4/25 5/31 11/16 13/19 11/28 13/33 6/23 7/27 13/20 15/23 13/32 15/37 6/25 7/29 8/15 9/17 8/17 9/19 1/10 1/11 6/7 11/13 6/17 11/31 5/16 9/29 14/23 25/41 14/33 25/59 5/24 9/43 13/22 23/39 13/30 23/53 4/21 7/37 18/25 31/43 18/47 31/81 11/40 19/69 26/41 45/71 26/63 45/109 11/48 19/83 19/34 33/59 19/42 33/73 4/27 7/47 17/24 29/41 17/44 29/75 10/37 17/63 23/36 39/61 23/56 39/95 10/43 17/73 16/29 27/49 16/35 27/59 3/22 5/37 18/23 29/37 18/49 29/79 13/44 21/71 34/55 55/89 34/81 55/131 13/60 21/97 29/50 47/81 29/66 47/107 8/45 13/73 30/41 49/67 30/79 49/129 19/68 31/111 46/73 75/119 46/111 75/181 19/84 31/137 35/62 57/101 35/78 57/127 8/51 13/83 25/36 41/59 25/64 41/105 14/53 23/87 31/48 51/79 31/76 51/125 14/59 23/97 20/37 33/61 20/43 33/71 3/26 5/43 17/22 27/35 17/46 27/73 12/41 19/65 31/50 49/79 31/74 49/117 12/55 19/87 26/45 41/71 26/59 41/93 7/40 11/63 25/34 39/53 25/66 39/103 16/57 25/89 39/62 61/97 39/94 61/147 16/71 25/111 30/53 47/83 30/67 47/105 7/44 11/69 20/29 31/45 20/51 31/79 11/42 17/65 24/37 37/57 24/59 37/91 11/46 17/71 15/28 23/43 15/32 23/49 2/19 3/29 14/17 19/23 14/39 19/53 11/36 15/49 30/49 41/67 30/71 41/97 11/52 15/71 27/46 37/63 27/62 37/85 8/43 11/59 34/47 47/65 34/89 47/123 21/76 29/105 50/79 69/109 50/121 69/167 21/92 29/127 37/66 51/91 37/82 51/113 8/53 11/73 31/44 43/61 31/80 43/111 18/67 25/93 41/64 57/89 41/100 57/139 18/77 25/107 28/51 39/71 28/61 39/85 5/38 7/53 26/33 37/47 26/71 37/101 19/64 27/91 50/81 71/115 50/119 71/169 19/88 27/125 43/74 61/105 43/98 61/139 12/67 17/95 46/63 65/89 46/121 65/171 29/104 41/147 70/111 99/157 70/169 99/239 29/128 41/181 53/94 75/133 53/118 75/167 12/77 17/109 39/56 55/79 39/100 55/141 22/83 31/117 49/76 69/107 49/120 69/169 22/93 31/131 32/59 45/83 32/69 45/97 5/42 7/59 23/30 33/43 23/62 33/89 16/55 23/79 41/66 59/95 41/98 59/141 16/73 23/105 34/59 49/85 34/77 49/111 9/52 13/75 31/42 45/61 31/82 45/119 20/71 29/103 49/78 71/113 49/118 71/171 20/89 29/129 38/67 55/97 38/85 55/123 9/56 13/81 24/35 35/51 24/61 35/89 13/50 19/73 28/43 41/63 28/69 41/101 13/54 19/79 17/32 25/47 17/36 25/53 2/21 3/31 13/16 17/21 13/36 17/47 10/33 13/43 27/44 35/57 27/64 35/83 10/47 13/61 24/41 31/53 24/55 31/71 7/38 9/49 29/40 37/51 29/76 37/97 18/65 23/83 43/68 55/87 43/104 55/133 18/79 23/101 32/57 41/73 32/71 41/91 7/46 9/59 26/37 33/47 26/67 33/85 15/56 19/71 34/53 43/67 34/83 43/105 15/64 19/81 23/42 29/53 23/50 29/63 4/31 5/39 19/24 23/29 19/52 23/63 14/47 17/57 37/60 45/73 37/88 45/107 14/65 17/79 32/55 39/67 32/73 39/89 9/50 11/61 35/48 43/59 35/92 43/113 22/79 27/97 53/84 65/103 53/128 65/157 22/97 27/119 40/71 49/87 40/89 49/109 9/58 11/71 30/43 37/53 30/77 37/95 17/64 21/79 38/59 47/73 38/93 47/115 17/72 21/89 25/46 31/57 25/54 31/67 4/33 5/41 16/21 19/25 16/43 19/51 11/38 13/45 28/45 33/53 28/67 33/79 11/50 13/59 23/40 27/47 23/52 27/61 6/35 7/41 20/27 23/31 20/53 23/61 13/46 15/53 32/51 37/59 32/77 37/89 13/58 15/67 25/44 29/51 25/56 29/65 6/37 7/43 15/22 17/25 15/38 17/43 8/31 9/35 17/26 19/29 17/42 19/47 8/33 9/37 10/19 11/21 10/21 11/23 1/12 1/13 7/8 13/15 7/20 13/37 6/19 11/35 17/28 31/51 17/40 31/73 6/29 11/53 16/27 29/49 16/37 29/67 5/26 9/47 23/32 41/57 23/60 41/107 14/51 25/91 33/52 59/93 33/80 59/143 14/61 25/109 24/43 43/77 24/53 43/95 5/34 9/61 22/31 39/55 22/57 39/101 13/48 23/85 30/47 53/83 30/73 53/129 13/56 23/99 21/38 37/67 21/46 37/81 4/29 7/51 25/32 43/55 25/68 43/117 18/61 31/105 47/76 81/131 47/112 81/193 18/83 31/143 40/69 69/119 40/91 69/157 11/62 19/107 41/56 71/97 41/108 71/187 26/93 45/161 63/100 109/173 63/152 109/263 26/115 45/199 48/85 83/147 48/107 83/185 11/70 19/121 34/49 59/85 34/87 59/151 19/72 33/125 42/65 73/113 42/103 73/179 19/80 33/139 27/50 47/87 27/58 47/101 4/35 7/61 24/31 41/53 24/65 41/111 17/58 29/99 44/71 75/121 44/105 75/179 17/78 29/133 37/64 63/109 37/84 63/143 10/57 17/97 36/49 61/83 36/95 61/161 23/82 39/139 56/89 95/151 56/135 95/229 23/102 39/173 43/76 73/129 43/96 73/163 10/63 17/107 29/42 49/71 29/74 49/125 16/61 27/103 35/54 59/91 35/86 59/145 16/67 27/113 22/41 37/69 22/47 37/79 3/28 5/47 23/28 37/45 23/64 37/103 18/59 29/95 49/80 79/129 49/116 79/187 18/85 29/137 44/75 71/121 44/101 71/163 13/70 21/113 55/76 89/123 55/144 89/233 34/123 55/199 81/128 131/207 81/196 131/317 34/149 55/241 60/107 97/173 60/133 97/215 13/86 21/139 50/71 81/115 50/129 81/209 29/108 47/175 66/103 107/167 66/161 107/261 29/124 47/201 45/82 73/133 45/98 73/159 8/61 13/99 41/52 67/85 41/112 67/183 30/101 49/165 79/128 129/209 79/188 129/307 30/139 49/227 68/117 111/191 68/155 111/253 19/106 31/173 73/100 119/163 73/192 119/313 46/165 75/269 111/176 181/287 111/268 181/437 46/203 75/331 84/149 137/243 84/187 137/305 19/122 31/199 62/89 101/145 62/159 101/259 35/132 57/215 78/121 127/197 78/191 127/311 35/148 57/241 51/94 83/153 51/110 83/179 8/67 13/109 36/47 59/77 ...
The first 1000 rational numbers have been enumerated.
Each queue has 1001 items to be processed.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.