Stern-Brocot Tree

A special type of Binary Tree obtained by starting with the fractions and and iterativelyinserting between each two adjacent fractions and . The result can be arranged in tree form asillustrated above. The Farey Sequence defines a subtree of the Stern-Brocot tree obtained by pruning off unwantedbranches (Vardi 1991, Graham et al. 1994).

References

Brocot, A. ``Calcul des rouages par approximation, nouvelle méthode.'' Revue Chonométrique 6, 186-194, 1860.

Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, pp. 116-117, 1994.

Stern, M. A. ``Über eine zahlentheoretische Funktion.'' J. reine angew. Math. 55, 193-220, 1858.

Vardi, I. Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, p. 253, 1991.

• Link
• Linkage
• Link Diagram
• Linking Number
• Links Curve
• Linnik's Constant
• Linnik's Theorem
• Lin's Method
• Liouville Function
• Liouville Measure
• Liouville Number
• Liouville Polynomial Identity
• Liouville-Roth Constant
• Liouville's Boundedness Theorem
• Liouville's Conformality Theorem
• Liouville's Conic Theorem
• Liouville's Constant
• Liouville's Elliptic Function Theorem
• Liouville Space
• Liouville's Phase Space Theorem
• Liouville's Rational Approximation Theorem
• Liouville's Sphere-Preserving Theorem
• Lipschitz Condition
• Lipschitz Function
• Lipschitz's Integral