Farey sequence

The Farey sequences of orders 1 to 8 are : :F1 = { , } :F2 = { , , } :F3 = { , , , , } :F4 = { , , , , , , } :F5 = { , , , , , , , , , , } :F6 = { , , , , , , , , , , , , } :F7 = { , , , , , , , , , , , , , , , , , , } :F8 = { , , , , , , , , , , , , , , , , , , , , , , } Farey sunburst Plotting the numerators versus the denominators of a Farey sequence gives a shape like the one to the right, shown for Reflecting this shape around the diagonal and main axes generates the Farey sunburst, shown below. The Farey sunburst of order connects the visible integer grid points from the origin in the square of side , centered at the origin. Using Pick's theorem, the area of the sunburst is , where is the number of fractions in. ==History==

:''The history of 'Farey series' is very curious'' — Hardy & Wright (1979) :... 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) Farey sequences are named after the British geologist John Farey, Sr., whose letter about these sequences was published in the Philosophical Magazine in 1816. Farey conjectured, without offering proof, that each new term in a Farey sequence expansion is the mediant of its neighbours. Farey's letter was read by Cauchy, who provided a proof in his Exercices de mathématique, and attributed this result to Farey. In fact, another mathematician, Charles Haros, had published similar results in 1802 which were not known either to Farey or to Cauchy. Thus it was a historical accident that linked Farey's name with these sequences. This is an example of Stigler's law of eponymy. ==Properties==

Sequence length and index of a fraction The Farey sequence of order contains all of the members of the Farey sequences of lower orders. In particular contains all of the members of and also contains an additional fraction for each number that is less than and coprime to . Thus consists of together with the fractions and . The middle term of a Farey sequence is always , for . From this, we can relate the lengths of and using Euler's totient function : |F_n| = |F_{n-1}| + \varphi(n). Using the fact that , we can derive an expression for the length of : |F_n| = 1 + \sum_{m=1}^n \varphi(m) = 1 + \Phi(n), where is the summatory totient. 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 : |F_n| = \frac{1}{2} (n+3)n - \sum_{d=2}^n|F_{\lfloor n/d \rfloor}|, where is the number-theoretic Möbius function, and \lfloor n/d \rfloor is the floor function. The asymptotic behaviour of is : |F_n| \sim \frac {3n^2}{\pi^2}. The number of Farey fractions with denominators equal to in is given by when 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 in . This function has some interesting properties as :\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 , :\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 , the number of fractions with numerators equal to is the same as the number of fractions with denominators equal to , 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, see below. Various useful properties follow: \begin{align} I_n(0/1) &= 0, \\[6pt] I_n(1/n) &= 1, \\[2pt] I_n(1/2) &= \frac{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 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 . This formula is used in the proof of the Franel–Landau theorem. ==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 and are the two given entries, and is the unknown next entry, then . Since is in lowest terms, there must be an integer k such that and , giving and . 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 gets to . To give the next term in the sequence k must be as large as possible, subject to (as we are only considering numbers with denominators not greater than n), so k is the greatest . 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 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 Brute-force searches for solutions to Diophantine equations 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. ==See also==