This site is supported by donations to The OEIS Foundation.

# The Stern-Brocot or Farey Tree

### From OeisWiki

**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^{[1]}. 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.

## Contents |

## Extensions to the Stern-Brocot tree

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

## Notes

- ↑ Alexander Bogomolny, http://www.cut-the-knot.org/blue/Stern.shtml

## 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.