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. It is named after Neil Calkin and Herbert Wilf, but appears in other works including Kepler's Harmonices Mundi. 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. History The Calkin–Wilf tree is named after Neil Calkin and Herbert Wilf, who considered it in a 2000 paper. In a 1997 paper, Jean Berstel and Aldo de Luca called the same tree the Raney tree, since they drew some ideas from a 1973 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 (including only the fractions between 0 and 1) appears in Kepler's Harmonices Mundi (1619). Definition and structure The Calkin–Wilf tree may be defined as a directed graph in which each positive rational number occurs as a vertex and has one outgoing edge to another vertex, its parent, except for the root of the tree, the number 1, which has no parent. The parent of any rational number can be determined after placing the number into simplest terms, as a fraction for which greatest common divisor of and is 1. If , the parent of is ; if , the parent of is . Thus, in either case, the parent is a fraction with a smaller sum of numerator and denominator, so repeated reduction of this type must eventually reach the number 1. As a graph with one outgoing edge per vertex and one root reachable by all other vertices, the Calkin–Wilf tree must indeed be a tree. The children of any vertex in the Calkin–Wilf tree may be computed by inverting the formula for the parents of a vertex. Each vertex has one child whose value is less than 1, , because of course . Similarly, each vertex has one child whose value is greater than 1,