Stern-Brocot Tree

As we have seen, Algorithm 1 finds L-R encoding for any (positive) rational number m/n. However, intermediate fractions generated by the algorithm are not quite those one would expect from the manner in which the encoding has been defined. With m/n = 4/7, the algorithm generates successively, 4/7, 4/3, 1/3, 1/2, 1/1.

In terms of single numbers, the sequence is 1/1, 1/2, 2/3, 3/5, 4/7, and we as well may wonder why does the whole thing really work. Of course a proof is a proof and, since we have one, we know that the algorithm works. In what follows, I establish a geometric interpretation for the algorithm which puts the L-R encoding and the algorithm back into the scope of our intuition.

Two identities f(RS) = f(S) + 1 and 1/f(LS) = 1/f(S) + 1 form a basis for our derivation. Given a fraction m/n and its (unique) encoding S, we obtain another fraction f(RS) through the first formula. f(RS) is uniquely determined by m/n which enables us to define a function f_R as f_R(m/n) = m/n+1 = (m+n)/n. It all may appear as a vacuous manipulation of mathematical symbols; for, obviously, m/n+1 is a function of m/n. The point was of course not in affirming a trivial mathematical fact but in pointing out that this trivial mathematical fact underlies the algorithm at hand. From the second formula we derive another function f_L as f_L(m/n) = m/(n+m). An easily proven formula f_R(1 - f_L) = 1 may also be observed on the tree.

In the diagram below, red lines trace the action of f_R, the blue lines that of f_L. Starting with row #1, there are three lines emanating from every fraction on the tree: two (one red, one blue) point to the next row, one line points to the row above. Because of the latter property, for every fraction m/n, there is a unique way upwards that connects it to the fraction 1/1. For example, for m/n = 4/7 we get successively, 4/7, 4/3, 1/3, 1/2, 1/1 which, of course, is the sequence that has been generated by the algorithm.

This also shows that 4/7 = f_Lf_Rf_Lf_L(1/1).

One more observation will prove helpful. For a given row, all red lines from its terms downwards end on the right half of the row below. Likewise, all the blue lines connect fractions in one row to the left-hand side fractions of the next row. We have already observed how the two halves of a row (of numerators) are formed from the previous row. Bearing in mind that in the Stern-Brocot tree, sequences of denominators are obtained by reversing the order of the sequences of numerators, we see that, extended to the tree of fractions our old observation confirms the new one: to obtain the right half of a row, apply function f_R to the fractions of the previous row. To obtain the left half, apply function f_L.

Let's compare 4/7 = f_Lf_Rf_Lf_L(1/1) with f(LRLL) = 4/7 which is obtained from tLRLL = [1/2,3/5]. In the latter, we first multiply by the leftmost L, then by R, then twice by L. 4/7 = f_Lf_Rf_Lf_L(1/1) suggests that carrying operations in the reverse order is more relevant to the algorithm. The important thing to note is, whereas, in tLRLL, factors L and R applied on the right, in f_Lf_Rf_Lf_L(1/1) f_L and f_R appear on the left. What's the mystery?

Extend definition of f_R and f_L columnwise to the tree (or the matrix) case: f_R[x1/y2,y1/x2] = [f_R(x1/y2), f_R(y1/x2)]. Similarly, f_L[x1/y2,y1/x2] = [f_L(x1/y2), f_L(y1/x2)]. Thus, for example, f_L[0/1,1/0] = [0/1,1/1]. Furthermore, f_Lf_Rf_Lf_L[0/1,1/0] = f_Lf_Rf_L[0/1,1/1] = f_Lf_R[0/1,1/2] = f_L[1/1,3/2] = [1/2,3/5] which, as we know, reduces to the expected 4/7. Written a little differently, tLRLL = f_Lf_Rf_Lf_Lt which clearly relates two ways of deriving L-R encoding. With a small additional effort we can simplify this expression. Recollect, that t² = I, the identity matrix. Then tLRLL = tLttRttLttLtt = (tLt)(tRt)(tLt)(tLt)t. May it be that tLt = f_L and tRt = f_R? This is indeed the case. From the definition, f_R[x1/y2,y1/x2] = [f_R(x1/y2), f_R(y1/x2)], the matrix representation of f_R is [1/0,1/1] while the representation of f_L is [1/1,0/1]. In other words, f_R = L while f_L = R. By simple inspection we also verify that tLt = R and tRt = L. Thus all parts fit nicely together: tLRLL = RLRRt.

How do we get 4/3? First, 4/3 is located in the third row. Therefore we shall need 3 binary digits to represent this fraction. Second, it's the fourth fraction in the row. (The first is the 0th!) Thus its binary encoding is 100 which converts to LRR for the "left-side" encoding or into its complementary RLL "right-side" encoding.

Problem: Find the fraction in the 10-th position of the 4-th row of the Stern-Brocot tree. (Remember to start counting from 0.)

Solution: Using for binary digits, 10th position is represented by 1010 which converts to LRLR for the "left-hand" encoding and to RLRL for the "right=hand" encoding. LRLR[0/1,1/0] = LRL[0/1,1/1] = LR[1/1,2/1] = L[1/2,2/3] = [3/2,5/3]. Which boils down to 8/5.

Problem: Find location on the tree of a fraction whose "right-side" encoding is LRLLRLRR.

Solution: Its "left-side" encoding is RLRRLRLL which converts to 01001011₂ = 75₁₀. Therefore, the corresponding fraction is located in the row #8, position 75 where the count starts from 0.

• Modular Arithmetic
  • Differences and Similarities
  • Solutions to some problems
• Chinese Remainder Theorem
• Euclid's Algorithm
  • Euclid's Game
  • Binary Euclid's Algorithm
  • gcd and the Fundamental Theorem of Arithmetic
  • Extension of Euclid's Algorithm
  • Stern-Brocot Tree
    • Fine features
    • Binary Encoding
    • Binary Encoding, a Second Interpretation
    • Continued Fractions on the Stern-Brocot Tree
    • Fractions on a Binary Tree
    • Fractions on a Binary Tree II
  • Farey series
    • Farey series, a story
• Pick's Theorem
  • Pick's Theorem, A Proof
  • Farey Series
  • Pick's Theorem Applies to the Farey Series
  • Stern-Brocot Tree
• Fermat's Little Theorem
• Wilson's Theorem
• Euler's Function
• Divisibility Criteria
• Examples
• Equivalence relations
• A real life story

Copyright © 1996-2008 Alexander Bogomolny