Listing the Rational Numbers II: The Stern-Brocot Tree

The rational numbers are countable: they can be put into one-to-one correspondence with the natural numbers. But it is not obvious how to construct a list that is sure to contain every rational number precisely once. In a previous post we described the Farey Sequences. Here we examine another, related, approach.

Mediant-red

The Stern-Brocot Tree

We consider a tree structure that contains each positive rational number precisely once. It was devised independently by Moritz Stern, a German number theorist and Achille Brocot, a French clockmaker. Brocot was interested in designing gear systems with specific gear ratios, constrained by engineering practicalities.

We start with two boundary values, ${\frac{0}{1}}$ to represent ${0}$ and ${\frac{1}{0}}$ to represent ${\infty}$ . They are not members of the tree, but are used to generate new entries by forming mediants. Recall that the mediant of two rational numbers ${m_1 / n_1}$ and ${m_2 / n_2}$ is

$\displaystyle \mbox{Mediant}\left(\frac{m_1}{n_1},\frac{m_2}{n_2}\right) = \frac{m_1+m_2}{n_1+n_2}$

and its value always falls between the two numbers.

The root of the tree is ${{1}/{1}}$ , which is the mediant of the boundary values. Thus, at Level 1 we have three numbers ${\{\frac{0}{1}, \frac{1}{1}, \frac{1}{0} \}}$ . This is the first Stern-Brocot sequence. To construct a new level, we form the mediant of each adjacent pair of ratios in the level above. Thus, if there are ${K}$ entries at level ${k}$ , there are ${K-1}$ new entries at Level ${k+1}$ . If we now carry down the ${K}$ numbers at Level ${k}$ to Level ${k+1}$ , we get the ${(k+1)}$ st Stern-Brocot sequence, which has ${2K-1}$ entries. This is then used to generate the new entries of the sequence at Level ${k+2}$ .

If we include only new entries at each level, we see that all rationals can be included in a tree structure (see Figure below), and each rational occurs precisely once. Every branch of the tree bifurcates at every level. Each number in the tree has two “children” but only one “parent”. For a rational ${r=p/q}$ , the left child is smaller than ${r}$ while the right child is greater. Explicit values for the children can be expressed in terms of continued fractions.

The Stern-Brocot tree and Stern-Brocot sequences of order n for n from 1 to 4. [ Image from Wikimedia Commons].

The Stern-Brocot sequence of order ${k}$ , which comprises all entries in the first ${k}$ levels of the tree, together with the two boundary values, arranged in ascending order, has ${2^k+1}$ ratios. For example, the 4 ${^\mathrm{th}}$ sequence is

$\displaystyle SB_4 = \biggl\{ \frac{0}{1}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1}, \frac{4}{3}, \frac{3}{2}, \frac{5}{3}, \frac{2}{1}, \frac{5}{2}, \frac{3}{1}, \frac{4}{1}, \frac{1}{0} \biggr\}$

For comparison, the 4 ${^\mathrm{th}}$ Farey sequence is

$\displaystyle F_4 = \biggl\{ \frac{0}{1}, \frac{1}{4}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1} \biggr\}$

The process of generating the Stern-Brocot tree has some similarity to that used to generate the Farey sequences. But, at each stage, all the mediants are included, not only those having a specific value of the denominator. Moreover, the Stern-Brocot tree includes all positive rationals, not just those in the interval ${[0,1]}$ .

$\displaystyle \begin{array}{ccccc cccccc ccccc ccccc} \phantom{\biggl[} SB_1 = \bigl\{ & \frac{0}{1} & & & & & & & & \frac{1}{1} & & & & & & & & \frac{1}{0} & \bigr\} \\ \phantom{\biggl[} SB_1 = \bigl\{ & \frac{0}{1} & & & & \frac{1}{2} & & & & \frac{1}{1} & & & & \frac{2}{1} & & & & \frac{1}{0} & \bigr\} \\ \phantom{\biggl[} SB_1 = \bigl\{ & \frac{0}{1} & & \frac{1}{3} & & \frac{1}{2} & & \frac{2}{3} & & \frac{1}{1} & & \frac{3}{2} & & \frac{2}{1} & & \frac{3}{1} & & \frac{1}{0} & \bigr\} \\ \phantom{\biggl[} SB_1 = \bigl\{ & \frac{0}{1} & \frac{1}{4} & \frac{1}{3} & \frac{2}{5} & \frac{1}{2} & \frac{3}{5} & \frac{2}{3} & \frac{3}{4} & \frac{1}{1} & \frac{4}{3} & \frac{3}{2} & \frac{5}{3} & \frac{2}{1} & \frac{5}{2} & \frac{3}{1} & \frac{4}{1} & \frac{1}{0} & \bigr\} \\ \end{array}$

Stern-Brocot sequences of orders 1 to 4, arranged to show new entries at each stage.

The Calkin-Wilf Tree

In a following article, we will introduce another structure, the Calkin-Wilf Tree. It is quite similar to the Stern-Brocot tree, but the differences are interesting.

Sources

${\bullet}$ Wikipedia article Stern-Brocot Tree.

ThatsMaths