Small Fractions: Farey Series and Fraction Trees
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 |
| ... |
John Farey gives his name to these series after he asked a question about
these series of ordered fractions in a letter published in 1816.
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
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 form 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 equal
to the mediant of the other two.
John Farey observed this in the letter of 1816 and asked if it was always true. It was soon proved so by Cauchy who
gave the name "Farey series" to thrm and it has been used ever since.
A Tree of Fractions
We can use the mediant operation to generate rows of small fractions beginning with
0/1 and 1/1
whose mediant is 1/2, as follows:
Each layer or level includes the fractions from the previous level and every gap between two on the
previous level is filled with its mediant fraction.
| 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 |
< | ... |
As a result, each fraction (apart from 0 and 1) is a mediant of
two successive 'parent' fractions on the previous level and it first appears nestled
between its two fractions.
Any two
neighbours on any level generate a 'child', their mediant, on the next level.
This family 'tree' of fractions has some interesting properties:
- eventually all fractions appear in the tree
- when we first form the mediant of two fractions as in this tree, the mediant is always in its lowest terms
This is not always so in the Farey series where, for instance, we find
1/6 1/5 1/4 together but the mediant of
the outer two:1/6 and 1/4 is 2/10
which must be reduced to get 1/5 between them.
- On later levels other fractions will separate a mediant from its 'parents' but
the mediant rule will still hold in that the middle fraction of any three consecutive
fractions is equal to the mediant but may need to be reduced to its lowest terms.
- 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 has twice the number on the row before, less 1.
Since there are 2 fractions on the top level, there are 2L + 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 the tree
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,
like the rest of this book that I would highly recommend to anyone who has enjoyed this 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.
© 2008 Dr Ron Knott
created: 26 March 2008
|