# Farey sequence

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Farey_sequence
> Markdown URL: https://mediated.wiki/source/Farey_sequence.md
> Source: https://en.wikipedia.org/wiki/Farey_sequence
> Source revision: 1356826180
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [mathematics](/source/Mathematics), the **Farey sequence** of order *n* is the [sequence](/source/Sequence) of completely reduced [fractions](/source/Fraction), either between 0 and 1, or without this restriction,[a] which have [denominators](/source/Denominator) less than or equal to *n*, arranged in order of increasing size.

With the restricted definition, each Farey sequence starts with the value 0, denoted by the fraction 0⁄1, and ends with the value 1, denoted by the fraction 1⁄1 (although some authors omit these terms).

A *Farey sequence* is sometimes called a Farey [*series*](/source/Series_(mathematics)), which is not strictly correct, because the terms are not summed.[1]

## Examples

The Farey sequences of orders 1 to 8 are :

- *F*1 = { 0⁄1, 1⁄1 }
- *F*2 = { 0⁄1, 1⁄2, 1⁄1 }
- *F*3 = { 0⁄1, 1⁄3, 1⁄2, 2⁄3, 1⁄1 }
- *F*4 = { 0⁄1, 1⁄4, 1⁄3, 1⁄2, 2⁄3, 3⁄4, 1⁄1 }
- *F*5 = { 0⁄1, 1⁄5, 1⁄4, 1⁄3, 2⁄5, 1⁄2, 3⁄5, 2⁄3, 3⁄4, 4⁄5, 1⁄1 }
- *F*6 = { 0⁄1, 1⁄6, 1⁄5, 1⁄4, 1⁄3, 2⁄5, 1⁄2, 3⁄5, 2⁄3, 3⁄4, 4⁄5, 5⁄6, 1⁄1 }
- *F*7 = { 0⁄1, 1⁄7, 1⁄6, 1⁄5, 1⁄4, 2⁄7, 1⁄3, 2⁄5, 3⁄7, 1⁄2, 4⁄7, 3⁄5, 2⁄3, 5⁄7, 3⁄4, 4⁄5, 5⁄6, 6⁄7, 1⁄1 }
- *F*8 = { 0⁄1, 1⁄8, 1⁄7, 1⁄6, 1⁄5, 1⁄4, 2⁄7, 1⁄3, 3⁄8, 2⁄5, 3⁄7, 1⁄2, 4⁄7, 3⁄5, 5⁄8, 2⁄3, 5⁄7, 3⁄4, 4⁄5, 5⁄6, 6⁄7, 7⁄8, 1⁄1 }

Centered F1 = { 0⁄1, 1⁄1 } F2 = { 0⁄1, 1⁄2, 1⁄1 } F3 = { 0⁄1, 1⁄3, 1⁄2, 2⁄3, 1⁄1 } F4 = { 0⁄1, 1⁄4, 1⁄3, 1⁄2, 2⁄3, 3⁄4, 1⁄1 } F5 = { 0⁄1, 1⁄5, 1⁄4, 1⁄3, 2⁄5, 1⁄2, 3⁄5, 2⁄3, 3⁄4, 4⁄5, 1⁄1 } F6 = { 0⁄1, 1⁄6, 1⁄5, 1⁄4, 1⁄3, 2⁄5, 1⁄2, 3⁄5, 2⁄3, 3⁄4, 4⁄5, 5⁄6, 1⁄1 } F7 = { 0⁄1, 1⁄7, 1⁄6, 1⁄5, 1⁄4, 2⁄7, 1⁄3, 2⁄5, 3⁄7, 1⁄2, 4⁄7, 3⁄5, 2⁄3, 5⁄7, 3⁄4, 4⁄5, 5⁄6, 6⁄7, 1⁄1 } F8 = { 0⁄1, 1⁄8, 1⁄7, 1⁄6, 1⁄5, 1⁄4, 2⁄7, 1⁄3, 3⁄8, 2⁄5, 3⁄7, 1⁄2, 4⁄7, 3⁄5, 5⁄8, 2⁄3, 5⁄7, 3⁄4, 4⁄5, 5⁄6, 6⁄7, 7⁄8, 1⁄1 }

Sorted F1 = {0/1, 1/1} F2 = {0/1, 1/2, 1/1} F3 = {0/1, 1/3, 1/2, 2/3, 1/1} F4 = {0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1} F5 = {0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1} F6 = {0/1, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1/1} F7 = {0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1/1} F8 = {0/1, 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8, 1/1}

### Farey sunburst

Plotting the numerators versus the denominators of a Farey sequence gives a shape like the one to the right, shown for F6.

Reflecting this shape around the diagonal and main axes generates the *Farey sunburst*, shown below. The Farey sunburst of order n connects the visible [integer](/source/Integer) grid points from the origin in the square of side 2n, centered at the origin. Using [Pick's theorem](/source/Pick's_theorem), the area of the sunburst is 4( − 1), where is the [number of fractions in Fn](#Sequence_length_and_index_of_a_fraction).

## History

- *The history of 'Farey series' is very curious* — Hardy & Wright (1979)[2]

- *... once again the man whose name was given to a mathematical relation was not the original discoverer so far as the records go.* — Beiler (1964)[3]

Farey sequences are named after the [British](/source/United_Kingdom) [geologist](/source/Geologist) [John Farey, Sr.](/source/John_Farey,_Sr.), whose letter about these sequences was published in the *[Philosophical Magazine](/source/Philosophical_Magazine)* in 1816.[4] Farey conjectured, without offering proof, that each new term in a Farey sequence expansion is the [mediant](/source/Mediant_(mathematics)) of its neighbours. Farey's letter was read by [Cauchy](/source/Cauchy), who provided a proof in his *Exercices de mathématique*, and attributed this result to Farey. In fact, another mathematician, [Charles Haros](/source/Charles_Haros), had published similar results in 1802 which were not known either to Farey or to Cauchy.[3] Thus it was a historical accident that linked Farey's name with these sequences. This is an example of [Stigler's law of eponymy](/source/Stigler's_law_of_eponymy).

## Properties

### Sequence length and index of a fraction

The Farey sequence of order n contains all of the members of the Farey sequences of lower orders. In particular Fn contains all of the members of *F**n*−1 and also contains an additional fraction for each number that is less than n and [coprime](/source/Coprime) to n. Thus *F*6 consists of *F*5 together with the fractions 1⁄6 and 5⁄6.

The middle term of a Farey sequence Fn is always 1⁄2, for *n* > 1. From this, we can relate the lengths of Fn and *F**n*−1 using [Euler's totient function](/source/Euler's_totient_function) *φ*(*n*):

|F_n| = |F_{n-1}| + \varphi(n).

Using the fact that = 2, we can derive an expression for the length of Fn:[5]

|F_n| = 1 + \sum_{m=1}^n \varphi(m) = 1 + \Phi(n),

where Φ(*n*) is the [summatory totient](/source/Totient_summatory_function).

We also have :

|F_n| = \frac{1}{2}\left(3+\sum_{d=1}^n \mu(d) \left\lfloor \tfrac{n}{d} \right\rfloor^2 \right),

and by a [Möbius inversion formula](/source/M%C3%B6bius_inversion_formula) :

|F_n| = \frac{1}{2} (n+3)n - \sum_{d=2}^n|F_{\lfloor n/d \rfloor}|,

where *μ*(*d*) is the number-theoretic [Möbius function](/source/M%C3%B6bius_function), and \lfloor n/d \rfloor is the [floor function](/source/Floor_and_ceiling_functions).

The asymptotic behaviour of is :

|F_n| \sim \frac {3n^2}{\pi^2}.

The number of Farey fractions with denominators equal to k in Fn is given by *φ*(*k*) when *k* ≤ *n* and zero otherwise. Concerning the numerators one can define the function \mathcal{N}_n(h) that returns the number of Farey fractions with numerators equal to h in Fn. This function has some interesting properties as[6]

- \mathcal{N}_n(1)=n,
- \mathcal{N}_n(p^m)=\left\lceil(n-p^m) \left(1- 1/p \right)\right\rceil for any prime number p,
- \mathcal{N}_{n+mh}(h)=\mathcal{N}_{n}(h) + m\varphi(h) for any integer *m* ≥ 0,
- \mathcal{N}_{n}(4h)=\mathcal{N}_{n}(2h) - \varphi(2h).

In particular, the property in the third line above implies \mathcal{N}_{mh}(h)=(m-1)\varphi(h) and, further, \mathcal{N}_{2h}(h)=\varphi(h). The latter means that, for Farey sequences of even order n, the number of fractions with numerators equal to n⁄2 is the same as the number of fractions with denominators equal to n⁄2, that is \mathcal{N}_{n}(n/2) = \varphi(n/2).

The index I_n(a_{k,n}) = k of a fraction a_{k,n} in the Farey sequence F_n=\{a_{k,n} : k = 0, 1, \ldots, m_n\} is simply the position that a_{k,n} occupies in the sequence. This is of special relevance as it is used in an alternative formulation of the [Riemann hypothesis](/source/Riemann_hypothesis), see [below](#Riemann_hypothesis). Various useful properties follow:

\begin{align}
  I_n(0/1) &= 0, \\[6pt]
  I_n(1/n) &= 1, \\[2pt]
  I_n(1/2) &= \frac{|F_n|-1}{2}, \\[2pt]
  I_n(1/1) &= |F_n|-1 , \\[2pt]
  I_n(h/k) &= |F_n|-1 - I_n\left(\frac{k-h}{k}\right).
\end{align}

The index of 1⁄*k* where n⁄*i*+1 < *k* ≤ *n*⁄*i* and n is the [least common multiple](/source/Least_common_multiple) of the first i numbers, *n* = lcm([2, *i*]), is given by:[7]

I_n(1/k) = 1 + n \sum_{j=1}^{i} \frac{\varphi(j)}{j} - k\Phi(i).

A similar expression was used as an approximation of I_n(x) for low values of x in the classical paper by F. Dress.[8] A general expression for I_n(h/k) for any Farey fraction h/k is given in.[9]

### Farey neighbours

Fractions which are neighbouring terms in any Farey sequence are known as a *Farey pair* and have the following properties.

If *a*⁄*b* and *c*⁄*d* are neighbours in a Farey sequence, with *a*⁄*b* < *c*⁄*d*, then their difference *c*⁄*d* − *a*⁄*b* is equal to 1⁄*bd*. Since

\frac{c}{d} - \frac{a}{b} = \frac{bc - ad}{bd},

this is equivalent to saying that

bc - ad = 1.

Thus 1⁄3 and 2⁄5 are neighbours in *F*5, and their difference is 1⁄15.

The converse is also true. If

bc - ad = 1

for positive integers *a*, *b*, *c*, *d* with *a* < *b* and *c* < *d*, then *a*⁄*b* and *c*⁄*d* will be neighbours in the Farey sequence of order max(*b,d*).

If *p*⁄*q* has neighbours *a*⁄*b* and *c*⁄*d* in some Farey sequence, with *a*⁄*b* < *p*⁄*q* < *c*⁄*d*, then *p*⁄*q* is the [mediant](/source/Mediant_(mathematics)) of *a*⁄*b* and *c*⁄*d* – in other words,

\frac{p}{q} = \frac{a + c}{b + d}.

This follows easily from the previous property, since if

\begin{align}
  && bp - aq &= qc - pd = 1, \\[4pt]
  \implies && bp + pd &= qc + aq, \\[4pt]
  \implies && p(b + d) &= q(a + c), \\
  \implies && \frac{p}{q} &= \frac{a+c}{b+d}.
\end{align}

It follows that if *a*⁄*b* and *c*⁄*d* are neighbours in a Farey sequence then the first term that appears between them as the order of the Farey sequence is incremented is

\frac{a+c}{b+d},

which first appears in the Farey sequence of order *b* + *d*.

Thus the first term to appear between 1⁄3 and 2⁄5 is 3⁄8, which appears in *F*8.

The total number of Farey neighbour pairs in Fn is 2 − 3.

The *[Stern–Brocot tree](/source/Stern%E2%80%93Brocot_tree)* is a [data structure](/source/Data_structure) showing how the sequence is built up from 0 and 1 , by taking successive mediants. Note, however, that at the *n*th step of the construction of the Stern–Brocot tree all mediants are included, not only the ones with denominator equal to *n*.

#### Equivalent-area interpretation

Every consecutive pair of Farey rationals have an equivalent area of 1.[10] See this by interpreting consecutive rationals

r_1 = \frac{p}{q} \qquad r_2 = \frac{p'}{q'}

as vectors (*p*, *q*) in the xy-plane. The area is given by

A \left(\frac{p}{q}, \frac{p'}{q'} \right) = qp' - q'p.

As any added fraction in between two previous consecutive Farey sequence fractions is calculated as the [mediant](/source/Mediant_(mathematics)) (⊕), then

\begin{align}
  A(r_1, r_1 \oplus r_2) &= A(r_1, r_1) + A(r_1, r_2) \\
  &= A(r_1, r_2) \\
  &= 1
\end{align}

(since *r*1 = 1⁄0 and *r*2 = 0⁄1, its area must be 1).

### Farey neighbours and continued fractions

Fractions that appear as neighbours in a Farey sequence have closely related [continued fraction](/source/Continued_fraction) expansions. Every fraction has two continued fraction expansions — in one the final term is 1; in the other the final term is greater by 1. If *p*⁄*q*, which first appears in Farey sequence Fq, has the [continued fraction expansions](/source/Simple_continued_fraction)

\begin{align}
  &[0;\ a_1,\ a_2,\ \ldots,\ a_{n-1},\ a_n,\ 1] \\{}
  &[0;\ a_1,\ a_2,\ \ldots,\ a_{n-1},\ a_n + 1]
\end{align}

then the nearest neighbour of *p*⁄*q* in Fq (which will be its neighbour with the larger denominator) has a continued fraction expansion

[0;\ a_1,\ a_2,\ \ldots,\ a_n]

and its other neighbour has a continued fraction expansion

[0;\ a_1,\ a_2,\ \ldots,\ a_{n-1}]

For example, 3⁄8 has the two continued fraction expansions [0; 2, 1, 1, 1] and [0; 2, 1, 2], and its neighbours in *F*8 are 2⁄5, which can be expanded as [0; 2, 1, 1]; and 1⁄3, which can be expanded as [0; 2, 1].

### Farey fractions and the least common multiple

The [lcm](/source/Least_common_multiple) can be expressed as the products of Farey fractions as

\text{lcm}[1,2,...,N] = e^{\psi(N)} = \frac{1}{2} \left( \prod_{r \in F_N, 0<r \le 1/2} 2 \sin(\pi r) \right)^2

where *ψ*(*N*) is the second [Chebyshev function](/source/Chebyshev_function).[11][12]

### Farey fractions and the greatest common divisor

Since the [Euler's totient function](/source/Euler's_totient_function) is directly connected to the [gcd](/source/Greatest_common_divisor) so is the number of elements in Fn,

|F_n| = 1 + \sum_{m=1}^n \varphi(m) = 1+ \sum\limits_{m=1}^{n} \sum\limits_{k=1}^m \gcd(k,m) \cos {2\pi\frac{k}{m}} .

For any 3 Farey fractions *a*⁄*b*, *c*⁄*d*, *e*⁄*f* the following identity between the [gcd](/source/Greatest_common_divisor)'s of the 2×2 [matrix determinants](/source/Matrix_determinant) in [absolute value](/source/Absolute_value) holds:[13][7]

\gcd\left(\begin{Vmatrix} a & c\\b & d \end{Vmatrix}, \begin{Vmatrix} a & e\\b & f \end{Vmatrix} \right)
  = \gcd\left(\begin{Vmatrix} a & c\\b & d \end{Vmatrix}, \begin{Vmatrix} c & e\\d & f \end{Vmatrix} \right)
  = \gcd\left(\begin{Vmatrix} a & e\\b & f \end{Vmatrix}, \begin{Vmatrix} c & e\\d & f \end{Vmatrix} \right)

### Applications

Farey sequences are very useful to find rational approximations of [irrational numbers](/source/Irrational_number).[14] For example, the construction by Eliahou[15] of a lower bound on the length of non-trivial cycles in the [3*x*+1 process](/source/Collatz_conjecture#Cycles) uses Farey sequences to calculate a continued fraction expansion of the number log2(3).

In physical systems with resonance phenomena, Farey sequences provide a very elegant and efficient method to compute resonance locations in 1D[16] and 2D.[17][18]

Farey sequences are prominent in studies of [any-angle path planning](/source/Any-angle_path_planning) on square-celled grids, for example in characterizing their computational complexity[19] or optimality.[20] The connection can be considered in terms of r-constrained paths, namely paths made up of line segments that each traverse at most r rows and at most r columns of cells. Let Q be the set of vectors (*q*, *p*) such that 1 \leq q \leq r, 0 \leq p \leq q, and p, q are coprime. Let Q* be the result of reflecting Q in the line *y* = *x*. Let S = \{ (\pm x, \pm y) : (x, y) \in Q \cup Q* \}. Then any r-constrained path can be described as a sequence of vectors from S. There is a [bijection](/source/Bijection) between Q and the Farey sequence of order r given by (*q*, *p*) mapping to \tfrac{p}{q}.

### Ford circles

There is a connection between Farey sequence and [Ford circles](/source/Ford_circle).

For every fraction *p*⁄*q* (in its lowest terms) there is a Ford circle *C*[*p*/*q*], which is the circle with radius \tfrac{1}{2q^2} and centre at \bigl(\tfrac{p}{q}, \tfrac{1}{2q^2}\bigr). Two Ford circles for different fractions are either [disjoint](/source/Disjoint_sets) or they are [tangent](/source/Tangent) to one another—two Ford circles never intersect. If 0 < *p*⁄*q* < 1 then the Ford circles that are tangent to *C*[*p*/*q*] are precisely the Ford circles for fractions that are neighbours of *p*⁄*q* in some Farey sequence.

Thus *C*[2/5] is tangent to *C*[1/2], *C*[1/3], *C*[3/7], *C*[3/8], etc.

Ford circles appear also in the [Apollonian gasket](/source/Apollonian_gasket) (0,0,1,1). The picture below illustrates this together with Farey resonance lines.[21]

### Riemann hypothesis

Farey sequences are used in two equivalent formulations of the [Riemann hypothesis](/source/Riemann_hypothesis). Suppose the terms of Fn are \{a_{k,n} : k = 0, 1, \ldots, m_n\}. Define d_{k,n} = a_{k,n} - \tfrac{k}{m_n}, in other words d_{k,n} is the difference between the kth term of the nth Farey sequence, and the kth member of a set of the same number of points, distributed evenly on the [unit interval](/source/Unit_interval). In 1924 [Jérôme Franel](/source/J%C3%A9r%C3%B4me_Franel)[22] proved that the statement

\sum_{k=1}^{m_n} d_{k,n}^2 = O (n^r) \quad \forall r > -1

is equivalent to the Riemann hypothesis, and then [Edmund Landau](/source/Edmund_Landau)[23] remarked (just after Franel's paper) that the statement

\sum_{k=1}^{m_n} |d_{k,n}| = O (n^r) \quad \forall r > \frac{1}{2}

is also equivalent to the Riemann hypothesis.

### Other sums involving Farey fractions

The sum of all Farey fractions of order n is half the number of elements:

\sum_{r\in F_n} r = \frac{1}{2} |F_n| .

The sum of the denominators in the Farey sequence is twice the sum of the numerators and relates to Euler's totient function:

\sum_{a/b \in F_n} b = 2 \sum_{a/b \in F_n} a = 1 + \sum_{i=1}^{n} i\varphi(i) ,

which was conjectured by Harold L. Aaron in 1962 and demonstrated by Jean A. Blake in 1966.[24] A one line proof of the Harold L. Aaron conjecture is as follows. The sum of the numerators is

1 + \sum_{2 \le b \le n} \ \sum_{(a,b)=1} a = 1 + \sum_{2 \le b \le n} b\frac{\varphi(b)}{2}.

The sum of denominators is

2 + \sum_{2 \le b \le n} \ \sum_{(a,b)=1} b  = 2 + \sum_{2 \le b \le n} b\varphi(b).

The quotient of the first sum by the second sum is 1⁄2.

Let bj be the ordered denominators of Fn, then:[25]

\sum_{j=0}^{|F_n|-1} \frac{b_j}{b_{j+1}} = \frac{3|F_n|-4}{2}

and

\sum_{j=0}^{|F_n|-1} \frac{1}{b_{j+1}b_{j}} = 1.

Let \tfrac{a_j}{b_j} the jth Farey fraction in Fn, then

\sum_{j=1}^{|F_n|-1} (a_{j-1}b_{j+1} - a_{j+1}b_{j-1})
  = \sum_{j=1}^{|F_n|-1} \begin{Vmatrix}
    a_{j-1} & a_{j+1} \\
    b_{j-1} & b_{j+1}
    \end{Vmatrix} = 3(|F_n|-1) - 2n - 1,

which is demonstrated in.[26] Also according to this reference the term inside the sum can be expressed in many different ways:

a_{j-1} b_{j+1} - a_{j+1} b_{j-1} = \frac{b_{j-1}+b_{j+1}}{b_{j}} = \frac{a_{j-1}+a_{j+1}}{a_{j}} = \left\lfloor\frac{n+ b_{j-1}}{b_{j}} \right\rfloor,

obtaining thus many different sums over the Farey elements with same result. Using the symmetry around 1/2 the former sum can be limited to half of the sequence as

\sum_{j=1}^{\left\lfloor \frac{|F_n|}{2} \right\rfloor} (a_{j-1} b_{j+1} - a_{j+1} b_{j-1}) = \frac{3(|F_n|-1)}{2} - n - \left\lceil \frac{n}{2} \right\rceil ,

The [Mertens function](/source/Mertens_function) can be expressed as a sum over Farey fractions as

M(n)= -1+ \sum_{a\in \mathcal{F}_n} e^{2\pi i a}

where \mathcal{F}_n is the Farey sequence of order n.

This formula is used in the proof of the [Franel–Landau theorem](#Riemann_hypothesis).[27]

## Next term

A surprisingly simple algorithm exists to generate the terms of *Fn* in either traditional order (ascending) or non-traditional order (descending). The algorithm computes each successive entry in terms of the previous two entries using the mediant property given above. If *a*⁄*b* and *c*⁄*d* are the two given entries, and *p*⁄*q* is the unknown next entry, then *c*⁄*d* = *a* + *p*⁄*b* + *q*. Since *c*⁄*d* is in lowest terms, there must be an integer *k* such that *kc* = *a* + *p* and *kd* = *b* + *q*, giving *p* = *kc* − *a* and *q* = *kd* − *b*. If we consider *p* and *q* to be functions of *k*, then

- \frac{p(k)}{q(k)}- \frac{c}{d} = \frac{cb - da}{d(kd - b)}

so the larger *k* gets, the closer *p*⁄*q* gets to *c*⁄*d*.

To give the next term in the sequence *k* must be as large as possible, subject to *kd* − *b* ≤ *n* (as we are only considering numbers with denominators not greater than *n*), so *k* is the greatest integer ≤ *n* + *b*⁄*d*. Putting this value of *k* back into the equations for *p* and *q* gives

- p = \left\lfloor\frac{n+b}{d}\right\rfloor c - a
- q = \left\lfloor\frac{n+b}{d}\right\rfloor d - b

This is implemented in [Python](/source/Python_(programming_language)) as follows:

from fractions import Fraction
from collections.abc import Generator

def farey_sequence(n: int, descending: bool = False) -> Generator[Fraction]:
    """
    Print the n'th Farey sequence. Allow for either ascending or descending.

    >>> print(*farey_sequence(5), sep=' ')
    0 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1
    """
    a, b, c, d = 0, 1, 1, n
    if descending:
        a, c = 1, n - 1
    yield Fraction(a, b)
    while 0 <= c <= n:
        k = (n + b) // d
        a, b, c, d = c, d, k * c - a, k * d - b
        yield Fraction(a, b)

Brute-force searches for solutions to [Diophantine equations](/source/Diophantine_equation) in rationals can often take advantage of the Farey series (to search only reduced forms). While this code uses the first two terms of the sequence to initialize *a*, *b*, *c*, and *d*, one could substitute any pair of adjacent terms in order to exclude those less than (or greater than) a particular threshold.[28]

## See also

- [ABACABA pattern](/source/ABACABA_pattern)
- [Stern–Brocot tree](/source/Stern%E2%80%93Brocot_tree)
- [Euler's totient function](/source/Euler's_totient_function)
- [Calkin–Wilf tree](/source/Calkin%E2%80%93Wilf_tree)

## Footnotes

1. “*The sequence of all reduced fractions with denominators not exceeding n, listed in order of their size, is called the Farey sequence of order n.*” With the comment: “*This definition of the Farey sequences seems to be the most convenient. However, some authors prefer to restrict the fractions to the interval from 0 to 1.*” — Niven & Zuckerman (1972)[29]

## References

1. Guthery, Scott B. (2011). ["1. The Mediant"](https://books.google.com/books?id=swb2c9enRJcC&pg=PA7). *A Motif of Mathematics: History and Application of the Mediant and the Farey Sequence*. Boston: Docent Press. p. 7. ISBN 978-1-4538-1057-6. [OCLC 1031694495](https://www.worldcat.org/oclc/1031694495). Retrieved 28 September 2020.

1. Hardy, G.H. & Wright, E.M. (1979). [*An Introduction to the Theory of Numbers*](https://archive.org/details/introductiontoth00hard/page/). Fifth ed. Oxford University Press. [Chapter III](https://archive.org/details/introductiontoth00hard/page/). ISBN 0-19-853171-0.

1. Beiler, Albert H. (1964). *Recreations in the Theory of Numbers*. Second ed. Dover. Chapter XVI. ISBN 0-486-21096-0. Cited in ["Farey Series, A Story"](http://www.cut-the-knot.org/blue/FareyHistory.shtml). [Cut-the-Knot](/source/Cut-the-Knot)

1. [John Farey Sr.](/source/John_Farey_Sr.) (1816), ["On a curious property of vulgar fractions"](https://archive.org/details/s2id13416200/page/384/mode/2up), *Philosophical Magazine*. **47**: 385–386

1. Tomas Garcia, Rogelio (July 2024). ["Farey Fractions with Equal Numerators and the Rank of Unit Fractions"](https://math.colgate.edu/~integers/y63/y63.pdf). *Integers*. **24**. [arXiv:2404.08283](https://arxiv.org/abs/2404.08283). [doi:10.5281/zenodo.12685697](https://doi.org/10.5281/zenodo.12685697)

1. Tomas, Rogelio (January 2022). ["Partial Franel sums"](https://cs.uwaterloo.ca/journals/JIS/VOL25/Tomas/tomas5.pdf). *Journal of Integer Sequences*. **25** (1)

1. Dress, F. (1999). ["Discrépance des suites de Farey"](http://archive.numdam.org/article/JTNB_1999__11_2_345_0.pdf). *J. Théorie des Nr. Bordx.*. **11**

1. Tomas Garcia, Rogelio (2025). ["New Analytical Formulas for the Rank of Farey Fractions and Estimates of the Local Discrepancy"](https://www.mdpi.com/2227-7390/13/1/140). *Mathematics*. **13** (1): 140. [doi:10.3390/math13010140](https://doi.org/10.3390/math13010140)

1. Austin, David (December 2008). ["Trees, Teeth, and Time: The mathematics of clock making"](http://www.ams.org/publicoutreach/feature-column/fcarc-stern-brocot). *[American Mathematical Society](/source/American_Mathematical_Society)*. [Archived](https://web.archive.org/web/20200204014725/http://www.ams.org/publicoutreach/feature-column/fcarc-stern-brocot) 4 February 2020 at the Wayback Machine. Retrieved 28 September 2020.

1. Martin, Greg (2009). "A product of Gamma function values at fractions with the same denominator". [arXiv:0907.4384](https://arxiv.org/abs/0907.4384)

1. Wehmeier, Stefan (2009). "The LCM(1,2,...,n) as a product of sine values sampled over the points in Farey sequences". [arXiv:0909.1838](https://arxiv.org/abs/0909.1838)

1. Tomas Garcia, Rogelio (August 2020). ["Equalities between greatest common divisors involving three coprime pairs"](http://rtomas.web.cern.ch/rtomas/NNTDM-26-3-005-007.pdf). *Notes on Number Theory and Discrete Mathematics*. **26** (3): 5–7. [doi:10.7546/nntdm.2020.26.3.5-7](https://doi.org/10.7546/nntdm.2020.26.3.5-7). [S2CID 225280271](https://api.semanticscholar.org/CorpusID:225280271)

1. ["Farey Approximation"](https://web.archive.org/web/20181119092100/https://nrich.maths.org/6596). *NRICH.maths.org*. Archived from [the original](https://nrich.maths.org/6596) on 19 November 2018. Retrieved 18 November 2018.

1. Eliahou, Shalom (August 1993). "The 3x+1 problem: new lower bounds on nontrivial cycle lengths". *Discrete Mathematics*. **118** (1–3): 45–56. [doi:10.1016/0012-365X(93)90052-U](https://doi.org/10.1016/0012-365X(93)90052-U)

1. Zhenhua Li, A. & Harter, W.G. (2015). "Quantum Revivals of Morse Oscillators and Farey–Ford Geometry". *Chem. Phys. Lett.*. **633**: 208–213. [arXiv:1308.4470](https://arxiv.org/abs/1308.4470). [Bibcode:2015CPL...633..208L](https://ui.adsabs.harvard.edu/abs/2015CPL...633..208L). [doi:10.1016/j.cplett.2015.05.035](https://doi.org/10.1016/j.cplett.2015.05.035). [S2CID 66213897](https://api.semanticscholar.org/CorpusID:66213897)

1. Tomas, R. (2014). ["From Farey sequences to resonance diagrams"](http://cds.cern.ch/record/2135825/files/10.1103_PhysRevSTAB.17.014001.pdf). *Physical Review Special Topics - Accelerators and Beams*. **17** (1). [Bibcode:2014PhRvS..17a4001T](https://ui.adsabs.harvard.edu/abs/2014PhRvS..17a4001T). [doi:10.1103/PhysRevSTAB.17.014001](https://doi.org/10.1103/PhysRevSTAB.17.014001)

1. Tomas Garcia, Rogelio (2025). ["Resonance gaps, discrepancies, and lines"](https://journals.aps.org/prab/pdf/10.1103/2gfw-xckn). *Physical Review Accelerators and Beams*. **17** (1). [doi:10.1103/2gfw-xckn](https://doi.org/10.1103/2gfw-xckn)

1. Harabor, Daniel Damir; Grastien, Alban; Öz, Dindar; Aksakalli, Vural (26 May 2016). "Optimal Any-Angle Pathfinding In Practice". *Journal of Artificial Intelligence Research*. **56**: 89–118. [doi:10.1613/jair.5007](https://doi.org/10.1613/jair.5007)

1. Hew, Patrick Chisan (19 August 2017). "The Length of Shortest Vertex Paths in Binary Occupancy Grids Compared to Shortest *r*-Constrained Ones". *Journal of Artificial Intelligence Research*. **59**: 543–563. [doi:10.1613/jair.5442](https://doi.org/10.1613/jair.5442)

1. Tomas, Rogelio (2020). "Imperfections and corrections". [arXiv:2006.10661](https://arxiv.org/abs/2006.10661)

1. Franel, Jérôme (1924). ["Les suites de Farey et le problème des nombres premiers"](http://www.digizeitschriften.de/dms/resolveppn/?PID=GDZPPN00250653X) (in French). *Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen*. Mathematisch-Physikalische Klasse.

1. Landau, Edmund (1924). ["Bemerkungen zu der vorstehenden Abhandlung von Herrn Franel"](http://www.digizeitschriften.de/dms/resolveppn/?PID=GDZPPN002506548) (in German). *Nachrichten von der Gesellschaft der Wissenschaften zu Göttingen*. Mathematisch-Physikalische Klasse.

1. Blake, Jean A. (1966). "Some Characteristic Properties of the Farey Series". *The American Mathematical Monthly*. **73** (1): 50–52. [doi:10.2307/2313922](https://doi.org/10.2307/2313922). [JSTOR 2313922](https://www.jstor.org/stable/2313922)

1. Kurt Girstmair & Girstmair, Kurt (2010). "Farey Sums and Dedekind Sums". *The American Mathematical Monthly*. **117** (1): 72–78. [doi:10.4169/000298910X475005](https://doi.org/10.4169/000298910X475005). [JSTOR 10.4169/000298910X475005](https://www.jstor.org/stable/10.4169%2F000298910X475005). [S2CID 31933470](https://api.semanticscholar.org/CorpusID:31933470)

1. Hall, R. R. & Shiu, P. (2003). "The Index of a Farey Sequence". *Michigan Math. J.*. **51** (1): 209–223. [doi:10.1307/mmj/1049832901](https://doi.org/10.1307/mmj/1049832901)

1. Edwards, Harold M. (1974). ["12.2 Miscellany. The Riemann Hypothesis and Farey Series"](https://archive.org/details/riemannszetafunc00edwa_0/page/262). *Riemann's Zeta Function*. Pure and Applied Mathematics. New York: [Academic Press](/source/Academic_Press). pp. 263–267. ISBN 978-0-08-087373-2. [OCLC 316553016](https://www.worldcat.org/oclc/316553016). Retrieved 30 September 2020.

1. Routledge, Norman (March 2008). "Computing Farey series". *[The Mathematical Gazette](/source/The_Mathematical_Gazette)*. Vol. 92, no. 523. pp. 55–62.

1. Niven, Ivan M. & Zuckerman, Herbert S. (1972). *An Introduction to the Theory of Numbers*. Third ed. John Wiley and Sons. Definition 6.1.

## Further reading

- Hatcher, Allen (2022), *Topology of Numbers*, Providence, RI: [American Mathematical Society](/source/American_Mathematical_Society), ISBN 978-1470456115
- Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1989). *Concrete Mathematics: A foundation for computer science*. 2nd ed. Boston, MA: Addison-Wesley. pp. 115–123, 133–139, 150, 462–463, 523–524. ISBN 0-201-55802-5. — in particular, see §4.5 (pp. 115–123), Bonus Problem 4.61 (pp. 150, 523–524), §4.9 (pp. 133–139), §9.3, Problem 9.3.6 (pp. 462–463).
- Vepstas, Linas. ["The Minkowski Question Mark, GL(2,Z), and the Modular Group"](http://linas.org/math/chap-minkowski.pdf) — reviews the isomorphisms of the Stern-Brocot Tree.
- Vepstas, Linas. ["Symmetries of Period-Doubling Maps"](http://linas.org/math/chap-takagi.pdf) — reviews connections between Farey Fractions and Fractals.
- Cobeli, Cristian & Zaharescu, Alexandru (2003). "The Haros–Farey sequence at two hundred years. A survey". *Acta Univ. Apulensis Math. Inform.*. '***(5): 1–38.******["pp. 1–20"](http://www.emis.de/journals/AUA/acta5/survey3.ps_pages1-20.pdf).*Acta Univ. Apulensis*["pp. 21–38"](http://www.emis.de/journals/AUA/acta5/survey3.ps_pages21-38.pdf).*Acta Univ. Apulensis**
- Matveev, Andrey O. (2017). *Farey Sequences: Duality and Maps Between Subsequences*. Berlin, DE: De Gruyter. ISBN 978-3-11-054662-0. [Errata + Code](https://github.com/andreyomatveev/farey-sequences)

## External links

- Hatcher, Allen. ["Topology of Numbers"](https://pi.math.cornell.edu/~hatcher/TN/TNbook1225.pdf) Online copy of book
- Bogomolny, Alexander. ["Farey series"](http://www.cut-the-knot.org/blue/Farey.shtml). [Cut-the-Knot](/source/Cut-the-Knot)
- Bogomolny, Alexander. ["Stern-Brocot Tree"](http://www.cut-the-knot.org/blue/Stern.shtml). [Cut-the-Knot](/source/Cut-the-Knot)
- Pennestri, Ettore. ["A Brocot table of base 120"](https://www.researchgate.net/publication/297000899)
- Archived at [Ghostarchive](https://ghostarchive.org/varchive/youtube/20211212/0hlvhQZIOQw) and the [Wayback Machine](https://web.archive.org/web/20181007135618/https://www.youtube.com/watch?bpctr=9999999999&hl=en&disable_polymer=true&gl=US&v=0hlvhQZIOQw&has_verified=1): Bonahon, Francis. [*Funny Fractions and Ford Circles*](https://www.youtube.com/watch?v=0hlvhQZIOQw) (video). [Brady Haran](/source/Brady_Haran). Retrieved 9 June 2015. – via YouTube.

---
Adapted from the Wikipedia article [Farey sequence](https://en.wikipedia.org/wiki/Farey_sequence) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Farey_sequence?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.