MY AMERICAN SCIENTIST
SEARCH

HOME > PAST ISSUE > July-August 2000 > Article Detail

COMPUTING SCIENCE

The Stern-Brocot Tree

The story begins a year ago, when I was writing in this space about the work of Divakar Viswanath (now at the University of Chicago) on a randomized version of the Fibonacci numbers. In the ordinary Fibonacci sequence (1, 1, 2, 3, 5, 8, 13,...) you form each term by adding the two previous terms. In the "Vibonacci" series, you either add or subtract, with each operation chosen at random. You might guess that random additions and subtractions would tend to cancel each other out, but Viswanath proved that the terms grow steadily in absolute value.

Viswanath’s proof makes use of an object from number theory called the Stern-Brocot tree, which is constructed as follows. Take any two rational numbers, a/b and c/d, and insert between them a third value, called the mediant, equal to (a+c)/(b+d). For example, starting with 2/3 and 3/4 yields the mediant (2+3)/(3+4), or 5/7. Now, with three numbers in hand, construct mediants between the first and second and between the second and third, so that the next level of the tree has five members. The process can continue indefinitely. Note that on each level the numbers are always in order.

The canonical version of the Stern-Brocot tree starts with the numbers 0/1 and 1/0. (The second of these "numbers" is admittedly peculiar; somebody has said it is "infinity reduced to lowest terms.") With these starting values, the second level of the tree consists of 0/1, 1/1 and 1/0, and the third level becomes 0/1, 1/2, 1/1, 2/1 and 1/0. (See Figure 2.) The remarkable thing about the tree is that every rational number appears somewhere among its leaves, but no number appears more than once.

When I described the Stern-Brocot tree in my earlier article, I mentioned that it is named for "the mathematician Moriz Stern and the watchmaker Achille Brocot." Now I must make a confession. Although Viswanath's paper cited the works of Stern and Brocot, I did not look up those references. At the time, I excused this lapse of diligence on the grounds that Viswanath himself gave a lucid account of the tree's construction, and I also had an excellent secondary source, namely the textbook Concrete Mathematics, by Ronald L. Graham, Donald E. Knuth and Oren Patashnik. I knew what I needed to know of the tree without tracking down two obscure 19th-century papers written in German and French. Or I thought I knew. In fact I didn't know what I was missing.