Calkin–Wilf tree

The Calkin–Wilf tree

How values are derived from their parent

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 $q$ expressed in simplest terms as the fraction $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠a/b⁠$ has as its two children the numbers $⁠ 1 / 1+1/ q ⁠ = ⁠ a / a + b ⁠$ and $q + 1 = ⁠ a + b / b ⁠$ . 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^[1] called the same tree the Raney tree, since they drew some ideas from a 1973 paper by George N. Raney.^[2] 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).^[3]

Definition and structure

The Calkin–Wilf tree may be defined as a directed graph in which each positive rational number $⁠ a / b ⁠$ 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 $q \neq 1$ can be determined after placing the number into simplest terms, as a fraction $⁠ a / b ⁠$ with $a \neq b$ relatively prime. If $q = ⁠ a / b ⁠ < 1$ , its parent is $⁠ 1 / 1/ q - 1 ⁠ = ⁠ a / b - a ⁠$ ; if $q = ⁠ a / b ⁠ > 1$ , its parent is $q - 1 = ⁠ a - b / b ⁠$ . 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 $⁠ a / b ⁠$ has one child whose value is less than 1, $⁠ a / a + b ⁠$ , because of course $a + b > a$ . Similarly, each vertex $⁠ a / b ⁠$ has one child whose value is greater than 1, $⁠ a + b / b ⁠$ .^[4]

As each vertex has two children, the Calkin–Wilf tree is a binary tree. However, it is not a binary search tree: its inorder does not coincide with the sorted order of its vertices. However, it is closely related to a different binary search tree on the same set of vertices, the Stern–Brocot tree: the vertices at each level of the two trees coincide, and are related to each other by a bit-reversal permutation.^[5]

Breadth first traversal

The Calkin–Wilf sequence is the sequence of rational numbers generated by a breadth-first traversal of the Calkin–Wilf tree,

⁠11⁠, ⁠12⁠, ⁠21⁠, ⁠13⁠, ⁠32⁠, ⁠23⁠, ⁠31⁠, ⁠14⁠, ⁠43⁠, ⁠35⁠, ⁠52⁠, ⁠25⁠, ⁠53⁠, ⁠34⁠, ….

Because the Calkin–Wilf tree contains every positive rational number exactly once, so does this sequence.^[6] The denominator of each fraction equals the numerator of the next fraction in the sequence. The Calkin–Wilf sequence can also be generated directly by the formula

q_{i+1}={\frac {1}{2\lfloor q_{i}\rfloor -q_{i}+1}}

where $q i$ denotes the $i$ th number in the sequence, starting from $q 1 = 1$ , and $⌊ q i ⌋$ represents the integral part.^[7]

It's also possible to calculate $q i$ directly from the run-length encoding of the binary representation of $i$ : the number of consecutive 1s starting from the least significant bit, then the number of consecutive 0s starting from the first block of 1s, and so on. The sequence of numbers generated in this way gives the continued fraction representation of $q i$ . Example:

i = 1081 = 10000111001₂: The continued fraction is [1;2,3,4,1] hence

q 1081 = ⁠ 53 / 37 ⁠

.

i = 1990 = 11111000110₂: The continued fraction is [0;1,2,3,5] hence

q 1990 = ⁠ 37 / 53 ⁠

.

In the other direction, using the continued fraction of any $q i$ as the run-length encoding of a binary number gives back $i$ itself. Example:

q i = ⁠ 3 / 4 ⁠

: The continued fraction is [0;1,3] hence

i

= 1110₂ = 14.

q i = ⁠ 4 / 3 ⁠

: The continued fraction is [1;3]. But to use this method, the length of the continued fraction must be an odd number. So [1;3] should be replaced by the equivalent continued fraction [1;2,1]. Hence

i

= 1001₂ = 9.

A similar conversion between run-length-encoded binary numbers and continued fractions can also be used to evaluate Minkowski's question mark function; however, in the Calkin–Wilf tree the binary numbers are integers (positions in the breadth-first traversal) while in the question mark function they are real numbers between 0 and 1.

Stern's diatomic sequence

Stern's diatomic sequence is the integer sequence

0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, … (sequence A002487 in the OEIS).

Using zero-based numbering, the $n$ th value in the sequence is the value $fusc(n)$ of the fusc function, named^[8] according to the obfuscating appearance of the sequence of values and defined by the recurrence relations

{\begin{aligned}\operatorname {fusc} (2n)&=\operatorname {fusc} (n)\\\operatorname {fusc} (2n+1)&=\operatorname {fusc} (n)+\operatorname {fusc} (n+1),\end{aligned}}

with the base cases $fusc(0) = 0$ and $fusc(1) = 1$ .

The $n$ th rational number in a breadth-first traversal of the Calkin–Wilf tree is the number $⁠ fusc(n) / fusc(n + 1) ⁠$ .^[9] Thus, the diatomic sequence forms both the sequence of numerators and the sequence of denominators of the numbers in the Calkin–Wilf sequence.

The function $fusc(n + 1)$ is the number of odd binomial coefficients of the form $(n - r r)$ , $0 \leq 2 r < n$ ,^[10] and also counts the number of ways of writing $n$ as a sum of powers of two in which each power occurs at most twice. This can be seen from the recurrence defining fusc: the expressions as a sum of powers of two for an even number $2 n$ either have no 1s in them (in which case they are formed by doubling each term in an expression for $n$ ) or two 1s (in which case the rest of the expression is formed by doubling each term in an expression for $n - 1$ ), so the number of representations is the sum of the number of representations for $n$ and for $n - 1$ , matching the recurrence. Similarly, each representation for an odd number $2 n + 1$ is formed by doubling a representation for $n$ and adding 1, again matching the recurrence.^[11] For instance,

6 = 4 + 2 = 4 + 1 + 1 = 2 + 2 + 1 + 1

has three representations as a sum of powers of two with at most two copies of each power, so $fusc(6 + 1) = 3$ .

Relation to Stern–Brocot tree

The Calkin–Wilf tree resembles the Stern–Brocot tree in that both are binary trees with each positive rational number appearing exactly once. Additionally, the top levels of the two trees appear very similar, and in both trees, the same numbers appear at the same levels. One tree can be obtained from the other by performing a bit-reversal permutation on the numbers at each level of the trees.^[5] Alternatively, the number at a given node of the Calkin–Wilf tree can be converted into the number at the same position in the Stern–Brocot tree, and vice versa, by a process involving the reversal of the continued fraction representations of these numbers.^[12] However, in other ways, they have different properties: for instance, the Stern–Brocot tree is a binary search tree: the left-to-right traversal order of the tree is the same as the numerical order of the numbers in it. This property is not true of the Calkin–Wilf tree.

Notes

^ Berstel & de Luca (1997), Section 6.
^ Raney (1973).
^ Kepler, J. (1619), Harmonices Mundi, vol. III, p. 27.
^ The description here is dual to the original definition by Calkin and Wilf, which begins by defining the child relationship and derives the parent relationship as part of a proof that every rational appears once in the tree. As defined here, every rational appears once by definition, and instead the fact that the resulting structure is a tree requires a proof.
^ ^a ^b Gibbons, Lester & Bird (2006).
^ Calkin & Wilf (2000): "a list of all positive rational numbers, each appearing once and only once, can be made by writing down ⁠1/1⁠, then the fractions on the level just below the top of the tree, reading from left to right, then the fractions on the next level down, reading from left to right, etc." Gibbons, Lester & Bird (2006) discuss efficient functional programming techniques for performing this breadth first traversal.
^ Knuth et al. (2003) credit this formula to Moshe Newman.
^ The fusc name was given in 1976 by Edsger W. Dijkstra; see EWD570 and EWD578.
^ Calkin & Wilf (2000), Theorem 1.
^ Carlitz (1964).
^ The OEIS entry credits this fact to Carlitz (1964) and to uncited work of Lind. However, Carlitz's paper describes a more restricted class of sums of powers of two, counted by $fusc(n)$ instead of by $fusc(n + 1)$ .
^ Bates, Bunder & Tognetti (2010).

References

Aigner, Martin; Ziegler, Günter M. (2004), Proofs from THE BOOK (3rd ed.), Berlin; New York: Springer, pp. 94–97, ISBN 978-3-540-40460-6
Bates, Bruce; Bunder, Martin; Tognetti, Keith (2010), "Linking the Calkin-Wilf and Stern-Brocot trees", European Journal of Combinatorics, 31 (7): 1637–1661, doi:10.1016/j.ejc.2010.04.002, MR 2673006
Berstel, Jean; de Luca, Aldo (1997), "Sturmian words, Lyndon words and trees", Theoretical Computer Science, 178 (1–2): 171–203, doi:10.1016/S0304-3975(96)00101-6
Calkin, Neil; Wilf, Herbert (2000), "Recounting the rationals" (PDF), American Mathematical Monthly, 107 (4), Mathematical Association of America: 360–363, doi:10.2307/2589182, JSTOR 2589182.
Carlitz, L. (1964), "A problem in partitions related to the Stirling numbers", Bulletin of the American Mathematical Society, 70 (2): 275–278, doi:10.1090/S0002-9904-1964-11118-6, MR 0157907.
Dijkstra, Edsger W. (1982), Selected Writings on Computing: A Personal Perspective, Springer-Verlag, ISBN 0-387-90652-5. EWD 570: An exercise for Dr.R.M.Burstall, pp. 215–216, and EWD 578: More about the function "fusc" (A sequel to EWD570), pp. 230–232, reprints of notes originally written in 1976.
Knuth, Donald E.; Rupert, C.P.; Smith, Alex; Stong, Richard (2003), "Recounting the Rationals, Continued: 10906", The American Mathematical Monthly, 110 (7): 642–643, doi:10.2307/3647762, JSTOR 3647762
Gibbons, Jeremy; Lester, David; Bird, Richard (2006), "Functional pearl: Enumerating the rationals", Journal of Functional Programming, 16 (3): 281–291, doi:10.1017/S0956796806005880, S2CID 14237968.
Raney, George N. (1973), "On continued fractions and finite automata", Mathematische Annalen, 206 (4): 265–283, doi:10.1007/BF01355980, hdl:10338.dmlcz/128216, S2CID 120933574
Stern, Moritz A. (1858), "Ueber eine zahlentheoretische Funktion", Journal für die reine und angewandte Mathematik, 55: 193–220.

External links

[1] Berstel & de Luca (1997), Section 6.

[2] Raney (1973).

[3] Kepler, J. (1619), Harmonices Mundi, vol. III, p. 27.

[4] The description here is dual to the original definition by Calkin and Wilf, which begins by defining the child relationship and derives the parent relationship as part of a proof that every rational appears once in the tree. As defined here, every rational appears once by definition, and instead the fact that the resulting structure is a tree requires a proof.

[FOOTNOTEGibbonsLesterBird2006-5] Gibbons, Lester & Bird (2006).

[6] Calkin & Wilf (2000): "a list of all positive rational numbers, each appearing once and only once, can be made by writing down ⁠1/1⁠, then the fractions on the level just below the top of the tree, reading from left to right, then the fractions on the next level down, reading from left to right, etc." Gibbons, Lester & Bird (2006) discuss efficient functional programming techniques for performing this breadth first traversal.

[7] Knuth et al. (2003) credit this formula to Moshe Newman.

[8] The fusc name was given in 1976 by Edsger W. Dijkstra; see EWD570 and EWD578.

[9] Calkin & Wilf (2000), Theorem 1.

[10] Carlitz (1964).

[11] The OEIS entry credits this fact to Carlitz (1964) and to uncited work of Lind. However, Carlitz's paper describes a more restricted class of sums of powers of two, counted by $fusc(n)$ instead of by $fusc(n + 1)$ .

[FOOTNOTEBatesBunderTognetti2010-12] Bates, Bunder & Tognetti (2010).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]