Definition:Farey Sequence
Definition
A Farey sequence is a chain of subsets of the reduced rational numbers lying in $\Q \cap \closedint 0 1$.
For $Q \in \Z_{>0}$, the Farey set $F_Q$ is the set of all reduced rational numbers with denominators not larger than $Q$:
- $F_Q = \set {\dfrac p q: p = 0, \ldots, Q,\ q = 1, \ldots, Q,\ p \perp q}$
where $p \perp q$ denotes that $p$ and $q$ are coprime.
Order of Farey Sequence
Let $F_Q$ denote the Farey sequence of all reduced rational numbers with denominators not larger than $Q$:
- $F_Q = \set {\dfrac p q: p = 0, \ldots, Q,\ q = 1, \ldots, Q,\ p \perp q}$
The index $Q$ is called the order of $F_Q$.
Examples
Order $5$
The Farey sequence $F_5$ of order $5$ is:
- $\dfrac 0 1, \dfrac 1 5, \dfrac 1 4, \dfrac 1 3, \dfrac 2 5, \dfrac 1 2, \dfrac 3 5, \dfrac 2 3, \dfrac 3 4, \dfrac 4 5, \dfrac 1 1$
Also see
- Results about Farey sequences can be found here.
Source of Name
This entry was named for John Farey.
Historical Note
The Farey sequence was first exploited by Charles Haros in $1801$ in creating tables of the decimal expansions for all vulgar fractions whose denominators are less than $100$.
In order to make sure he captured them all, he used a technique exploiting the properties of the mediant that originated with Nicolas Chuquet.
Some $15$ years later, John Farey rediscovered this property, and published a paper on the subject.
This was subsequently picked up on by Augustin Louis Cauchy, who reproved the results of Charles Haros while crediting John Farey with the technique.
Source
- 1801: Charles Haros: Tables pour évaluer une fraction ordinaire avec autant de decimals qu'on voudra; et pour trouver la fraction ordinaire la plus simple, et qui approche sensiblement d'une fraction décimale (J. l'École Polytechnique Vol. 6, no. 11: pp. 364 – 368)
- 1816: John Farey: On a Curious Property of Vulgar Fractions (Phil. Mag. Vol. 47, no. 3: pp. 385 – 386)
- 1989: Ephraim J. Borowski and Jonathan M. Borwein: Dictionary of Mathematics ... (previous) ... (next): Farey sequence
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): Farey sequence (of order $n$)
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): Farey sequence (of order $n$)