The Stern-Brocot tree and Farey sequences¶
Stern-Brocot tree¶
The Stern-Brocot tree is an elegant construction to represent the set of all positive fractions. It was independently discovered by German mathematician Moritz Stern in 1858 and by French watchmaker Achille Brocot in 1861. However, some sources attribute the discovery to ancient Greek mathematician Eratosthenes.
The construction starts at the zeroth iteration with the two fractions
where it should be noted that the second quantity is not strictly a fraction, but it can be interpreted as an irreducible fraction representing infinity.
At every subsequent iteration, consider all adjacent fractions
The first few iterations look like this:
Continuing this process to infinity this covers all positive fractions. Additionally, all fractions will be unique and irreducible. Finally, the fractions will also appear in ascending order.
Before proving these properties, let us actually show a visualization of the Stern-Brocot tree, rather than the list representation. Every fraction in the tree has two children. Each child is the mediant of the closest ancestor on the left and closest ancestor to the right.

Proofs¶
Ordering. Proving ordering is simple. We note that the mediant of two fractions is always in-between the fractions
given that
The two inequalities can be easily shown by rewriting the fractions with common denominators.
As the ordering is ascending in the zeroth iteration, it will be maintained at every subsequent iteration.
Irreducibility. To prove this we will show that for any two adjacent fractions
Recall that a Diophantine equation with two variables
Clearly at the zeroth iteration
Assume our two adjacent fractions uphold
the new expressions become
which, using that
From this we see that the property is always maintained and thus all fractions are irreducible.
The presence of all fractions. This proof is closely related to locating a fraction in the Stern-Brocot tree. From the ordering property we have that left subtree of a fraction contains only fractions smaller than the parent fraction, and the right subtree contains only fractions larger than the parent fraction. This means we can search for a fraction by traversing the tree from the root, going left if the target is smaller than the fraction and going right if the target is larger.
Pick an arbitrary positive target fraction
If that is the case we would at all iterations have
which (using the fact than an integer
Now multiply the first inequality by
Expanding this and using the previously shown property
And given that at every iteration at least one of
Tree Building Algorithm¶
To build any subtree of the Stern-Brocot tree, it suffices to know the left and right ancestor. On the first level, the left and right ancestors are
This pseudocode tries to build the entire infinite tree:
void build(int a = 0, int b = 1, int c = 1, int d = 0, int level = 1) {
int x = a + c, y = b + d;
... output the current fraction x/y at the current level in the tree
build(a, b, x, y, level + 1);
build(x, y, c, d, level + 1);
}
Fraction Search Algorithm¶
The search algorithm was already described in the proof that all fractions appear in the tree, but we will repeat it here. The algorithm is a binary search algorithm. Initially we stand at the root of the tree and we compare our target with the current fraction. If they are the same we are done and stop the process. If our target is smaller we move to the left child, otherwise we move to the right child.
Naive search¶
Here is an implementation that returns the path to a given fraction 'L'
and 'R'
characters, meaning traversal to the left and right child respectively. This sequence of characters uniquely defines all positive fractions and is called the Stern-Brocot number system.
string find(int p, int q) {
int pL = 0, qL = 1;
int pR = 1, qR = 0;
int pM = 1, qM = 1;
string res;
while(pM != p || qM != q) {
if(p * qM < pM * q) {
res += 'L';
tie(pR, qR) = {pM, qM};
} else {
res += 'R';
tie(pL, qL) = {pM, qM};
}
tie(pM, qM) = pair{pL + pR, qL + qR};
}
return res;
}
Irrational numbers in the Stern-Brocot number system corresponds to infinite sequences of characters. Along the endless path towards the irrational number the algorithm will find reduced fractions with gradually increasing denominators that provides increasingly better approximations of the irrational number. So by taking a prefix of the infinite sequence approximations with any desired precision can be achieved. This application is important in watch-making, which explains why the tree was discovered in that domain.
Note that for a fraction
Logarithmic search¶
Fortunately, it is possible to enhance the algorithm above to guarantee
Therefore, instead of doing steps of L
or R
one by one, we can do
As the directions alternate this way, we will always know which one to take. So, for convenience we may represent a path to a fraction
such that
where
This allows to find the run-length encoding of the path to
auto find(int p, int q) {
bool right = true;
vector<pair<int, char>> res;
while(q) {
res.emplace_back(p / q, right ? 'R' : 'L');
tie(p, q) = pair{q, p % q};
right ^= 1;
}
res.back().first--;
return res;
}
However, this approach only works if we already know
On practice, it is often the case that
Knowing this, we can emulate the search on Stern-Brocot tree by maintaining the current boundaries floor
of some known expression).
Farey Sequence¶
The Farey sequence of order
The sequences are named after English geologist John Farey, who in 1816 conjectured that any fraction in a Farey sequence is the mediant of its neighbors. This was proven some time later by Cauchy, but independent of both of them, the mathematician Haros had come to almost the same conclusion in 1802.
The Farey sequences have many interesting properties on their own, but the connection to the Stern-Brocot tree is the most obvious. In fact, the Farey sequences can be obtained by trimming branches from the tree.
From the algorithm for building the Stern-Brocot tree, we get an algorithm for the Farey sequences. Start with the list of fractions
Length of a Farey Sequence¶
A Farey sequence of order
or equivalently, by unraveling the recursion we get