Farey sequence
A Farey sequence of order n, denoted F_n, is the ordered sequence of all reduced fractions between 0 and 1 (inclusive) with denominators at most n, arranged in increasing order.[1] For example, F_1 = \frac{0}{1}, \frac{1}{1}, F_2 = \frac{0}{1}, \frac{1}{2}, \frac{1}{1}, and F_3 = \frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1}.[2] The concept was first systematically described by French mathematician Charles Haros in 1802, though it gained prominence through English geologist John Farey Sr., who published tables of such sequences in 1816 without crediting Haros.[1] That same year, Augustin Cauchy provided a rigorous proof of key properties, including the mediant rule for generating higher-order sequences.[3] Earlier roots trace to a 1747 problem in The Ladies' Diary, solved in 1751 by Thomas Flitcroft, who computed the number of fractions strictly between 0 and 1 with denominators at most 99 as 3003.[3] Central properties include the adjacency condition: for two consecutive fractions \frac{a}{b} and \frac{c}{d} in F_n, bc - ad = 1, ensuring they are "Farey neighbors."[2] The mediant \frac{a+c}{b+d} of such neighbors is the first new fraction to appear between them in F_{b+d}, and it is already in lowest terms.[1] The number of terms in F_n is given by |F_n| = 1 + \sum_{k=1}^n \phi(k), where \phi is Euler's totient function, with asymptotic growth |F_n| \sim \frac{3n^2}{\pi^2}.[3] Sequences can be generated recursively by inserting mediants into F_{n-1} for denominators up to n.[1] Farey sequences find applications in Diophantine approximation, where they identify best rational approximations to irrationals, such as Dirichlet's theorem that for any real \xi, there are infinitely many \frac{a}{b} with |\xi - \frac{a}{b}| < \frac{1}{b^2}.[1] They connect to Ford circles, which visualize tangencies corresponding to adjacency, and to the Stern-Brocot tree for enumerating positives rationals.[2] Advanced uses include links to the Riemann Hypothesis via the Franel-Landau theorem on discrepancies in Farey fractions, and practical roles in gear ratios for clock-making.[3]Definition and Examples
Definition
A Farey sequence of order n, denoted F_n, is the sequence of all completely reduced fractions between 0 and 1, inclusive, whose denominators are at most n, arranged in order of increasing value.[4] A fraction a/b is completely reduced if \gcd(a, b) = 1, with $0 \leq a \leq b \leq n and b > 0.[5] This includes the boundary fractions $0/1 and $1/1.[6] Formally, F_n = \left\{ \frac{h}{k} \;\middle|\; 0 \leq h \leq k \leq n,\ \gcd(h,k)=1 \right\}, where the elements are sorted by their numerical value.[4] Farey sequences arise in the study of Diophantine approximation, providing a systematic way to enumerate rational approximations to real numbers with bounded denominators.[7]Examples
The Farey sequence of order 1, denoted F_1, consists of the fractions \frac{0}{1} and \frac{1}{1}. For order 2, F_2 includes \frac{0}{1}, \frac{1}{2}, \frac{1}{1}. The sequence for order 3 is F_3 = \left\{ \frac{0}{1}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{1}{1} \right\}. Order 4 yields F_4 = \left\{ \frac{0}{1}, \frac{1}{4}, \frac{1}{3}, \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{1}{1} \right\}. Finally, for order 5, F_5 = \left\{ \frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1} \right\}. These examples illustrate that each Farey sequence F_n is a subset of F_{n+1}, with the higher-order sequence formed by inserting additional reduced fractions whose denominators equal n+1 between existing terms of F_n. A radial visualization known as the Farey sunburst represents fractions in F_n as rays emanating from the origin in the plane, where each ray corresponds to the point (q, p) for a fraction \frac{p}{q} (with p a non-negative integer and q a positive integer, coprime, $0 \leq p \leq q \leq n), positioning the rays at angles \theta = \arctan\left( \frac{p}{q} \right).[8] This arrangement highlights the nested structure across orders, as higher-order sunbursts incorporate all rays from lower orders while adding new ones that fill gaps angularly.[8]History
Early Discovery
The Farey sequence was first discovered by the French geometer Charles Haros in 1802. In his publication "Tables pour évaluer une fraction ordinaire avec autant de décimales qu'on voudra ; et pour trouver la fraction ordinaire la plus simple, et qui approche le plus d'une fraction décimale," Haros described a systematic arrangement of irreducible fractions between 0 and 1, ordered by increasing magnitude and limited to denominators up to 99, as a means to identify optimal rational approximations to decimal values.[9] This construction provided a practical tool for converting and simplifying fractions in computational settings.[10] Haros developed these sequences in the context of his work at the Bureau du Cadastre de Paris, where he contributed to the creation of comprehensive logarithmic and trigonometric tables essential for the French land registry project.[11] These tables required precise decimal representations of fractions to support accurate calculations in surveying, engineering, and the emerging metric system, highlighting the applied focus of Haros's approach.[10] This discovery occurred amid a vibrant era in early 19th-century French mathematics, characterized by rapid progress in number theory and approximation theory, driven by the need for reliable numerical methods in scientific and administrative reforms following the Revolution.[10] Haros's sequences exemplified how theoretical insights into rational numbers could address practical challenges in approximation, laying groundwork for later advancements in the field.[9] These ideas were independently rediscovered and further disseminated by John Farey in 1816.[10]Naming and Development
John Farey Sr., a British geologist and land surveyor, popularized the sequences now bearing his name in a 1816 letter published in the Philosophical Magazine under the title "On a curious property of vulgar fractions." In this note, Farey described arrangements of reduced fractions between 0 and 1 with denominators up to a fixed maximum, arranged in increasing order of their values, highlighting their systematic properties without asserting originality and instead soliciting proofs from the mathematical community.[12][3] In August 1816, Augustin Cauchy provided a rigorous proof of the key properties, including the mediant rule for consecutive terms.[3] Farey's engagement with these sequences stemmed from his practical pursuits in geology and surveying, where rational approximations facilitated precise calculations in engineering contexts such as land measurement and mineralogical tabulations.[12][13] Subsequent developments saw increased mathematical scrutiny, with the connection between the sequences' cardinality and Euler's totient function dating back to at least 1751, when Thomas Flitcroft used it to compute the number of terms in F_{99} as 3003, formalizing their role in enumerative number theory. By the mid-20th century, Farey sequences had evolved into a foundational tool in analytic number theory, notably contributing to approximations in the distribution of primes and equivalents to the Riemann hypothesis via the Franel-Landau theorem.[3][14]Fundamental Properties
Sequence Length and Fraction Index
The length of the Farey sequence of order n, denoted |F_n|, counts the total number of distinct irreducible fractions between 0 and 1 (inclusive) with denominators at most n. This cardinality is given by the exact formula |F_n| = 1 + \sum_{k=1}^n \phi(k), where \phi(k) denotes Euler's totient function, which counts the number of positive integers up to k that are coprime to k.[15] The derivation follows from partitioning the fractions by their denominator. The sequence F_n consists of the fraction $0/1 together with all irreducible fractions a/b where $1 \leq b \leq n, $1 \leq a \leq b, and \gcd(a, b) = 1. For each fixed denominator b, the number of such numerators a is precisely \phi(b), since there are \phi(b) integers from 1 to b coprime to b. The term $1/1 is included in the sum for b=1 (where \phi(1) = 1), while the additional 1 accounts for $0/1. Thus, the total length is the stated sum.[15] As n \to \infty, the length admits the asymptotic approximation |F_n| \sim \frac{3n^2}{\pi^2}, with an error term of O(n \log n). This follows directly from the corresponding asymptotic for the partial sum of the totient function, \sum_{k=1}^n \phi(k) \sim \frac{3n^2}{\pi^2}, which arises from the Dirichlet series representation \sum_{k=1}^\infty \phi(k)/k^s = 1/\zeta(s-1) for \Re(s) > 2 and analytic continuation techniques. The index of an irreducible fraction a/b in F_n (with \gcd(a, b) = 1, $0 < a < b \leq n) is defined as its position in the sequence, starting with index 1 for $0/1. Equivalently, the index is $1 plus the number of irreducible fractions p/q \in F_n (with q \leq n) satisfying p/q < a/b. To derive this index, count the qualifying fractions by denominator: for each q = 1 to n, determine the number of numerators p with $0 \leq p \leq q, \gcd(p, q) = 1, and p/q < a/b (i.e., p < q \cdot (a/b)). This count for fixed q is the partial totient sum up to \lfloor q a / b - \epsilon \rfloor, where \epsilon > 0 ensures the strict inequality. Using Möbius inversion to detect coprimality, \sum_{p=1}^m [\gcd(p, q) = 1] = \sum_{d \mid q} \mu(d) \lfloor m / d \rfloor, where \mu is the Möbius function, the index can be expressed as a double sum over denominators and divisors involving floor functions and \mu. Explicit analytical formulas for this index, reducing the computational order through rearrangements of these sums, have been derived using properties of the totient summatory function \Phi(x) = \sum_{j=1}^{\lfloor x \rfloor} \phi(j) and local discrepancy terms.[16] For example, in F_3 = \{0/1, 1/3, 1/2, 2/3, 1/1\}, the fraction $1/2 has index 3, as there are two fractions less than $1/2 ($0/1 and $1/3). Such positions enable efficient indexing without generating the full sequence.[16]Farey Neighbors and Mediants
In a Farey sequence F_n, two consecutive fractions \frac{a}{b} and \frac{c}{d} (with a/b < c/d, both in lowest terms, and denominators at most n) are termed Farey neighbors if they satisfy the condition bc - ad = 1. This determinant condition ensures that no other reduced fraction with denominator at most n lies between them.[17][3] A key property of Farey neighbors is their persistence across higher-order sequences: if \frac{a}{b} and \frac{c}{d} are neighbors in F_n, they remain consecutive (and thus neighbors) in all F_m for m \geq n until the order reaches b + d, at which point they are separated. This stability arises because the condition bc - ad = 1 prevents intermediate fractions from appearing until the mediant is introduced.[3][13] The mediant of two fractions \frac{a}{b} and \frac{c}{d} is defined as \frac{a+c}{b+d}, which always lies strictly between them: \frac{a}{b} < \frac{a+c}{b+d} < \frac{c}{d}. For Farey neighbors satisfying bc - ad = 1, this mediant is the first fraction to appear between them in a higher-order sequence, specifically in F_{b+d}, and it inherits the neighbor relation with each parent: b(a+c) - a(b+d) = 1 and d(a+c) - c(b+d) = 1.[17][13] This neighbor condition is unique to consecutive pairs in any Farey sequence: every pair of adjacent terms in F_n satisfies bc - ad = 1, and conversely, any two reduced fractions with bc - ad = 1 are adjacent in the Farey sequence of order \max(b, d). Moreover, the mediant operation provides a recursive method to generate Farey sequences: starting from F_1 = \{ 0/1, 1/1 \}, higher orders are obtained by inserting the mediant between each pair of neighbors in the previous sequence whenever the sum of their denominators does not exceed the new order.[17][3]Arithmetic Connections
Relation to Continued Fractions
A fundamental link between Farey sequences and continued fractions is encapsulated in the theorem that two reduced fractions \frac{a}{b} and \frac{c}{d} (with a, b, c, d > 0) are Farey neighbors if and only if they appear as consecutive convergents in the continued fraction expansion of some rational number.[18] This equivalence highlights how the structure of Farey sequences captures the hierarchical approximations inherent in continued fractions, where convergents provide optimal rational approximations to real numbers. The connection emerges naturally from the continued fraction algorithm, which generates convergents by iteratively applying the Euclidean algorithm to the numerator and denominator. In this process, successive convergents trace a path through the Farey diagram, with each pair of consecutive convergents (or a convergent and an adjacent semi-convergent) satisfying the neighbor condition |ad - bc| = 1.[19] Semi-convergents, formed as weighted mediants of consecutive convergents (e.g., k \cdot \frac{p_n}{q_n} + \frac{p_{n+1}}{q_{n+1}} for integer k \geq 1), fill intermediate positions and also align with Farey neighbor relations, ensuring that the algorithm's approximations respect the geometry of the Farey tessellation. An important property follows for the mediant of Farey neighbors: the continued fraction expansion of the mediant \frac{a+c}{b+d} alternates between the expansions of \frac{a}{b} and \frac{c}{d} after their shared initial partial quotients. This interleaving reflects the dual approximation roles of the neighbors, with the mediant's expansion combining their tails in an alternating fashion. For example, consider the Farey neighbors \frac{1}{2} = [0; 2] and \frac{1}{1} = [0; 1]. Their mediant is \frac{2}{3} = [0; 1, 2], where the expansion begins with the common prefix [0; ] and then alternates the remaining quotients 1 from \frac{1}{1} and 2 from \frac{1}{2}.[18] This pattern underscores how mediants bridge the approximations provided by continued fractions of neighboring fractions.Links to GCD and LCM
In Farey sequences, the adjacency of two fractions \frac{a}{b} and \frac{c}{d} (with a/b < c/d, both in lowest terms, and denominators at most n) in F_n is characterized by the condition bc - ad = 1 and b + d > n.[20] This implies that the denominators b and d are coprime, i.e., \gcd(b, d) = 1, because any common divisor of b and d would divide bc - ad = 1.[17] The mediant of such adjacent fractions, \frac{a+c}{b+d}, has denominator b + d, which satisfies b + d \geq n + 1, with equality holding precisely when this mediant is the next fraction inserted between them in F_{n+1}.[20] For non-adjacent fractions \frac{a}{b} and \frac{c}{d} in F_n, the quantity k = |bc - ad| > 1 defines the Farey distance, and the number of fractions between them is k - 1; moreover, \gcd(b, d) divides k, generalizing the coprimality condition for neighbors.[17] The least common multiple of the denominators b and d for adjacent pairs follows directly from the coprimality: \operatorname{lcm}(b, d) = bd / \gcd(b, d) = bd.[17] This relation underscores the maximal separation in the arithmetic structure of neighbors. A key identity arises from the differences between adjacent fractions: \frac{c}{d} - \frac{a}{b} = \frac{1}{bd}, so the sum over all adjacent pairs in F_n of $1/(bd) equals 1, as these differences telescope to cover the interval [0, 1].[1]Geometric Interpretations
Ford Circles
Ford circles provide a geometric representation of rational numbers and Farey sequences in the upper half-plane. For a reduced fraction \frac{p}{q} where p and q are coprime positive integers, the corresponding Ford circle is defined as the circle tangent to the x-axis at \left( \frac{p}{q}, 0 \right), with center at \left( \frac{p}{q}, \frac{1}{2q^2} \right) and radius \frac{1}{2q^2}.[21] This construction was introduced by Lester R. Ford in 1938 to visualize the actions of the modular group on families of circles tangent to the real axis at rational points.[21] A key property is that two distinct Ford circles for fractions \frac{a}{b} and \frac{c}{d} (in lowest terms) are tangent if and only if |ad - bc| = 1, which is precisely the condition for \frac{a}{b} and \frac{c}{d} to be neighbors in some Farey sequence; the tangency is internal when they appear consecutively in the same sequence.[21] Moreover, any two Ford circles are either tangent or disjoint, ensuring no overlaps.[22] The Ford circles associated with the fractions in the Farey sequence F_n form a packing in the region above the x-axis up to height \frac{1}{2n^2}, where they touch the x-axis and each other according to the neighbor relations, offering a visual illustration of the sequence's structure.[21]Equivalent-Area Interpretation
In the equivalent-area interpretation of Farey sequences, each reduced fraction \frac{a}{b} between 0 and 1 is associated with the line segment from the origin (0,0) to the lattice point (b, a) in the plane, where the slope of this segment is precisely \frac{a}{b}.[23] Similarly, another fraction \frac{c}{d} corresponds to the segment from (0,0) to (d, c). Two such fractions are neighbors in a Farey sequence if and only if the triangle formed by the points (0,0), (b, a), and (d, c) has an area of exactly \frac{1}{2}.[2] This area condition reflects the primitive nature of the parallelogram spanned by the vectors \overrightarrow{(0,0)(b,a)} = (b, a) and \overrightarrow{(0,0)(d,c)} = (d, c), which has area 1 and contains no other lattice points inside or on its boundary except the vertices.[1] The area of this triangle is given by the formula \frac{1}{2} | b c - a d |, derived from the determinant of the matrix formed by the vectors (b, a) and (d, c).[23] For neighboring fractions, the condition |b c - a d| = [1](/page/1) holds, yielding a triangle area of \frac{1}{2}.[2] This determinant value implies that the vectors (b, a) and (d, c) form a basis for the integer lattice \mathbb{Z}^2, as their parallelogram is the fundamental domain with minimal area, ensuring no intermediate lattice points lie strictly inside the triangle.[1] Geometrically, this basis property guarantees that \frac{a}{b} and \frac{c}{d} are adjacent without any other reduced fraction between them in the relevant Farey sequence.[23] For non-neighboring fractions, the absolute value |b c - a d| > 1, resulting in a triangle area greater than \frac{1}{2}.[2] This larger area corresponds to the presence of intermediate lattice points within the triangle, each of which represents a reduced fraction that lies between \frac{a}{b} and \frac{c}{d} in the Farey sequence.[1] The number of such intermediate fractions is directly related to the value of |b c - a d| - 1, providing a measure of their separation.[23] This interpretation is visualized through the integer lattice, where the triangle's boundary consists of three lattice points (the vertices), and the absence of interior points for neighbors is confirmed via Pick's theorem: the area A = I + \frac{B}{2} - 1, with interior points I = 0 and boundary points B = 3, yielding A = \frac{1}{2}.[2] For larger areas, I > 0, accounting for the enclosed lattice points that correspond to intervening fractions, thus offering a lattice-based geometric proof of Farey neighbor properties.[23]Algorithms and Computations
Generating the Next Term
The Farey sequence of order n, denoted F_n, can be constructed recursively by starting with the initial sequence F_1 = \left\{ \frac{0}{1}, \frac{1}{1} \right\} and iteratively inserting mediants between adjacent fractions.[17] For two neighboring fractions \frac{a}{b} and \frac{c}{d} in F_k (with k \leq n), the mediant \frac{a+c}{b+d} is the next fraction to appear between them, specifically in F_{b+d}, provided b+d \leq n.[17] This property ensures that all irreducible fractions with denominators up to n are generated in increasing order without duplicates, as the mediant of two adjacent Farey fractions is always in lowest terms.[17] To generate the full F_n, begin with the list containing \frac{0}{1} and \frac{1}{1}. Then, traverse the current list of adjacent pairs and insert the mediant between each pair \frac{a}{b}, \frac{c}{d} if b + d \leq n. Newly inserted fractions create additional pairs for further insertions in subsequent iterations. This process continues until no more mediants can be added (i.e., for all adjacent pairs, b + d > n).[24] The mediant operation itself requires constant time, as it involves simple addition of numerators and denominators followed by reduction if necessary (though reduction is typically not needed due to the adjacency property).[17] Here is a step-by-step outline of the algorithm:- Initialize a list L with \left[ \frac{0}{1}, \frac{1}{1} \right].
- While changes occur:
- The final L is F_n.