Sales Toll Free No: 1-855-666-7446

Farey Sequence

Top

In mathematics, sequences and series are two very important topics. A sequence is a list of numbers, each of which satisfy a certain property. For example : 1, 4, 7, 10, ...
While, in a series the terms of a sequence are summed up.

For Example : 1 + 4 + 7 + 10 + ...

Farey sequence has always been a sequence of interest in mathematics. This sequence was named after a famous British geologist John Farey.

A sequence is known as Farey sequence which is made up of totally reduced fractions from 0 to 1, i.e. this sequence always has 0 as its lowest term and 1 as its highest term.

In other words, a Farey sequence of order n is a sequence consisting positive fractions, in which the denominators are less than or equal to the order n.

The terms in a Farey sequence lie between 0 to 1 and are arranged ascending order. Each term in Farey sequence is denoted in the form of

fraction, such as : 0 is written as fraction $\frac{0}{1}$; while 1 is denoted by fraction $\frac{1}{1}$.

The Farey sequence is usually represented by the notation $F_{n}$, where n denotes a positive integer. It is said to be a sequence of order n in which the terms are the members of set of irreducible rational number in the form of $\frac{p}{q}$ with the property 0 $\leq$ p $\leq$ q $\leq$ n, that are arranged in ascending order.

The first-order Farey sequence is:

$F_{1}$ = {$\frac{0}{1}$,$\frac{1}{1}$}

The second-order Farey sequence be:

$F_{2}$ = {$\frac{0}{1}$,$\frac{1}{2}$,$\frac{1}{1}$}

The third-order Farey sequence is:

$F_{3}$ = {$\frac{0}{1}$,$\frac{1}{3}$,$\frac{1}{2}$,$\frac{2}{3}$,$\frac{1}{1}$}

The fourth-order Farey sequence be:

$F_{4}$ = {$\frac{0}{1}$,$\frac{1}{4}$,$\frac{1}{3}$,$\frac{1}{2}$,$\frac{2}{3}$,$\frac{3}{4}$,$\frac{1}{1}$}

and so on.

A tree showing the pattern of Farey sequence is illustrated below :
Farey Sequence

Let us suppose that if $\frac{p_{1}}{q_{1}}$, $\frac{p_{2}}{q_{2}}$, $\frac{p_{3}}{q_{3}}$ are three successive members of Farey sequence, then

$\frac{p_{2}}{q_{2}}$=$\frac{p_{1}+p_{3}}{q_{1}+q_{3}}$
A Farey sequence when the terms are summed up, is known as Farey series.

Proof

Back to Top
The construction of Farey sequence can be proved. This proof is as follows :

Let us suppose that a Farey sequence of order n i.e. F$_{n}$, has two consecutive terms $\frac{p}{q}$ and $\frac{r}{s}$. Then, Farey

sequence of order order n+1 i.e $F_{n+1}$ may be constructed by adding the mediant term $\frac{p+r}{q+s}$ in sequence $F_{n}$. Here,

by the definition Farey sequence, we may write that b + d = n + 1.

We also know that
$\frac{p}{q}$< $\frac{p+r}{q+s}$< $\frac{r}{s}$
And
r + s is irreducible in $\frac{p+r}{q+s}$

In the order n + 1 Farey sequence, there will be addition element than F$_{n}$ equal to $\phi$(n + 1)

Now the all mediant values of $F_{n}$ converge in $F_{n+1}$. Also, $\frac{1}{n+1}$ and $\frac{n}{n+1}$ do involve in it.
In this way a Farey sequence can be constructed and verified.

Properties

Back to Top
Farey sequence has the following important properties :
1) Mediant Property
This Property states that if $\frac{p}{q}$ and $\frac{r}{s}$ be two terms in a Farey sequence and $\frac{p}{q}$ < $\frac{r}

{s}$
, then their mediant which is computed by the relation $\frac{p+r}{q+s}$, lies between $\frac{p}{q}$ and $\frac{r}{s}$

and $\frac{p}{q}$ < $\frac{p+r}{q+s}$ < $\frac{r}{s}$.

2) In Farey sequence, for any two consecutive fractions $\frac{p}{q}$ and $\frac{r}{s}$, q + s $\leq$ n + 1.

3) The fractions $\frac{p}{q}$ and $\frac{r}{s}$ are successive fractions in a Farey sequence if and only if q r - p s = 1.

4) For a Farey sequence of order n ($F_{n}$), the total number of terms are given by the relation $\frac{3n^{2}}{\pi^{2}}$ ; provided that n is sufficiently large.

5) In a Farey sequence $F_{n}$, if $\frac{p}{q}$ be a fraction, then there must exist a nearby fraction in $F_{n}$ for a

real number x ; such that |$x$ - $\frac{p}{q}$| $\leq$ $\frac{1}{q(n+1)}$

Examples

Back to Top
The few examples of Farey sequence are as follows:

Example 1 : Write Farey sequence of order 1 and order 2.

Solution : Farey sequence of order 1 is given by:

$F_{1}$ = {$\frac{0}{1},\frac{1}{1}$}

The second-order Farey sequence can be obtained by adding  the numerators and denominators of terms of $F_{1}$ -

$F_{2}$ = {$\frac{0}{1},\frac{0+1}{1+1},\frac{1}{1}$}

= 0{$\frac{0}{1},\frac{1}{2},\frac{1}{1}$}

Example 2 : Give Farey sequence of order 4. Deduce Farey sequence of order 5 from it.

Solution : Farey sequence of order 4, i.e.

$F_{4}$ = {$\frac{0}{1},\frac{1}{4},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{3}{4},\frac{1}{1}$}

Then Farey sequence of order 5 will be

$F_{5}$ = {$\frac{0}{1},\frac{0+1}{1+4}, \frac{1}{4},\frac{1}{3},\frac{1+1}{3+2}, \frac{1}{2},\frac{1+2}{2+3}, \frac{2}{3},\frac{3}{4},\frac{3+1}{4+1}, \frac{1}{1}$}

$F_{5}$ = {$\frac{0}{1},\frac{1}{5}, \frac{1}{4},\frac{1}{3},\frac{2}{5}, \frac{1}{2},\frac{3}{5}, \frac{2}{3},\frac{3}{4},\frac{4}{5}, \frac{1}{1}$}

Example 3 : Write eighth order Farey sequence.

Solution : Eighth order Farey sequence is given by :

$F_{8}$ = {$\frac{0}{1}, \frac{1}{8}, \frac{1}{7}, \frac{1}{6}, \frac{1}{5}, \frac{1}{4}, \frac{0}{1}, \frac{2}{7}, \frac{1}{3}, \frac{3}{8}, \frac{2}{5}, \frac{3}{7}, \frac{1}{2}, \frac{4}{7}, \frac{3}{5}, \frac{5}{8}, \frac{2}{3}, \frac{5}{7}, \frac{3}{4}, \frac{4}{5}, \frac{5}{6}, \frac{6}{7}, \frac{7}{8}, \frac{1}{1}$}