page_title: Calkin–Wilf tree
hierarchical_section_title: Calkin–Wilf tree
caption_attribution_description: English: A page from J. Kepler's "Harmonices Mundi Libri V", Lib III, Chap. II ("Kepler tree") Русский: Страница из "Гармонии мира" И. Кеплера (кн. III, ч. II) - построение так называемого "Дерева Кеплера"
context_page_description: In number theory, the Calkin–Wilf tree is a tree in which the vertices correspond one-to-one to the positive rational numbers. The tree is rooted at the number 1, and any rational number expressed in simplest terms as the fraction has as its two children the numbers and. Every positive rational number appears exactly once in the tree.
  The sequence of rational numbers in a breadth-first traversal of the Calkin–Wilf tree is known as the Calkin–Wilf sequence. Its sequence of numerators is Stern's diatomic series, and can be computed by the fusc function.
  The Calkin–Wilf tree is named after Neil Calkin and Herbert Wilf, who considered it in their 2000 paper. The tree was introduced earlier by Jean Berstel and Aldo de Luca as Raney tree, since they drew some ideas from a paper by George N. Raney. Stern's diatomic series was formulated much earlier by Moritz Abraham Stern, a 19th-century German mathematician who also invented the closely related Stern–Brocot tree. Even earlier, a similar tree appears in Kepler's Harmonices Mundi.
context_section_description: In number theory, the Calkin–Wilf tree is a tree in which the vertices correspond one-to-one to the positive rational numbers. The tree is rooted at the number 1, and any rational number expressed in simplest terms as the fraction  has as its two children the numbers  and . Every positive rational number appears exactly once in the tree.
  The sequence of rational numbers in a breadth-first traversal of the Calkin–Wilf tree is known as the Calkin–Wilf sequence. Its sequence of numerators (or, offset by one, denominators) is Stern's diatomic series, and can be computed by the fusc function.
  The Calkin–Wilf tree is named after Neil Calkin and Herbert Wilf, who considered it in their 2000 paper. The tree was introduced earlier by Jean Berstel and Aldo de Luca as Raney tree, since they drew some ideas from a paper by George N. Raney. Stern's diatomic series was formulated much earlier by Moritz Abraham Stern, a 19th-century German mathematician who also invented the closely related Stern–Brocot tree. Even earlier, a similar tree appears in Kepler's Harmonices Mundi (1619).
caption: The tree from Kepler's Harmonices Mundi (1619)
exif: {}