Fractions in the Farey Series and the Stern-Brocot Tree
Here are two classic ways of arranging fractions, the Farey series and the Stern-Brocot Tree of fractions.
Both list fractions in order of increasing size and have some nice number patterns in their denominators and
numerators. The Stern-Brocot tree turns out to have a simple relationship to the way a fraction can
be written as a Continued Fraction.
This page is one of a series on Fractions. For the full list see the Home
page.
Contents of this page
The icon means there is a
Things to do section of questions to start your own investigations.
The calculator icon
indicates that there is a live interactive calculator in that section.
Farey Series
If we list all the "small" fractions, that is, those using no number higher than 5, say, and if we list
them in order of size from 0 to 1, then the resulting series is called a Farey series:
0
1
1
1
2
1
3
2
3
4
1
5
4
3
5
2
5
3
4
5
Such series of small fractions have many interesting properties.
There is a Farey series for each size of maximum denominator
so we call the maximum denominator of a series the order of that series and
talk about "the Farey series of order 5" for instance.
It makes the maths tidier if we start at 0 and end with 1 and write these as 0/1 and 1/1:
The lengths of these series (counts) are 2, 3, 5, 7, 11, 13, 19, 23, 29, 33, ..
A005728
and, apart from the first, are always odd. Up until 29 it looked as if they might all be primes, but 33
puts an end to that theory.
The Complementary Fraction
If a/b is in a Farey series or any order
then so is 1 – a/b = (b–a)/b,
called its complement.
Even 0/0 has a complement: 1/1.
There is one fraction not paired in this way because it is equal to its complement:
1/2.
So there are always an odd number of fractions in any Farey series beyond those of order 1,
as each is paired with its complement except for 1/2.
The Denominators
In the table of Farey series, the denominators have a pattern. To generate the denominators of the next row (order 7)
we insert a 7 wherever two neighbouring denominators of level 6 sum to 7:
We can then number the new fractions with numerators in order from 1 to 6 since there are 6 of them.
However, in general there are not n-1 fractions with a denominator of n
since some of them will not be in lowest form.
Here are the first 8 levels with the new denominators shown in red.
Are there any patterns in the numerators?
We noticed above that both a/b and its complement (b–a)/b
are in the same Farey series. The Farey series are always in increasing size so the sum of the
second fraction from
the end is the complement of the second fraction (from the beginning),
and so on for the third, fourth, etc, till we get to the central fraction 1/2.
Such pairs have the same denominator and
their numerators will sum or n, the order of the Farey series.
A Farey Fractions Calculator
Farey Fractions C A L C U L A T O R
Neighbouring Fractions in Farey Series
An important property of two neighbouring fractions in any Farey series is that
"cross-multiplying" gives two consecutive integers. In other words, if
a/b and p/q
are consecutive terms in any Farey series,
then b×p is the next integer after
a×q. For instance, the Farey seris of order 6 has
..., 1/3, 2/5, ... and
5×1 = 5 , 3×2 = 6.
This works for all pairs of terms in all Farey series
if we write the first fraction, 0, as 0/1.
... ,
a
,
p
, ... ⇒ b p – a q = 1
b
q
Ford Circles and Farey Fractions
A nice visual representation of Farey fractions is Ford Circles. The fraction p/q is represented by a circle
that touches the x axis at x=p/q. If the radius of the circle is 1/(2q2) then
consecutive Farey fractions on level L are tangential to those on level L-1 as well as the x-axis. If the circles at 0
is represented by 0/1 then the two initial circles for 0 and 1 have radius 1/2 and touch each other also
and all the circles fit neatly into the diagram below.
Fractions L R Ford, Amer Math Monthly vol 45 (1938) pages 586-601
The Stern-Brocot Tree of Fractions
The Ford Circles and therefore the Farey fractions have a close relationship to another tree of fractions, the Stern-Brocot Tree.
The Mediant
Another way to represent all small fractions is to use the fact that between
fractions a/b and p/q lies the
fraction (a+p)/(b+q) formed by
summing their numerators and their denominators:
a
b
<
a + p
b + q
<
p
q
The central fraction here is called the mediant of the other two.
between 1/2 and 1/3 lies their mediant: 2/5
the mediant of 1/6 and 1/4 is 2/10
which reduces to 1/5
the mediant of 0/1 and 1/4 is 1/5
the mediant of 4/5 and 1/1 is 5/6
For any three successive fractions in any Farey series, the middle one is the mediant of the other two
but not always in its lowest form as we saw with the mediant of
1/6 and 1/4
above.
John Farey observed this in a letter of 1816 to the Philosophical Magazine and asked if it was always true.
It was soon proved so by Cauchy who
gave gave them the name "Farey series". However C Haros had already proved this
in 1802 and it seems his work was unknown to both Farey and Cauchy but it is Farey's name that is
now always given to these series.
(See the References below for more on this in both Hardy and Wright's book and the
wonderfully inspiring book by Beiler.)
Another arrangement of Fractions
There is another way to arrange all fractions. It uses the mediant operation but this time it
always gives the mediant fractions in their lowest terms.
We again start with a row of just two fractions:
0/1 and 1/1.
The rows of Farey fractions table
has all fractions with a denominator n or less. However, in this new table
this is not true, but we do still include all fractions once and once only.
It uses the mediant of two fractions to fill in each row as follows:
We again start with 0/1 and 1/1 as the first row.
Each subsequent row includes all the fractions from the previous level, as does the Farey series table
Every gap between two fractions on the
previous level is filled with their mediant fraction on the next level compared ti the Farey table where
row n only had in it the extra fractions with a denominator of n.
level
series
count
1
0/1
1/1
2
2
0/1
1/2
1/1
3
3
0/1
1/3
1/2
2/3
1/1
5
4
0/1
1/4
1/3
2/5
1/2
3/5
2/3
3/4
1/1
9
...
So every fraction apart from 0/1 and 1/0 is the mediant of
two consecutive 'parent' fractions from the level above.
Each fraction produces two 'children'
formed from the mediants of itself and the fraction on its left and with the fraction on its right.
This family 'tree' of fractions has some interesting properties:
eventually all fractions appear in the tree
fractions with the same denominator first appear on different levels in the tree, unlike the Farey fraction rows where
all fractions with denominator n appeared on the same row:
level 4:
0
1
1
2
1
3
2
3
1
1
4
3
5
2
5
3
4
1
level 5:
0
1
1
2
1
3
2
3
1
4
3
5
2
5
3
4
1
1
5
4
7
3
8
5
7
2
7
5
8
3
7
4
5
1
but the Farey series of order 5 is
order 5:
0
1
1
1
2
1
3
2
3
4
1
1
5
4
3
5
2
5
3
4
5
1
each time we take the mediant of two fractions to introduce a new one into this tree, it will always
be in its lowest terms
This is not always so in the Farey series where, for instance, we find the first appearance of
1
5
is
between
1
6
and
1
4
but the mediant of
these two is
1+1
=
2
6+4
10
which must be reduced to get
1
5
.
In each Farey series,
the mediant rule will still hold for any three consecutive fractions on the same level but
may need to be reduced to its lowest terms:
level 4:0/11/5 ....2/71/33/8... 4/5 1
but (2+7)/(7+8) = 9/15 which then reduces to 1/3
Each level has new fractions equal to the number of gaps in the previous level. Thus if
there are n fractions on one level, there are n–1 gaps and
the next level has n + (n – 1) = 2n – 1 fractions
so each row is almost twice as long as the previous row.
In the tree there are 2 fractions on level 0, 3 on level 1 and so on: 2,3,5,9,17,33,... so
there are 2L+1 + 1
fractions on level L
The 'cross-multiply' relationship that we saw for neighbouring fractions in any Farey series will also
apply to any consecutive pair of fractions in this tree too:
level 5:
... 2/7
1/3 ...
and cross-multiplying gives 2×3 = 6 7×1 = 7
level 5:
....
1/33/8...
and cross-multiplying gives 1×8 = 8 3×3 = 9
Stern and Brocot realised that the table we have above can be extended, using the same fill-in-with-the-mediant rule,
to include all fractions, those bigger than one also and not just those between 0 and 1.
Instead of starting with 0/1 and 1/1 we start with
0/1 and 1/0 to represent 0 and infinity.
To start the tree, the first mediant is that of 0/1 and 1/0 which is 1/1.
Now the left half of this new table contains all the fractions between 0 and 1 (0/1 and 1/1) while the
right-hand half becomes populated with all the fractions greater than 1, between 1 and infinity (1/1 and 1/0)!
row
fractions
< 1
= 1
>1
0
0/1
1/0
1
0/1
1/1
1/0
2
0/1
1/2
1/1
2/1
1/0
3
0/1
1/3
1/2
2/3
1/1
3/2
2/1
3/1
1/0
4
0/1
1/4
1/3
2/5
1/2
3/5
2/3
3/4
1/1
4/3
3/2
5/3
2/1
5/2
3/1
4/1
1/0
5
...
Did you notice that the right-hand half of the table has the same fractions as in the left-hand half,
but each is inverted and they are in reverse order?
Since the left-hand half contains all fractions m/n < 1, then the right hand half will contain
all fractions n/m > 1, with 1/1 itself central to every row.
The Stern-Brocot Tree
If we ignore the two end fractions 0/1 and 1/0 then the first
time a fraction appears, we can draw a line from it to its nearest fraction on the row above. The only fraction
that we cannot do this for is 1/1 and this becomes the 'root' of our tree, which, like many
trees in computing and mathematics, grows down the page.
Every fraction first appears as the mediant (a+p)/(b+q)
of the two fractions a/b and p/q
on the level above in the table. The line from (a+p)/(b+q)
will therefore go to either a/b or p/q.
Stern-Brocot Tree of ALL fractions
0/1
1/1
1/0
1/2
2/1
1/3
2/3
3/2
3/1
1/4
2/5
3/5
3/4
4/3
5/3
5/2
4/1
Did you notice that:
the fractions on each row are in order of size
Stern-Brocot Tree and Ford Circles
If we look again at the diagram above of Ford circles, we see that the Stern-Brocot tree shows which circles
touch other circles and which are the largest circles in any gap.
For instance, the 1/3 circle touches 1/4 on its left and 2/5 on its right and the circle at 0
touches 1/2, 1/3, 1/4, 1/5, ... that is all the fractions on the left hand side of the tree.
A Path in the Tree to every fraction
We can now find a unique path from 1/1 to any and every fraction - except 1/1 which is
the starting point.
From a parent we can go down to the Left fraction (child) on the next level below
or to the R fraction on the level below. Since all the fractions are joined into a single tree
with root 1/1, then every fraction has such a string of Ls and Rs from the top to reach it.
In this table, each fraction appears once, on its highest (first) level and below it are its two children.
Paths in the Stern-Brocot Tree
Row 0
0/1
1/0
Row 1
1/1
Row 2
L 1/2
R 2/1
Row 3
L 1/3
R 2/3
L 3/2
R 3/1
Row 4
L 1/4
R 2/5
L 3/5
R 3/4
L 4/3
R 5/3
L 5/2
R 4/1
Row 5
L 1/5
R 2/7
L 3/8
R 3/7
L 4/7
R 5/8
L 5/7
R 4/5
L 5/4
R 7/5
L 8/5
R 7/4
L 7/3
R 8/3
L 7/2
R 5/1
For example, from 1/1:
L gets us to 1/2 and R to 2/1
whereas LL reaches 1/3, LR leads to 2/3,
RL to 3/2 and RR 3/1
4/3 is at the end of the path RLL
The path to 1/1 is the empty path, or perhaps we can write it just as 1
The LR path to a fraction
gives a route from the 1/1 Ford circle to that fraction's circle by going to
the topmost touching circle on the Left or Right.
The Ford circle diagram above shows 1/2 which is L from 1/1.
Then to get to 2/5 we go first to 1/3 on the L then 2/5 on
the R so the whole path is
LLR.
You can see that LLR is also the path in the table above from Row 1 to 2/5 on Row 4.
An algorithm to find the path to m/n
The above examples give us an easy method to compute the LR path from 1/1 to any fraction m/n:
Algorithm to find the SB tree path to fraction m/n
Variables:
Input: the fraction being sought
Two fractions define the range within which we are looking for our fraction:
Call these two fractions start = 0/1 initially
and end which is 1/0 initially.
We will build up the path letter by letter as the path which is initially empty.
Output will be the path to this fraction m/n
Find the mediant of start and end
If mediant = m/n then print out the path found so far and STOP otherwise ifmediant > m/n then
add an L on to the end of the path
change end to be equal to mediant
otherwisemediant < m/n so
add an R on to the end of the path
change start to be equal to mediant
Keep repeating the previous step until the method stops at the fraction m/n.
The only problem is 1/1 itself which, being at the 'root' of the tree, has no path or, rather,
its path is empty.
A similar simple algorithm will compute m/n from a given LR path.
Here is a Calculator to do both.
The Stern-Brocot Fractions Tree
Long Paths and a shorter notation
Note that the fraction 1/N occurs for the first time at the start of row N
in the tree and every level gives rise to an L or an R in the path.
Some paths can therefore be very long: for example the path
to 1/1000000 is one million L's!
As a result, we use a superscript notation to abbreviate the paths.
A string of 12 L's, for instance is represented by L12
and 4/21 which has path LLLLLRRR is shown as L5R3.
In the Calculator input you can write
and spaces are optional.
We use just L and R instead of L1 and R1.
The Calculator can also draw the half-tree of fractions <1 down to a given level where
level n begins with 1/n
and ends (n-1)/n.
The Stern-Brocot Fractions Tree C A L C U L A T O R
There are now several interesting questions that you can work on for yourself:
Things to do
If we know the path for fraction m/n and we change all L's to R's and R's to L's in it,
how is the new path's fraction related to m/n?
(Easy) Where are the fractions of the form 1/n in the tree?
Make a table of the only the numerators of the Farey fractions (the left half of the Stern-Brocot tree )
for a particular level.
What pattern do you notice? Does it apply to all levels?
Now try the same thing but for the denominators.
Make a list of the ratio of two consecutive
Fibonacci numbers 1, 2, 3, 5, 8, 13, 21, ... and let's call these
the Fibonacci Fractions: 1/2, 2/3, 3/5, 5/8, 8/13, ... etc
Where are they in the table, or in other words, what is the path to each of them?
What about ratios of two consecutive Lucas numbers (2,) 1, 3, 4, 7, 11, ...
(2/1,) 1/3, 3/4, 4/7, 7/11, 11/18, ... ? What are their paths and what pattern can you see in them?
More patterns in the SB tree
The fractions in every row are in order of size
Since we always insert the mediant of two fractions between them to make the SB tree,
and since the mediant of A and B when A < B is always bigger than A and less than B,
then every row of the SB tree
will always have its fractions in the order of size.
The pattern in the Numerators
If we list the numerators of the fractions in the SB tree between 0/1 and 1/1
we find:
Since the top row's numerators are 0 and 1 then the second row begins 0,1 too and so every row
will begin not only with 0,1 but with the whole of the previous row as its first half.
What about the second half of each row's numerators?
If we write down the previous row and underneath it the reverse of the previous row,
then we can add corresponding pairs to get the second half. For instance:
1, 2, 3, 3 3, 3, 2, 1
+
4, 5, 5, 4
So the whole of the row is 1,2,3,3, 4,5,5,4
Another pattern is that the numerators of the second half of any row are
just the denominators of the previous row!
4,5,5,4 are the denominators of the row 1/4, 2/5, 3/5, 3/4
The pattern in the Denominators
This time the pattern in the denominators of the two halves of any row is easy to spot:
The second half of any row is the reverse of the first half!
Can you find a rule to write down either half of one row given the previous row(s)?
The first half of any row is the sum of the numerators and denominators of
each fraction in the previous row.
For example:
The row 1/4, 2/5, 3/5, 3/4 means that the next row's denominators begin:
1+4=5, 2+5=7, 3+5=8, 3+4=7
with the rest of the row being the reverse of this pattern.
The whole row is therefore 5,7,8,7, 7,8,7,5
The pattern in the continued fractions
On of the remarkable things about the SB tree is that it is closely related to expressing Fractions
as continued fractions.
As an example, let's take 11/4. We can write this as
11
= 2 +
1
4
1 +
1
3
where we only use additions and fractions with a numerator of 1.
The abbreviated notation which takes up much less space on the page
is [2; 1, 3] where the initial whole-number part is followed by a semicolon.
To take the reciprocal of a fraction, we put a 0 in front (or, if the whole number part was 0 already, remove it):
4
= 0 +
1
11
2 +
1
1 +
1
3
= [0; 2, 1, 3].
The remarkable thing about the SB tree is that
On each level of the SB tree, the sum of the terms in every continued fraction
is the same!
In fact, all combinations that give the row number are present because any CF that ends in 1 can have that
1 added to the previous term and the CF still represents exactly the same fraction: [ ..., a, 1 ] = [ ..., a+1]
So there are no combinations ending in 1 as we show all CFs in the form which ends with a term greater than 1.
Note that with a sum of 5, the CF [0; 2,1,2] = 3/8 = [0; 2,1,1,1]
whereas the same numbers in a different order give a different
fraction: [0; 1,2,2] = 5/7 = [0; 1,2,1,1]. [0; 2,2,1] ends in 1 and is the same as [0; 2,3] = 3/7.
If we look at the full SB tree including fractions bigger than 1, the CFs are the same as those above but with the initial
zero removed, so the sum of the items in each CF on one level in the complete tree is the same.
Partitions of an integer N
A collection of whole numbers whose sum is N, where the order does not matter and numbers may be repeated
For instance, the partitions of 3 are [1,1,1], [1,2] and [3] only. [2,1] is the same partition
(contains exactly the same elements) as [1,2].
Since repetitions are allowed in a partition, these are also called multisets or bags.
If repetitions are not allowed, then we call them partition-sets.
Compositions of a number N
A sequence of whole numbers whose sum in N, where the order does matter and numbers may be repeated.
For instance, the compositions of 3 are [1,1,1], [1,2], [2,1] and [3] because the order is now important.
Often we use the term list since the order in the list matters and items can be repeated. Also, as a generalisation of
double, triple, quadrulple, ... they are also called tuples and my be written inside round brackets instead of square ones.
More...
What about non-fractional numbers - the irrationals such as √2 or e or π?
There is a close connection between the Stern-Brocot tree and LR paths of the fractions that best
approximate any irrational value - a property of continued fractions.
There is more to read on this in Graham, Knuth and Patashnik's
Concrete Mathematics - see the References section that follows.
Or you can explore all the patterns of ordinary decimal fractions using
the Fractions Converter at this site, where the decimal fractions are
computed to many places.
You can explore more about the
continued fraction representation of fractions and the Stern-Brocot tree on
an Introduction to Continued Fractions page at this site.
References
The tree is named after Moritz Stern and Achille Brocot who both wrote about it independently around
1858.
Uebe eine zahlentheoretische Funktion M A Stern, Journal für die reine und angewandte Mathematik
vol 55 (1858) pages 193-220
The original references for the Stern-Brocot tree together with ...
Calcul des rouages par approximation, nouvelle méthode
Achille Brocot Revue Chronométrique 6 (1860) pages 186-194
On Farey fractions origins, see:
On a curious property of vulgar fractions J Farey London, Edinburgh and Dublin Philosophical Magazine vol 47 (1816)
pages 385-386
is the original letter by Farey on what are now called 'Farey fractions'. However, he only spotted that the
mediant of two fractions lies between them and offered no proof. This was already known and had been published :
Tables pour évaluer une fraction ordinaire avec autant de
decimales qu'on voudra; et pour trouver la fraction ordinaire la plus
simple, et qui approche sensiblement d'une fraction décimal C. Haros Journal
de L'Ecole Royale Polytechnique Tome IV (Cahier 11) (1802), pages 364-368.
...but the name that has 'stuck' to the ordered row of fractions less than one with denominators no bigger than
n, is the order n Farey sequence, i.e. it is Farey's name and not Haros's!
Here are some great books that contain sections on Farey Fractions and the Stern-Brocot tree:
Introduction to the Theory of numbers G H Hardy, E M Wright,
Oxford University Press, 5th edition, 1980,
ISBN: 0198531710
is a classic book well worth studying
but some parts are at mathematics undergraduate level. There is a whole chapter on the basic
result of Farey Series with proofs.
Neverending Fractions - An Introduction to Continued Fractions J Borwein, A van der Poorten,
J Shallit, W Zudilin (Cambridge, 2014)
is a new book with all the basics of the theory developed from scratch.
It covers the material on this page in detail and much much more. Highly recommended for undergraduate mathematicians.
Concrete Mathematics
(2nd edition, 1994) by Graham, Knuth and Patashnik, Addison-Wesley.
is highly recommended but is at undergraduate mathematics level. Section 4.5 is
a wonderful introduction to more of the mathematics of the Farey series and the Stern-Brocot tree,
paths in the tree and continued fractions.
icon means there is a
Things to do section of questions to start your own investigations.
The 
calculator icon
indicates that there is a live interactive calculator in that section.
If we look again at the diagram above of Ford circles, we see that the Stern-Brocot tree shows which circles
touch other circles and which are the largest circles in any gap.
© 2008-2018 Dr Ron Knott
