Fractions on a Binary Tree II
We have already discussed an instance of a binary tree related to the Stern-Brocot tree. A fraction a/b on the tree served a parent to two other fractions: a/(a + b) and b/(a + b). At the time we only considered the case where a < b. With the root equal to 1/2, the tree has been populated by all positive fractions less than 1. Each fraction on the tree appeared in lowest terms. Have we started with the root of 2/1, we would have obtained a tree (of reciprocals) populated by all fractions greater than 1, again all in lowest terms.
By a little change of procedure Calkin and Wilf arrived at a tree with many additional and no less remarkable features. In the modified tree, each fraction a/b has two children, which in order of their appearance on the tree are a/(a + b), as before, and (a + b)/b, which is the reciprocal of the second term in the previous construct. The diagram below depicts the two trees -- the new and the old -- rooted at the same fraction a/b:
| (1) |
|
In terms of functions fL and fR, defined for the fractions on the Stern-Brocot tree, the new algorithm generates two children for any fraction a/b: fL(a/b) and fR(a/b). These are exactly the fractions generated on the Stern-Brocot tree, albeit, in an entirely different order. Thus we may claim that row by row the two trees contain exactly same fractions.
Starting with a/b = 1/1, the new tree appears as
| (2) |
|
As the Stern-Brocot tree, it, too, contains all positive rational numbers and each of them appears exactly once. Calkin and Wilf noticed that in each row any two neighboring fraction have an additional property:
| (3) |
The denominator of the left neighbor coincides with the numerator of the right neighbor.
|
Also, 1 being the numerator of the first fraction in each row as well as the denominator of the last one, (3) holds for the sequence of fractions obtained by writing the tree terms row by row:
| (4) |
1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, 1/4, 4/3, 3/5, 5/2, 2/5, 5/3, 3/4, 4/1, ...
|
To prove (3), first note that the property is obvious for two immediate descendants of the same parent. Two neighbors that are not siblings but share a grandparent also have the same property, see (1). In general, two neighboring fractions that are not siblings, descend from two neighboring fractions in the row above. The situation calls for an inductive argument. Assume, for the sake of induction, that the two parents are a/b and b/c. Their four children then are
| |
a/(a + b), (a + b)/b, b/(b + c), (b + c)/c,
|
and the inductive step follows. A look at the first rows of the tree (2) supplies a base for induction. The proof is complete. (An inductive argument based on fR(b/a) = 1/fL(a/b) shows that each row of the tree has central symmetry.)
Based on (3), the fractions in (4) can be written as q(n)/q(n + 1), n ≥ 0, where q(n) is the sequence of numerators
| (5) |
1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, ...,
|
with q(0) = q(1) = 1, q(2) = 2, q(3) = 1, etc. (The sequence (5) is listed as #A002487 in the On-Line Encyclopedia of Integer Sequences, where it's called Stern's diatomic series. The sequence is remarkable in its own right.)
Function q(n) provides an effective way for enumeration of rational numbers. For n = 0, 1, 2, ..., fraction #n equals q(n)/q(n+1). That simple.
The sequence (5) has been discovered several times over. E. W. Dijkstra described it in a letter to a friend in 1976. Then later same year he learned that function q(n) has been investigated by G. de Rham yet in 1947. Calkin and Wilf proved that q(n) gives a number of hyperbinary representations of the number n. (In other words, q(n) is the number of ways of writing the integer n as a sum of powers of 2, each power being used at most twice (i.e., once more than the legal limit for binary expansions).) Berlekamp et al (1981) identified q(n) with the number of distinct nim-sums of two numbers that add up in the ordinary sense to the number n. Hence, the sequence (5) can be read from an XOR table: q(n) is the number of distinct terms on the nth SW-NE diagonal of the XOR table:
The proof of the latter two assertions is based on the fact that function q(n) satisfies a recurrence relation:
| (6) |
q(2n + 1) = q(n),
q(2n + 2) = q(n) + q(n + 1), n = 0, 1, ...
|
(This is because the children of q(n)/q(n + 1) are q(2n + 1)/q(2n + 2) and q(2n + 2)/q(2n + 3).) As it happens, we have the following
Proposition
The number b(n) of hyperbinary representations of n satisfies the recurrence (6) with the same initial condition, b(0) = 1.
The number x(n) of distinct nim-sums k ^ m, where k + m = n, satisfies the recurrence (6) with the same initial condition, x(0) = 1.
Proof
Now, the binary and hence any hyperbinary expansion of an odd number 2n + 1 ends in 1. It follows by first subtracting 1 and then dividing by 2 that there is a 1-1 correspondence between the hyperbinary expansions of 2n + 1 and n. Thus b(2n + 1) = b(n). Furthermore, b(2n + 2) = b(n) + b(n + 1), because a hyperbinary expansion of 2n + 2 might have either two 1’s or no 1’s in it. If it has two 1’s, then by deleting them and dividing by 2 we'll get an expansion of n. If it has no 1’s, then by just dividing by 2 we get an expansion of n+1.
If k + m = 2n + 1, then the binary expansion of one of k or m ends in 1, the other in 0. By removing this one and dividing by 2, we'll get k1 + m1 = n, for some k1 and m1 such that k1 ^ m1 = k ^ m. If k + m = 2n + 2, then k and m have binary expansions that either both end in 1 or both end in 0. In the first case, asas before, we find k1 + m1 = n and also k1 ^ m1 = k ^ m. In the second case, k1 + m1 = n + 1 and still k1 ^ m1 = k ^ m.
"Playing with figures" on Ascension day 1976 E. W. Dijkstra came across a shifted function (which he called fusc):
| (6') |
fusc(1) = 1,
fusc(2n) = fusc(n),
fusc(2n + 1) = fusc(n) + fusc(n + 1), n = 1, ...
|
so that fusc(k) = q(k - 1), k = 1, 2, 3, ... Compatible with (6'), Dijkstra also defines fusc(0) = 0. He derived an iterative algorithm to compute fusc(n) and, based on it, has established several properties of the function. The algorithm is cute:
| |
k = n
a = 1
b = 0
while (k > 0 ) {
if (k is even) {
k = k/2
a = a + b
} else {
k = (k-1)/2
b = a + b
}
}
fusc(n) = b
|
Function fusc has the following properties:
For n odd, let m be obtained from n by inverting the internal (all, but the first and the last) digits of the binary representation of n (0 to 1, 1 to 0). Then fusc(m) = fusc(n).
Let the binary representation of m be the reverse (written in the reverse order) of the binary representation of n. Then fusc(m) = fusc(n).
fusc(n) is even iff 3|n.
References
- E. R. Berlekamp, J. H. Conway, R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 1, A K Peters, 2001, pp. 115-116.
- E. W. Dijkstra, An exercise for Dr.R.M.Burstall, published in Edsger W. Dijkstra, Selected Writings on Computing: A Personal Perspective,
Springer-Verlag, 1982, pp. 215-216.
- E. W. Dijkstra, More about the function ``fusc'', published in Edsger W. Dijkstra, Selected Writings on Computing: A Personal Perspective,
Springer-Verlag, 1982, pp. 230-232.
- N. Calkin, H. S. Wilf, Recounting the Rationals, Am Math Monthly, Vol. 107 (2000), pp. 360-363.
Stern-Brocot Tree
Copyright © 1996-2009 Alexander Bogomolny
|
