The Stern-Brocot or Farey Tree

This article page is a stub, please help by expanding it.

This article needs more work.

Please help by expanding it!

There are several versions of this tree. This one, which appears in (Graham, Knuth and Patashnik 1990, p. 117), was drawn by Alexander Bogomolny. For another version see J. C. Lagarias, Number Theory and Dynamical Systems, pp. 35-72 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc.

The nth order Farey series is the set of reduced fractions between 0 and 1 whose denominators are n or less, arranged in increasing order, and corresponds to a subtree of the Stern-Brocot tree.

There are also many associated sequences:

• The numerators and denominators of the fractions in the full tree give A007305/A047679.
• The numerators and denominators of the fractions in the left-hand subtree give A007305/A007306.
• The numerators and denominators of the triangle whose nth row consists of the Farey series of order n give A006842/A006843.
• See also A049455/A049456, A002487 and A057431.

Extensions to the Stern-Brocot tree

One way to extend the Stern-Brocot tree to cover whole $\scriptstyle \mathbb {Q} \,$, not just the positive rationals, is to reflect it over the "Y-axis" where zero, (i.e. fraction $\scriptstyle {\frac {0}{1}}\,$) is located, and make the fractions on the left side all negative. (See A057114 for example.) (XXX - We need here an illustration like above.)

References

• Graham, R. L.; Knuth, D. E. & Patashnik, O. (1990). Concrete Mathematics. Reading, MA: Addison-Wesley. 

Authorship

The original version of this page was written by Neil Sloane. (The initial version was copied from http://oeis.org/stern_brocot.html but is intended to be filled with more information!)

Further additions by Antti Karttunen.

Cite this page as

N. J. A. Sloane, <insert your name here if you added anything essential>, et al., <a href="http://oeis.org/wiki/The_Stern-Brocot_or_Farey_Tree">The Stern-Brocot or Farey Tree</a>, OEIS Wiki.