Navigation 
 Home 
 Search 
 Site map 

 Contact Graeme 
 Home 
 Email 
 Twitter

 Skip Navigation LinksMath Help > Sequences and Series > Sequences > Farey Sequences

The nth Farey Sequence, Fn, is the sequence of rational numbers a/b, such that GCD(a,b)=1, and 0 ≤ a ≤ b ≤ n.  For example,

F5 is {0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1}

If a/b and c/d are successive terms of a Farey sequence, then bc - ad=1.   That is, the product of the means minus the product of the extremes is 1.

The denominators, b and d, of adjacent elements of a Farey sequence are coprime, because numbers x and y exist such that bx+dy=1.  In fact, x and y are the numerators (the first one negative) of these adjacent elements.

Similarly, the numerators, a and c, of adjacent elements of a Farey sequence are coprime, because ax+cy=1, where x=-d and y=b.

Mediant

The "mediant" of two fractions expressed in lowest terms, a/b and c/d, is (a+c)/(b+d).  For example,

the mediant of 2/5 and 1/2 is (2+1)/(5+2) = 3/7

Each element of a Farey Sequence that has two neighbors is the mediant of those two neighbors.  For example, in F5, 3/5 lies between 1/2 and 2/3, and 3/5 is the mediant of 1/2 and 2/3.

Let a/b, c/d, e/f be successive elements of a Farey Sequence,
so bc-ad=1 and de-cf=1.
Thus bc-ad+cf-de=0.
Rearranging this, d(a+e)=c(b+f), so c/d=(a+e)/(b+f)

This fact can be used to find Fn+1 given Fn.  For each pair of successive elements of Fn in which the sum of their denominators equals n+1, the mediant can be inserted between them to form Fn+1.  The mediants formed this way will always be in lowest terms because both the denominators and numerators of adjacent elements of a Farey Sequence are coprime, and the sum of two coprime numbers is coprime to each of them.

Farey Sunburst

Letting F6 = {y1/x1, y2/x2, ...} the (x,y) pairs are plotted on a lattice, occupying the first half of the first quadrant (i.e. the first octant).  To complete the starburst, this sequence is repeated seven more times with reflections about the line y=x and the axes. 

Farey Triangle

The image to the right shows F5, extended the same way, and blown up so you can see the sequence of triangles formed with the origin and two successive elements of a F5.

I will call a lattice triangle a "Farey Triangle" if its vertices are (0,0), (x1,y1), and (x2,y2), or one of its seven other reflections, where x1/y1 and x2/y2 are adjacent elements of a Farey sequence.  The Farey Triangles in the diagram to the right are the thin triangles with yellow interior and one vertex at the origin.

It is fairly easy to see that the area of each of the Farey triangles is 1/2.  Since its vertices are (0,0), (a,b), (c,d), its area is |ad-bc|/2.  And since a/b and c/d are successive elements of a Farey sequence, |ad-bc|=1, proving the result.

Relationship of Farey Sequences to Pick's Theorem

From the origin, we will call a lattice point (x,y) "visible" if GCD(x,y)=1.  Two lattice points (x1,y1), (x2,y2), in which the largest x- or y- coordinate (in absolute value) is n, will be called n-Farey-adjacent if, from the point of view of the origin, no other lattice point with coordinates no larger than n is visible between them.

A triangle formed by the origin and two n-Farey-adjacent lattice points is a Farey triangle, and (as proved above) has an area of 1/2.

Conversely, a lattice triangle whose longest side's longest component measures n units, and whose border contains only the three lattice points of its vertices, and whose interior has no lattice points is congruent to a Farey triangle, because viewed from one end of its longest side, the other two vertices are n-Farey-adjacent.

Internet references

Mathworld: Farey Sequence 

Cut-the-knot: Farey Sequence and its application to Pick's Theorem  

Related pages in this website

Pick's Theorem, for finding the area of lattice polygons.

The area of a triangle with vertices (0,0), (a,b), (c,d) is |ad-bc|/2. 

See also Recurrence Relation

 


The webmaster and author of this Math Help site is Graeme McRae.