Stern-Brocot tree

From Wikipedia, the free encyclopedia

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 Moriz 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. Moreover, an in-order traversal of the first k levels yields the Farey sequence F_k. Put another way, the iterative list construction followed above will precisely construct each of the Farey sequences F_k for increasing k in turn. This should come as no surprise, since in any triple of elements ^a⁄_b < ^p⁄_q < ^c⁄_d in a Farey sequence, the middle element ^p⁄_q is the mediant of the other two. The tree is often referred to as the Farey Tree, due to its excellent illustration of this mediant arithmetic.