Jump to content

Stern–Brocot tree: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
see also: Farey sequence
Line 18: Line 18:
== See also ==
== See also ==
* [[Farey sequence]], which the Stern-Brocot tree is intimitely related to.
* [[Farey sequence]], which the Stern-Brocot tree is intimitely related to.


According to the referenced article "On the Teeth of Wheels" by Brian Hayes in the Sigma Xi journal American Scientist, the proper first name of Stern was Moritz, not Moriz. Moritz Abraham Stern succeeded Gauss as Ordinary Professor of Mathematics.


==External links==
==External links==

Revision as of 01:56, 21 May 2006

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/b and c/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.

Stern-Brocot tree

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 continued fractions. For any continued fraction [a0;a1,a2,...,an], its value can be found on the tree by starting at 1/1 and choosing the right path a0 times, then the left path a1 times, and continuing in this manner until choosing the right or left path (if n is even or odd resp.) an - 1 times. For example, 2/5 = [0;2,2] and is found by going left twice and right once.

See also


According to the referenced article "On the Teeth of Wheels" by Brian Hayes in the Sigma Xi journal American Scientist, the proper first name of Stern was Moritz, not Moriz. Moritz Abraham Stern succeeded Gauss as Ordinary Professor of Mathematics.