Stern-Brocot tree

__NOTOC__

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) in a tree structure. 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.

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 ^"n" elements, whereas $mathfrak\; F\_n$ including 0/1 and 1/1 has only $1\; +\; sum\_\{k=1\}^n\; varphi(k)$ elements.

Properties

* Every positive rational number can be found in this tree exactly once in lowest terms (i.e. the numerator and denominator are coprime)cite web | title=Stern Brocot-Tree | url=http://www.cut-the-knot.org/blue/Stern.shtml | accessdate=2008-09-03 | publisher=cut-the-knot.]

* The Stern-Brocot tree is an (infinite) binary search tree; that is, the rational numbers within it are sorted in natural order.

* If $\{\; frac\{p\_1\}\{q\_1\},\; frac\{p\_2\}\{q\_2\},\; ...\; frac\{p\_n\}\{q\_n\}\; \}$ are all the rationals at the same depth in the Stern-Brocot tree, then$sum\_\{k=1\}^n\; frac\{1\}\{p\_kq\_k\}\; =\; 1$.

Applications

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. [Sedgewick and Wayne, "Introduction to Programming in Java". A Java implementation of this algorithm can be found [http://www.cs.princeton.edu/introcs/92symbolic/RationalApprox.java.html here] .]

References

External links

*
*