Fractions in the Farey Series and the Stern-Brocot Tree
Contents
The 
icon means there is a
Things to do investigation at the end of the section. The 
icon means there is an
interactive calculator in this 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:
| order | Farey series | count |
|---|
| 1 | | 0 | | 1 | | | | 1 | 1 |
| 2 |
| 2 | | 3 |
| 3 | | 5 |
| 4 | | 7 |
| 5 | | 0 | | 1 | | 1 | | 1 | | 2 | | 1 | | 3 | | 2 | | 3 | | 4 | | 1 | | | | | | | | | | | | | 1 | 5 | 4 | 3 | 5 | 2 | 5 | 3 | 4 | 5 | 1 |
| 11 |
| 6 | | 0 | | 1 | | 1 | | 1 | | 1 | | 2 | | 1 | | 3 | | 2 | | 3 | | 4 | | 5 | | 1 | | | | | | | | | | | | | | | 1 | 6 | 5 | 4 | 3 | 5 | 2 | 5 | 3 | 4 | 5 | 6 | 1 |
| 13 |
| ... |
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
This is because if a/b is in a Farey series
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:
Level 6: 1 6 5 4 3 5 2 5 3 4 5 6 1
Level 7: 7 7 7 7 7 7
The Numerators
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.
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 |
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:
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 |
|---|
| 0 | 0/1 | | | | | | | | 1/1 | 2 |
| 1 | 0/1 | | | | 1/2 | | | | 1/1 | 3 |
| 2 | 0/1 | | 1/3 | | 1/2 | | 2/3 | | 1/1 | 5 |
| 3 | 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 3: 0/1, 1/4, 1/3, 2/5, 1/2,3/5, 2/3, 3/4, 1
level 4: 0/1, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 1
but
Farey series of order 5: 0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 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)/(6+4) = 2/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/1, 1/5, .... 2/7, 1/3, 3/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 Farey series will also
apply to any consecutive pair of fractions in this tree too:
| level 4: | ..., 2/7, | 1/3,... | and their mediant is 2×3 = 6, 7×1 = 7 |
| level 4: | ...., | 1/3, 3/8... | and their mediant is 1×8 = 8, 3×3 = 9 |
The Stern-Brocot Tree of Fractions
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)!
| level | fractions |
|---|
| < 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 level are in order of size
A Path in the Tree to every fraction
We can now find a unique path from 1/1 to any and every fraction.
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
| 0/1 |
1/1 |
1/0 |
L
1/2 | R
2/1 |
L
1/3 |
R
2/3 |
L
3/2 |
R
3/1 |
L
1/4 |
R
2/5 |
L
3/5 |
R
3/4 |
L
4/3 |
R
5/3 |
L
5/2 |
R
4/1 |
For example:
- 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
which gives us a nice method of computing the LR path from 1/1 to m/n:
- Input: the fraction being sought, Output will be the LR path to this fraction
- Two fractions define the RANGE within which we are looking for our fraction:
0/1 and 1/0. Call these two fractions Start and End.
- We will build up the path letter by letter and the PATH is initially empty.
-
- Find the MEDIANT of Start and End
- If MEDIANT = the fraction sought then STOP and print out the PATH found so far
- Otherwise:
- If m/n < MEDIANT then
add an "L" on to the end of the PATH and
change End to be equal to MEDIANT
- If m/n > MEDIANT then
add an "R" on to the end of the PATH and
change Start to be equal to MEDIANT
- Keep repeating the previous step until the method stops.
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
but here is a Calculator to do both.
Limitations in the Calculator:
Note that the fraction 1/N occurs for the first time at the start of row N
in the tree so its path can be very long compared to other fractions: the path
to 1/1000000 is one million L's! As a result, the paths of some
fractions cannot be fully computed with this Calculator.
Similarly, computing mediants involves very large numbers if the fractions
have a large denominator or numerator and this too limits the computation of
the fractions corresponding to some paths.
There are now several interesting questions that you can work on for yourself:
Things to do
- (Easy) If m/n is in its lowest form, on what level does it appear in the tree?
- (Easy) How long is the path for fraction m/n?
- 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?
- (Easy) Where are the integers in the tree?
- (Easy) Look again at the table of Farey fractions at the start of this page
or use the first Farey Calculator above to answer these questions:
- 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?
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. There is more to read on this in Graham, Knuth and Patashnik's
Concrete Mathematics - see the References section that follows.
What is a Continued Fraction? See An Introduction to Continued Fractions
at this site and also the online Continued Fractions Calculator.
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.
References
The tree is named after Moritz Stern and Achille Brocot who both wrote about it independently around
1858.
Recreations in
the Theory of Numbers - The Queen of Mathematics Entertains
A H Beiler, Dover, 1964
-
has a whole chapter on Farey Tales that is informative, fun and not at all too mathematical.
I highly recommend this book to anyone who has enjoyed this page and
Ron Knott's other maths web pages.
On a Curious Property of Vulgar Fractions J Farey London, Edinburgh and Dublin Phil. Mag
vol 47 (1816) page 385.
-
-
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 teh basic
result of Farey Series with proofs.
-
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 ...
-
Calcul des rouages par approximation, nouvelle méthode
Achille Brocot Revue Chronométrique 6 (1860) pages 186-194
-
-
On a curious property of vulgar fractions J Farey 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.
- ...however, 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!
-
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.
© 2008-2011 Dr Ron Knott
created: 26 March 2008, updated 16 April 2011