Farey sequence

Plotting F₆ numerators vs denominators

Starbursts of iterations 1–10 superimposed

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

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 grid points from the origin in the square of side 2n, centered at the origin. Using Pick's theorem, the area of the sunburst is 4(|F_n|−1), where |F_n| is the number of fractions in F_n.

Farey sunburst of order 6, with 1 interior (red) and 96 boundary (green) points giving an area of 1 + 96/2 − 1 = 48, according to Pick's theorem

The Farey sequence of order n contains all of the members of the Farey sequences of lower orders. In particular F_n 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 to n. Thus F₆ consists of F₅ together with the fractions 1/6 and 5/6.

The middle term of a Farey sequence F_n is always 1/2, for n > 1. From this, we can relate the lengths of F_n and F_n−1 using Euler's totient function ${\displaystyle \varphi (n)}$ :

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

Using the fact that |F₁| = 2, we can derive an expression for the length of F_n:[5]

${\displaystyle |F_{n}|=1+\sum _{m=1}^{n}\varphi (m)=1+\Phi (n),}$

where ${\displaystyle \Phi (n)}$ is the summatory totient.

We also have :

${\displaystyle |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 :

${\displaystyle |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, and ${\displaystyle \lfloor {\tfrac {n}{d}}\rfloor }$ is the floor function.

The asymptotic behaviour of |F_n| is :

${\displaystyle |F_{n}|\sim {\frac {3n^{2}}{\pi ^{2}}}.}$

The index ${\displaystyle I_{n}(a_{k,n})=k}$ of a fraction ${\displaystyle a_{k,n}}$ in the Farey sequence ${\displaystyle F_{n}=\{a_{k,n}:k=0,1,\ldots ,m_{n}\}}$ is simply the position that ${\displaystyle a_{k,n}}$ occupies in the sequence. This is of special relevance as it is used in an alternative formulation of the Riemann hypothesis, see below. Various useful properties follow:

${\displaystyle I_{n}(0/1)=0,}$

${\displaystyle I_{n}(1/n)=1,}$

${\displaystyle I_{n}(1/2)=(|F_{n}|-1)/2,}$

${\displaystyle I_{n}(1/1)=|F_{n}|-1,}$

${\displaystyle I_{n}(h/k)=|F_{n}|-1-I_{n}((k-h)/k).}$

The index of ${\displaystyle 1/k}$ where ${\displaystyle n/(i+1)<k\leq n/i}$ and ${\displaystyle n}$ is the least common multiple of the first ${\displaystyle i}$ numbers, ${\displaystyle n={\rm {lcm}}([2,i])}$, is given by:[6]

${\displaystyle I_{n}(1/k)=1+n\sum _{j=1}^{i}{\frac {\varphi (j)}{j}}-k\Phi (i).}$

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

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

this is equivalent to saying that

${\displaystyle bc-ad=1}$.

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

The converse is also true. If

${\displaystyle bc-ad=1}$

for positive integers a,b,c and 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

${\displaystyle {\frac {a}{b}}<{\frac {p}{q}}<{\frac {c}{d}}}$

then p/q is the mediant of a/b and c/d – in other words,

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

This follows easily from the previous property, since if bp – aq = qc – pd = 1, then bp + pd = qc + aq, p(b + d) = q(a + c), p/q = a + c/b + d.

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

${\displaystyle {\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₈.

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

The Stern–Brocot tree is a data structure showing how the sequence is built up from 0 (= 0/1) and 1 (= 1/1), by taking successive mediants.

Every consecutive pair of Farey rationals have an equivalent area of 1.[7] See this by interpreting consecutive rationals r₁ = p/q and r₂ = p′/q′ as vectors (p, q) in the x–y plane. The area of A(p/q, p′/q′) is given by qp′ − q′p. As any added fraction in between two previous consecutive Farey sequence fractions is calculated as the mediant (⊕), then A(r₁, r₁ ⊕ r₂) = A(r₁, r₁) + A(r₁, r₂) = A(r₁, r₂) = 1 (since r₁ = 1/0 and r₂ = 0/1, its area must be 1).

Fractions that appear as neighbours in a Farey sequence have closely related 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 F_q, has continued fraction expansions

[0; a₁, a₂, ..., a_{n − 1}, a_n, 1]

[0; a₁, a₂, ..., a_{n − 1}, a_n + 1]

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

[0; a₁, a₂, ..., a_n]

and its other neighbour has a continued fraction expansion

[0; a₁, a₂, ..., 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₈ are 2/5, which can be expanded as [0; 2, 1, 1]; and 1/3, which can be expanded as [0; 2, 1].

The lcm can be expressed as the products of Farey fractions as

${\displaystyle {\text{lcm}}[1,2,...,N]=e^{\psi (N)}={\frac {1}{2}}\left(\prod _{r\in F_{N},0<r\leq 1/2}2\sin(\pi r)\right)^{2}}$

where ${\displaystyle \psi (N)}$ is the second Chebyshev function.[8][9]

Since the Euler's totient function is directly connected to the gcd so is the number of elements in F_n,

${\displaystyle |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 and e/f the following identity between the gcd's of the 2x2 matrix determinants in absolute value holds:[10]

${\displaystyle \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)}$

[6]

Farey sequences are very useful to find rational approximations of irrational numbers.[11] For example, the construction by Eliahou[12] of a lower bound on the length of non-trivial cycles in the 3x+1 process uses Farey sequences to calculate a continued fraction expansion of the number log₂(3).

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

Farey sequences are prominent in studies of any-angle path planning on square-celled grids, for example in characterizing their computational complexity[15] or optimality.[16] The connection can be considered in terms of r-constrained paths, namely paths made up of line segments that each traverse at most ${\displaystyle r}$ rows and at most ${\displaystyle r}$ columns of cells. Let ${\displaystyle Q}$ be the set of vectors ${\displaystyle (q,p)}$ such that ${\displaystyle 1\leq q\leq r}$, ${\displaystyle 0\leq p\leq q}$, and ${\displaystyle p}$, ${\displaystyle q}$ are coprime. Let ${\displaystyle Q*}$ be the result of reflecting ${\displaystyle Q}$ in the line ${\displaystyle y=x}$. Let ${\displaystyle 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 ${\displaystyle S}$. There is a bijection between ${\displaystyle Q}$ and the Farey sequence of order ${\displaystyle r}$ given by ${\displaystyle (q,p)}$ mapping to ${\displaystyle {\tfrac {p}{q}}}$.

Comparison of Ford circles and a Farey diagram with circular arcs for n from 1 to 9. Each arc intersects its corresponding circles at right angles. In the SVG image, hover over a circle or curve to highlight it and its terms.

There is a connection between Farey sequence and Ford circles.

For every fraction p/q (in its lowest terms) there is a Ford circle C[p/q], which is the circle with radius 1/(2q²) and centre at (p/q, 1/ 2q² ). Two Ford circles for different fractions are either disjoint or they are 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 (0,0,1,1). The picture below illustrates this together with Farey resonance lines.[17]

Apollonian gasket (0,0,1,1) and the Farey resonance diagram.

Farey sequences are used in two equivalent formulations of the Riemann hypothesis. Suppose the terms of ${\displaystyle F_{n}}$ are ${\displaystyle \{a_{k,n}:k=0,1,\ldots ,m_{n}\}}$. Define ${\displaystyle d_{k,n}=a_{k,n}-k/m_{n}}$, in other words ${\displaystyle 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. In 1924 Jérôme Franel[18] proved that the statement

${\displaystyle \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[19] remarked (just after Franel's paper) that the statement

${\displaystyle \sum _{k=1}^{m_{n}}|d_{k,n}|=O(n^{r})\quad \forall r>1/2}$

is also equivalent to the Riemann hypothesis.

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

${\displaystyle \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:

${\displaystyle \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.[20] A one line proof of the Harold L. Aaron conjecture is as follows. The sum of the numerators is ${\displaystyle {\displaystyle 1+\sum _{2\leq b\leq n}\sum _{(a,b)=1}a=1+\sum _{2\leq b\leq n}b{\frac {\varphi (b)}{2}}}}$. The sum of denominators is ${\displaystyle {\displaystyle 2+\sum _{2\leq b\leq n}\sum _{(a,b)=1}b=2+\sum _{2\leq b\leq n}b\varphi (b)}}$. The quotient of the first sum by the second sum is ${\displaystyle {\frac {1}{2}}}$.

Let b_j be the ordered denominators of F_n, then:[21]

${\displaystyle \sum _{j=0}^{|F_{n}|-1}{\frac {b_{j}}{b_{j+1}}}={\frac {3|F_{n}|-4}{2}}}$

and

${\displaystyle \sum _{j=0}^{|F_{n}|-1}{\frac {1}{b_{j+1}b_{j}}}=1.}$

Let a_j/b_j the jth Farey fraction in F_n, then

${\displaystyle \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.[22] Also according to this reference the term inside the sum can be expressed in many different ways:

${\displaystyle 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

${\displaystyle \sum _{j=1}^{\lfloor |F_{n}|/2\rfloor }(a_{j-1}b_{j+1}-a_{j+1}b_{j-1})=3(|F_{n}|-1)/2-n-\lceil n/2\rceil ,}$

The Mertens function can be expressed as a sum over Farey fractions as

${\displaystyle M(n)=-1+\sum _{a\in {\mathcal {F}}_{n}}e^{2\pi ia}}$   where   ${\displaystyle {\mathcal {F}}_{n}}$   is the Farey sequence of order n.

This formula is used in the proof of the Franel–Landau theorem.[23]