# Stern-Brocot Tree

### Binary Encoding

The set of all trees [x, y] forms a two-dimensional vector space with operations of addition and product by a scalar defined naturally as _{1}, y_{1}] + [x_{2}, y_{2}] = [x_{1} + x_{2}, y_{1} + y_{2}]

[x, y]L = [x, x + y] and [x, y]R = [x + y,y]

These operators have a matrix representation

so that their definition reduces to the product of a vector by a matrix. And there is one more thing. Vector spaces can be added. I am interested here in the direct sum of two copies of SB. Indeed, so far we've been working with sequences of numerators. It's time to apply the theory to sequences of fractions. We shall treat the second copy of SB as a set of trees (or sequences) formed by the denominators. For the convenience sake, I'll write the direct sum of _{1}, y_{1}]_{2}, y_{2}]

which corresponds to the fact that the "denominator" trees are reflections of the "numerator" trees. (A convenient shorthand is [x_{1}/y_{2}, y_{1}/x_{2}].) Operators L and R are extended to the direct sum

and similarly for the operator R

### Remark

Note that determinants of L and R are both 1: det(L) = det(R) = 1, and recollect that for any two square matrices A and B, _{1}/y_{2}, y_{1}/x_{2}]_{}·x_{} - y_{}·y_{}.

After so many definitions we are finally ready for a payoff. In the space SB+SB, the Stern-Brocot tree is represented by

Compute, for example, tLRLL

This is the subtree obtained by first selecting the left subtree, then the right subtree of the latter, and, then, the left subtree twice. The tree is defined by two fractions:

The problem is solved by the following algorithm:

### Algorithm 1

**while** m ≠ n **do**

**if** m < n

**then** (output(L); replace n with n - m)

**else** (output(R); replace m with m - n)

For example, with m = 4 and n = 7 we successively get

m | 4 | 4 | 1 | 1 | 1 | |||||

n | 7 | 3 | 3 | 2 | 1 | |||||

Output | L | R | L | L | ||||||

To see why the algorithm works, introduce a function f defined for every string S of symbols L and R such that f(S) is exactly the fraction m/n encoded by S. More, accurately, if _{1}/n_{1}, m_{2}/n_{2}],_{1} + m_{2})/(n_{1} + n_{2}).

For m > n, the string encoding for m/n starts with R. Moreover,

### Proof

Assume tS = [m_{1}/n_{1}, m_{2}/n_{2}] and note that, t, when treated as a usual matrix, satisfies ^{2} = [1/0, 0/1] = I*identity* matrix. This is equivalent to saying that ^{-1},*multiplicative* inverse. We have _{1}/n_{1}, m_{2}/n_{2}] = [n_{1}/m_{1}, n_{2}/m_{2}]._{1}/(m_{1} + n_{1}), n_{2}/(m_{2} + n_{2})],_{1} + n_{1})/n_{1}, m_{2}/(m_{2} + n_{2})]._{1}+n_{1})/(m_{2} + n_{2})_{1}+n_{1}+m_{2} + n_{2})/(n_{1} + n_{2}) = (m_{1} + m_{2})/(n_{1} + n_{2}) + 1.

The equivalence follows from an already established fact that every fraction appears in the tree only once and, therefore, uniquely identifies its immediate ancestors.

Similarly, if m < n, then the string encoding for m/n starts with L. Moreover,

The Stern-Brocot tree contains only rational numbers. However, irrational numbers are approximated by rationals. For irrational numbers a, Algorithm 1 is modified (replace m/n with a) to

### Algorithm 2

**while (true)** **do**

**if** a < 1

**then** (output(L); replace a with a/(1-a))

**else** (output(R); replace a with

In this manner positive irrational numbers are associated with *infinite* strings of symbols L and R. For example,
^{0}RLR^{2}LRL^{4}RLR^{6}LRL^{8}RLR^{10}...) = e,

Algorithm 2 never stops even when a happens to be rational. In the latter case, assuming f(S) = a, Algorithm 2 generates a second representation for a: SRL^{∞} fully in accordance with what happens in numerical base systems.

## References

- R.Graham, D.Knuth, O.Patashnik,
*Concrete Mathematics*, 2nd edition, Addison-Wesley, 1994.

- Modular Arithmetic
- Chinese Remainder Theorem
- Euclid's Algorithm
- Pick's Theorem
- Fermat's Little Theorem
- Wilson's Theorem
- Euler's Function
- Divisibility Criteria
- Examples
- Equivalence relations
- A real life story

|Contact| |Front page| |Contents| |Generalizations|

Copyright © 1996-2018 Alexander Bogomolny

64996196 |