Farey sequence

English

Named after British geologist Template:W, whose letter about the sequences was published in the Template:W in 1816.

Template:Lb For a given positive integer n, the sequence of completely reduced fractions between 0 and 1 which, when in lowest terms, have denominators less than or equal to n, arranged in order of increasing size.
- Template:Quote-book
- 2007, Jakub Pawlewicz, Order Statistics in the Farey Sequences in Sublinear Time, Lars Arge, Michael Hoffmann, Emo Welzl (editors), Algorithms - ESA 2007: 15th Annual European Symposium, Proceedings, Springer, Template:W 4698, page 218,
  The Farey sequence of order $n$ (denoted $ℱ_{n}$ ) is the increasing sequence of all irreducible fractions from interval $[0, 1]$ with denominators less than or equal to $n$ . The Farey sequences have numerous interesting properties and they are well known in the number theory and in the combinatorics.
- Template:Quote-book

The sequence for given $n$ may be called the Farey sequence of order $n$ , and is often denoted $F_{n}$ .
The sequences are cumulative: each $F_{n}$ is contained in $F_{n + 1}$ . The added elements are those fractions $\frac{m}{n + 1}$ for which $m$ and $n + 1$ are coprime.
The restriction that the fraction be in the range [0,1] (i.e., 0≤ numerator ≤ denominator) is sometimes omitted.
- With the restriction in place, every Farey sequence begins with $\frac{0}{1}$ and ends with $\frac{1}{1}$ .