Farey sequence
In mathematics, the Farey sequence of order n is the sequence of completely reduced fractions, either between 0 and 1, or without this restriction,[a] which when in lowest terms have denominators 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).
Reflecting this shape around the diagonal and main axes generates the Farey sunburst, shown below.
Using Pick's theorem, the area of the sunburst is 4(|Fn| − 1), where |Fn| is the number of fractions in Fn.
In fact, another mathematician, Charles Haros, had published similar results in 1802 which were not known either to Farey or to Cauchy.
From this, we can relate the lengths of Fn and Fn−1 using Euler's totient function φ(n):
The number of Farey fractions with denominators equal to k in Fn is given by φ(k) when k ≤ n and zero otherwise.
that returns the number of Farey fractions with numerators equal to h in Fn.
This is of special relevance as it is used in an alternative formulation of the Riemann hypothesis, see below.
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).
The total number of Farey neighbour pairs in Fn is 2|Fn| − 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.
If p/q, which first appears in Farey sequence Fq, has the continued fraction expansions
[12][13] Since the Euler's totient function is directly connected to the gcd so is the number of elements in Fn,
For any 3 Farey fractions a/b, c/d, e/f the following identity between the gcd's of the 2x2 matrix determinants in absolute value holds:[14]
[8] Farey sequences are very useful to find rational approximations of irrational numbers.
[15] For example, the construction by Eliahou[16] 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 log2(3).
[18] Farey sequences are prominent in studies of any-angle path planning on square-celled grids, for example in characterizing their computational complexity[19] or optimality.
[21] Farey sequences are used in two equivalent formulations of the Riemann hypothesis.
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.
is equivalent to the Riemann hypothesis, and then Edmund Landau[23] remarked (just after Franel's paper) that the statement
The sum of all Farey fractions of order n is half the number of elements:
which was conjectured by Harold L. Aaron in 1962 and demonstrated by Jean A. Blake in 1966.
[26] Also according to this reference the term inside the sum can be expressed in many different ways:
obtaining thus many different sums over the Farey elements with same result.
The Mertens function can be expressed as a sum over Farey fractions as
is the Farey sequence of order n. This formula is used in the proof of the Franel–Landau theorem.
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 This is implemented in Python as follows: Brute-force searches for solutions to Diophantine equations in rationals can often take advantage of the Farey series (to search only reduced forms).
