The** Farey sequence** of order is the ascending sequence of irreducible fractions between 0 and 1, whose denominators do not exceed . This sequence was discovered by Charles Haros in 1806, but Augustin-Louis Cauchy named it after geologist John Farey.

Thus belongs to if and , the numbers 0 and 1 are included in the forms and . For example,

Following are the characteristic properties of Farey sequence (for proofs refer §3.3, §3.4 and §3.7 of G. H. Hardy and E. M. Wright’s *An Introduction to the Theory of Numbers*):

- If and are two successive terms of , then .
- If , and are three successive terms of , then .
- If and are two successive terms of , then the
**mediant**of and falls in the interval . - If , then no two successive terms of have the same denominator.

The **Stern-Brocot tree**, which we saw earlier while understanding the working of clocks, is a data structure showing how the sequence is built up from 0 (=0/1) and 1 (=1/1) by taking successive mediants.

Now, consider a circle of unit circumference, and an arbitrary point of the circumference as the representative of 0 (zero), and represent a real number by the point whose distance from , measured round the circumference in the anti-clockwise direction, is .

Plainly all integers are represented by the same point , and numbers which differ by an integer have the same representative point.

Now we will divide the circumference of the circle in the following manner:

- We take the Farey sequence , and form all the mediants of the successive pairs , . The first and last mediants are and . The mediants naturally do not belong themselves to .
- We now represent each mediant by the point . The circle is thus divided up into arcs which we call
**Farey arcs**, each bounded by two points and containing one**Farey point**, the representative of a term of . Thus is a Farey arc containing the one Farey point .

The aggregate of Farey arcs is called **Farey dissection** of the circle. For example, the sequence of mediants for , say is

And hence the Farey disscetion looks like:

Let . If is a Farey point, and, are the terms of which precede and follow , then the Farey arc around is composed of two parts, whose lengths are

respectively. Now , since and are unequal (using the point (4.) stated above)and neither exceeds ; and (using the point (3.) stated above). We thus obtain:

Theorem:In the Farey dissection of order , there , each part of the arc which contains the representative has a length between and .

For example, for we have:

Using the above result, one can prove the following result about rational approximations (for more discussion, see §6.2 of Niven-Zuckerman-Montgomery’s *An Introduction to the Theory of Numbers*):

Theorem:If is a real number, and a positive integer, then there is an irriducible fraction such that and

One can construct a geometric proof of Kronceker’s theorem in one dimension using this concept of Farey dissection. See §23.2 of G. H. Hardy and E. M. Wright’s *An Introduction to the Theory of Numbers *for details.

Blast. I remember there being some amusing anecdote about how I became aware of Farey Sequences but now I can’t think what it was.

LikeLiked by 1 person

Yes, absolutely beautiful…Yes, it is presented in Niven and Zuckermann; but I think I had found some need/reference to it some computer science/algorithm text also. …just to mention, Fibonacci numbers are used in DSP (digital signal processing) to design certain filters…more later…

LikeLiked by 1 person