Stern-Brocot tree

From Wikipedia, the free encyclopedia

Stern-Brocot tree

In number theory, the Stern-Brocot tree is a method of listing all non-negative rational numbers as well as a point representing infinity (here represented formally as 1/0). It was discovered independently by Moritz Stern (1858) and Achille Brocot (1860).

The tree may be created by an iterative process. It is easiest to describe as a list. Beginning with the list {0/1, 1/0} representing 0 and infinity respectively, one places between any two fractions the mediant of the fractions (the mediant of a/c and b/d is (a + b)/(c + d)). The first few steps of this process yield:

{0/1, 1/0}
{0/1, 1/1, 1/0}
{0/1, 1/2, 1/1, 2/1, 1/0}
{0/1, 1/3, 1/2, 2/3, 1/1, 3/2, 2/1, 3/1, 1/0}

This process can be represented as a tree where each row corresponds to the new numbers added at each step. Every positive rational number can be found in this tree exactly once and in lowest terms (i.e. the numerator and denominator are coprime).

The tree is closely tied to the concept of simple continued fractions in canonical form. The value of any finite simple continued fraction in canonical form [a₀; a₁, a₂, ..., a_n] can be found on the tree by starting at 1/1 and choosing the right path a₀ times, then the left path a₁ times, and continuing in this manner until choosing the right or left path (if n is even or odd respectively) a_n – 1 times. For example, 2/5 = [0; 2, 2] and is found by going left twice and right once.

The tree is also intimately related to the Farey sequence. Suppose we start with the endpoints 0/1 and 1/1 instead of 0/1 and 1/0. In this case the tree will contain all rational numbers between 0 and 1, inclusive. However, an in-order traversal of this tree up to a depth n does not in general yield the Farey sequence $\mathfrak F_n.$ This is because for n > 1, the mediant of two adjacent elements of $\mathfrak F_{n-1}$ is inserted between them in $\mathfrak F_n$ only if the denominator of the new fraction would be equal to n. In particular, the part of the Stern-Brocot tree starting with 0/1 and 1/1 up to and including depth n will have 1 + 2ⁿ elements, whereas $\mathfrak F_n$ including 0/1 and 1/1 has only $1 + \sum_{k=1}^n \varphi(k)$ elements.

Stern-Brocot trees can be used to convert floating-point numbers into rational numbers. By using a sort of binary search while constructing the tree and stopping once the desired precision is reached, floating-point numbers can be approximated to arbitrary precision.^[1]