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 Things To Do icon means there is a Things to do section of questions to start your own investigations. The calculator 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
543525345
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 2 1 1 2 0 1 1 3 1 2 1 3 0 1 1 2 1 5 1 3 2 3 1 4 0 1 1 1 2 3 1 7 1 4 3 2 3 4 1 5 0 1 1 1 2 1 3 2 3 4 1 11 1 5 4 3 5 2 5 3 4 5 1 6 0 1 1 1 1 2 1 3 2 3 4 5 1 13 1 6 5 4 3 5 2 5 3 4 5 6 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:
Level 6: 1 6 5 4 3 5 2 5 3 4 5 6 1 Level 7: 7 7 7 7 7 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.
Level 1: 1 1 Level 2: 1 2 1 Level 3: 1 3 2 3 1 Level 4: 1 4 3 2 3 4 1 Level 5: 1 5 4 3 5 2 5 3 4 5 1 Level 6: 1 6 5 4 3 5 2 5 3 4 5 6 1 Level 7: 1 7 6 5 4 7 3 5 7 2 7 5 3 7 4 5 6 7 1 Level 8: 1 8 7 6 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 6 7 8 1

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.

A Farey Fractions Calculator calculator

Farey Fractions C A L C U L A T O R

with a denominator up to

R E S U L T S


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
bq

The Stern-Brocot Tree of Fractions

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.
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:
levelseriescount
10/1 1/12
20/1 1/2 1/13
30/1 1/3 1/2 2/3 1/15
40/11/41/32/51/23/52/33/41/19
...
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: 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)!
rowfractions
< 1= 1>1
00/1 1/0
10/11/11/0
20/11/21/12/11/0
30/11/31/22/31/13/22/13/11/0
40/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/22/1
1/32/33/23/1
1/42/53/53/4 4/35/35/24/1
Did you notice that:
the fractions on each row 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 - 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
For example:

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:
    1. Find the mediant of start and end
    2. If mediant = m/n
      then print out the path found so far and STOP
      otherwise if mediant > m/n
      then
      1. add an L on to the end of the path
      2. change end to be equal to mediant
      otherwise mediant < m/n so
      1. add an R on to the end of the path
      2. change start to be equal to mediant
  1. 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 calculator

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
Fraction: LR Path:
show fractions
along path:
from top to level

R E S U L T S

There are now several interesting questions that you can work on for yourself:

/ Things to do /

  1. 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?
  2. (Easy) Where are the fractions of the form 1/n in the tree?
  3. (Easy) Where are the integers in the full tree?
  4. (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:
    1. 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?
    2. Now try the same thing but for the denominators.
  5. 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?
  6. 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.
What is a Continued Fraction?
See An Introduction to Continued Fractions at this site and also the online Continued Fractions Calculator
As an example, let's take 11/4. We can write this as
11 = 2 + 1
41 + 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
112 + 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. On Farey fractions origins, see: Here are some great books that contain sections on Farey Fractions and the Stern-Brocot tree:
Other pages on Fractions by Dr Ron Knott:
The HOME page of this site is:


Valid HTML 4.01! © 2008-2017 Dr Ron Knott
created: 26 March 2008, updated 13 March 2017