Some notes on the Stern–Brocot tree

Tim Richardt

Summary

After briefly recapturing the Stern–Brocot tree, I show how to count small prime omega ω(n) in it and how Shannon entropy can serve as a measure for convergence of irrationals.

Stern–Brocot tree

Over the past century, continued fractions and the Stern–Brocot tree have gradually become less prominent in curriculae around the world. Although not being completely extinct, they eke out an existence more as objects of recreational math than as active research topics, and it wouldn't be surprising if they still hold treasures.

The Stern–Brocot tree is a binary tree constructed by recursive mediant building. This mediant building can be conveniently encoded using matrices. Each node in the binary tree is represented by a two by two matrix \left(\begin{smallmatrix}a&b\\c&d\end{smallmatrix}\right) where the root of the tree is the unit matrix I:=\left(\begin{smallmatrix}1&0\\0&1\end{smallmatrix}\right) .

From this root the tree is constructed by branching left or right applying L or R .

\begin{align*} L \begin{pmatrix} a & b \\ c & d \end{pmatrix} &\mapsto \begin{pmatrix} a + b & b \\ c + d & d \end{pmatrix}, \\ R \begin{pmatrix} a & b \\ c & d \end{pmatrix} &\mapsto \begin{pmatrix} a & b + a \\ c & d + c \end{pmatrix}. \end{align*}

In words: we branch left by adding the right column to the left one, and we branch right by adding the left column to the right one.

The mapping Q from a matrix to an actual fraction n/d\in\mathbb{Q} is done by dividing the sum of the top row by the sum of the bottom row.

Q \begin{pmatrix} a & b \\ c & d \end{pmatrix} \mapsto \frac{a+b}{c+d} =: \frac{n}{d}

Rational numbers are now paths in this binary tree. Some examples:

\begin{align*} 1 &= [], \\ 2 &= R, \\ \tfrac{1}{3} &= LL, \\ \tfrac{22}{7} &= RRRLLLLLL. \end{align*}

Contrary to positional number systems, values of Stern–Brocot sequences do not distribute evenly, but exponentially along the number line, which can be seen in the following diagram of the first six levels.

Every fraction in the Stern–Brocot tree is an irreducible fraction n/d with n\perp d .

n\perp d means the nominator n and denominator d are coprime — or relatively prime — they do not share any common factor.

Furthermore, fully covering \mathbb{Q} means that the tree contains all irreducible fractions — respectively all coprime pairs.

Back to Top

ω(N) in the Stern–Brocot tree

Having a tree of all coprime pairs to hand can also be used to say something about integers. I could not find anything about this in the literature, so I will go into more detail here.

We replace Q by the map

N \begin{pmatrix} a & b \\ c & d \end{pmatrix} \mapsto \left(a+b\right)\left(c+d\right) =: nd,

so instead of dividing n by d , we build the product nd . Unlike division, multiplication commutes and the tree now has a right-left symmetry. The property of an ordered mapping to the number line is also lost, so the following diagram better illustrates the structure of the tree.

Furthermore, bijectivity to any fundamental number set is lost because certain integers appear multiple times in the tree.

Take the number 60 . It can be written as 60 = 2^2\cdot 3\cdot 5 and is therefore a composite of three distinct primes. From those three distinct ones, eight distinct coprime pairs can be formed, so there are eight different representations of 60

\begin{align*} []&[2^2\;3\;5] &= 1\cdot 60 &= R^{59},\\ [3]&[2^2\;5] &= 3\cdot 20 &= RRRRRRLR,\\ [5]&[2^2\;3] &= 5\cdot 12 &= RRRLRR,\\ [2^2]&[3\;5] &= 4\cdot 15 &= RRLLR,\\ [3\;5]&[2^2] &= 15\cdot 4 &= LLRRL,\\ [2^2\;3]&[5] &= 12\cdot 5 &= LLLRLL,\\ [2^2\;5]&[3] &= 20\cdot 3 &= LLLLLLRL,\\ [2^2\;3\;5]&[] &= 60\cdot 1 &= L^{59}. \end{align*}

When trying out other numbers, the reader will come across the pattern that every natural number N with k distinct prime factors has 2^k decompositions into coprime products.

The distinct number of primes k is called small prime omega — denoted \omega(N) , OEIS A001221 — so it follows that every N occurs 2^{\omega(N)} times in the Stern–Brocot tree.

Or put the other way round

\omega(N) = \log_2(\text{#}N\text{ in the Stern-Brocot tree}).

So we can determine the number of distinct primes of N by counting how many times N appears in the Stern–Brocot tree — no factorization required.

Also, we do not have to go through the whole tree. As soon as we encounter a tree node that is \geq N we can stop the traversal, since all its child nodes will have values >N .

The following Python program does just that. 

from collections import Counter
from math import log2

I = [1, 0, 0, 1] # root of the tree

def L(p): # left child of node p
		a, b, c, d = p
		return [a+b, b, c+d, d]

def R(p): # right child of node p
		a, b, c, d = p
		return [a, b+a, c, d+c]

def N(p): # node p -> integer
		a, b, c, d = p
		return (a+b)*(c+d)

def Ns(n, p): # collect all integers <= n
		if N(p) <= n:
				return [N(p)] + Ns(n, L(p)) + Ns(n, R(p))
		else:
				return []

# count occurrences of each integer in aggregate and log2
omegas = {k: int(log2(v)) for k, v in sorted(Counter(Ns(42, I)).items())}

print(omegas)

=> {1: 0, 2: 1, 3: 1, 4: 1, 5: 1, 6: 2, 7: 1, 8: 1, 9: 1, 10: 2, 11: 1,
    12: 2, 13: 1, 14: 2, 15: 2, 16: 1 ...

I hope to be able to be more precise about the time and space complexity in the future, but for now, just to get an idea of how many nodes we can truncate, the following graph shows the number of nodes traversed to determine \omega(N) .

The purple curve is simply the dual logarithm of N . It can be seen that while initially above, asymptotically the number of nodes traversed divided by N falls below \log_2 N .

Now I'd like to return to the original Stern-Brocot tree. I want to apply the concept of Shannon entropy to fractions.

Back to Top

Entropy and Irrationality

Let's ignore the fractions n/d and focus on the binary sequences of L 's and R 's themselves.

We'll pick a random number from the Stern–Brocot tree and retrieve its information one L or R at a time. Assuming we have no prior knowledge, getting an L or an R should be equally likely. This means that at each branch we get exactly one bit of information.

It follows that each natural number N=R^{N-1} carries N-1 bits of information. The same is true for unit — or Egyptian — fractions 1/N = L^{N-1} . In this picture the popular approximation of \pi\approx\tfrac{22}{7} = R^3L^6 carries nine bits of information.

As usual in information theory, we can also define the entropy of a binary sequence as

\begin{align*} S = - \sum_{i\in\{L,\,R\}} p_i \log p_i = -p_L \log p_L - p_R\log p_R. \end{align*}

For every natural number we get p_R=1 and p_L=0 , because they live on the rightmost branch. For them the entropy is

\begin{align*} S &= - p_L \log p_L - p_R \log p_R = - \log 0 - 1\log 1 = 0 \end{align*}

For a similar reason, the entropy of all the Egyptian fractions is zero because p_L=1 and p_R=0 holds all of them.

The fraction \tfrac{22}{7} = R^3L^6 has p_L = \tfrac{6}{9} = \tfrac{2}{3} and p_R = \tfrac{3}{9} = \tfrac{1}{3} , so the entropy is

\begin{align*} S\left(\tfrac{22}{7}\right) = - \tfrac{1}{3}\log \tfrac{1}{3} - \tfrac{2}{3}\log \tfrac{2}{3} \approx 0.91829\dots. \end{align*}

The entropy is at its maximum for numbers that branch as often to the right as to the left. For them p_L = \tfrac{1}{2} = p_R and so

\begin{align*} S = - \tfrac{1}{2}\log \tfrac{1}{2} - \tfrac{1}{2}\log \tfrac{1}{2} = 1. \end{align*}

While I cannot give a concise interpretation of the entropy of rational numbers, there is something that jumps out at you when you look at irrational numbers.

Irrational numbers carry infinite information because they are never ending sequences in the Stern–Brocot tree.

It is also remarkable, that all square roots have periodic patterns. And conversley, every periodic sequence is a square root. Also, e has an interesting pattern.

\begin{align*} \phi &= RLRLRLRLRL\dots, \\ \sqrt{2} &= RLLRRLLRRLL\dots, \\ \sqrt{3} &= RLRRLRRLRR\dots, \\ e &= RL^0RLR^2LRL^4RLR^6L\dots. \end{align*}

Since we cannot store an infinite amount of information, we can only work with approximations of irrational numbers. It follows that we can only talk about entropy of the first b bits of an irrational number.

The following three graphs show how the entropy of several irrational numbers evolves with increasing information. The plots show the same data at three different zoom levels: 40bit, 20kbit, and 180kbit.

We see that \phi and \sqrt{2} lead the field. They maximise the entropy because they balance out L 's and R 's in the most granular way. \phi is a repeating RL while \sqrt{2} is a repeating change between RL and LR .

\phi is known to be the most irrational number. and has, together with \sqrt{2} and their inverses, the highest entropy — asymptotically the entropy goes to one. We also see that \sqrt{3} 's entropy converges to a value below one because its period has an uneven number of L 's and R 's.

I suspect that entropy could be a good measure for the convergence of irrational numbers and I hope to gain more insight in the very near future.

Back to Top

References

Back to Top

Footnotes