{"history":[],"article":{"id":"588f26b3-6d01-442f-9a96-a68629527d89","title":"Farey sequence","slug":"farey-sequence","content":":::summary\n:::\n\n# \nIn [mathematics](https://bliptext.com/articles/mathematics), the **Farey [sequence](https://bliptext.com/articles/sequence)** of order n is the [sequence](https://bliptext.com/articles/sequence) of completely reduced [fractions](https://bliptext.com/articles/fraction), either between 0 and 1, or without this restriction, which when [in lowest terms](https://bliptext.com/articles/in-lowest-terms) have [denominators](https://bliptext.com/articles/denominator) less than or equal to n, arranged in order of increasing size.\nWith 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).\nA Farey sequence is sometimes called a Farey series, which is not strictly correct, because the terms are not summed.\n# [Farey diagram to F9 represented with circular arcs. In [[Media:Farey diagram horizontal arc 9.svg|the SVG image]], hover over a curve to highlight it and its terms. | upload.wikimedia.org/wikipedia/commons/9/91/Farey///diagram///horizontal///arc///9.svg]\n\n# Examples\nThe Farey sequences of orders 1 to 8 are :\n\n## Farey sunburst\nPlotting the numerators versus the denominators of a Farey sequence gives a shape like the one to the right, shown for\nF6.\nReflecting this shape around the diagonal and main axes generates the Farey sunburst, shown below.\nThe Farey sunburst of order n connects the visible integer grid points from the origin in the square of side\n2n\n, centered at the origin.\nUsing [Pick's theorem](https://bliptext.com/articles/pick-s-theorem), the area of the sunburst is\n4(\n, where\nis the [[#Sequence_length_and_index_of_a_fraction|number of fractions in\nFn\n]]. [[File:Farey_sunburst_6.svg|thumb|center|300px|Farey sunburst of order 6, with 1 interior (red) and 96 boundary (green) points giving an area of\n1 + 96⁄2 − 1 = 48,\naccording to [Pick's theorem](https://bliptext.com/articles/pick-s-theorem) ]]\n# [Plotting F6 numerators vs denominators | upload.wikimedia.org/wikipedia/commons/d/de/Sunburst///8.png]\n# [Starbursts of iterations 1–10 superimposed | upload.wikimedia.org/wikipedia/commons/3/36/Farey///sunbursts///1-10.svg]\n\n# History\nFarey sequences are named after the [British](https://bliptext.com/articles/united-kingdom) [geologist](https://bliptext.com/articles/geologist) [John Farey, Sr.](https://bliptext.com/articles/john-farey-sr), whose letter about these sequences was published in the [Philosophical Magazine](https://bliptext.com/articles/philosophical-magazine) in 1816.\nFarey conjectured, without offering proof, that each new term in a Farey sequence expansion is the [mediant](https://bliptext.com/articles/mediant-mathematics) of its neighbours.\nFarey's letter was read by [Cauchy](https://bliptext.com/articles/cauchy), who provided a proof in his Exercices de mathématique, and attributed this result to Farey.\nIn fact, another mathematician, [Charles Haros](https://bliptext.com/articles/charles-haros), had published similar results in 1802 which were not known either to Farey or to Cauchy.\nThus it was a historical accident that linked Farey's name with these sequences.\nThis is an example of [Stigler's law of eponymy](https://bliptext.com/articles/stigler-s-law-of-eponymy).\n\n# Properties\n\n## Sequence length and index of a fraction\nThe Farey sequence of order n contains all of the members of the Farey sequences of lower orders.\nIn particular Fn contains all of the members of\nFn−1\nand also contains an additional fraction for each number that is less than n and [coprime](https://bliptext.com/articles/coprime) to n. Thus\nF6\nconsists of\nF5\ntogether with the fractions 1⁄6 and 5⁄6.\nThe middle term of a Farey sequence Fn is always 1⁄2,\nfor\nn > 1\n. From this, we can relate the lengths of Fn and\nFn−1\nusing [Euler's totient function](https://bliptext.com/articles/euler-s-totient-function)\nφ(n)\nUsing the fact that\n= 2\n, we can derive an expression for the length of Fn:\nwhere\nΦ(n)\nis the [summatory totient](https://bliptext.com/articles/totient-summatory-function).\nWe also have :\nand by a [Möbius inversion formula](https://bliptext.com/articles/m-bius-inversion-formula) :\nwhere\nμ(d)\nis the number-theoretic [Möbius function](https://bliptext.com/articles/m-bius-function), and is the [floor function](https://bliptext.com/articles/floor-and-ceiling-functions).\nThe asymptotic behaviour of\nis :\nThe number of Farey fractions with denominators equal to k in Fn is given by\nφ(k)\nwhen\nk ≤ n\nand zero otherwise.\nConcerning the numerators one can define the function that returns the number of Farey fractions with numerators equal to h in Fn.\nThis function has some interesting properties as\nm ≥ 0\n, In particular, the property in the third line above implies and, further, The latter means that, for Farey sequences of even order n, the number of fractions with numerators equal to\nn⁄2\nis the same as the number of fractions with denominators equal to\nn⁄2\n, that is.\nThe index of a fraction a_{k,n} in the Farey sequence is simply the position that a_{k,n} occupies in the sequence.\nThis is of special relevance as it is used in an alternative formulation of the [Riemann hypothesis](https://bliptext.com/articles/riemann-hypothesis), see [below](https://bliptext.com/articles/).\nVarious useful properties follow:\nThe index of\n1⁄k\nwhere\nn⁄i+1 < k ≤ n⁄i\nand n is the [least common multiple](https://bliptext.com/articles/least-common-multiple) of the first i numbers,\nn = lcm([2, i])\n, is given by:\n\n## Farey neighbours\nFractions which are neighbouring terms in any Farey sequence are known as a Farey pair and have the following properties.\nIf\na⁄b\nand\nc⁄d\nare neighbours in a Farey sequence, with\na⁄b < c⁄d\n, then their difference\nc⁄d − a⁄b\nis equal to\n1⁄bd\n. Since\nthis is equivalent to saying that\nThus 1⁄3 and 2⁄5 are neighbours in\nF5\n, and their difference is 1⁄15.\nThe converse is also true.\nIf bc - ad = 1\nfor positive integers\na, b, c, d\nwith\na < b\nand\nc < d\n, then\na⁄b\nand\nc⁄d\nwill be neighbours in the Farey sequence of order\nmax(b,d)\n.\nIf\np⁄q\nhas neighbours\na⁄b\nand\nc⁄d\nin some Farey sequence, with\na⁄b < p⁄q < c⁄d\n, then\np⁄q\nis the [mediant](https://bliptext.com/articles/mediant-mathematics) of\na⁄b\nand\nc⁄d\n– in other words,\nThis follows easily from the previous property, since if\nIt follows that if\na⁄b\nand\nc⁄d\nare neighbours in a Farey sequence then the first term that appears between them as the order of the Farey sequence is incremented is\nwhich first appears in the Farey sequence of order\nb + d\n.\nThus the first term to appear between 1⁄3 and 2⁄5 is 3⁄8, which appears in\nF8\n.\nThe total number of Farey neighbour pairs in Fn is\n2\n.\nThe [Stern–Brocot tree](https://bliptext.com/articles/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.\n\n### Equivalent-area interpretation\nEvery consecutive pair of Farey rationals have an equivalent area of 1.\nSee this by interpreting consecutive rationals\nas vectors\n(p, q)\nin the xy-plane.\nThe area is given by\nAs any added fraction in between two previous consecutive Farey sequence fractions is calculated as the [mediant](https://bliptext.com/articles/mediant-mathematics) (⊕), then\n(since\nr1 = 1⁄0\nand\nr2 = 0⁄1\n, its area must be 1).\n\n## Farey neighbours and continued fractions\nFractions that appear as neighbours in a Farey sequence have closely related [continued fraction](https://bliptext.com/articles/continued-fraction) expansions.\nEvery fraction has two continued fraction expansions — in one the final term is 1; in the other the final term is greater by 1.\nIf\np⁄q\n, which first appears in Farey sequence Fq, has the [continued fraction expansions](https://bliptext.com/articles/simple-continued-fraction)\nthen the nearest neighbour of\np⁄q\nin Fq (which will be its neighbour with the larger denominator) has a continued fraction expansion\nand its other neighbour has a continued fraction expansion\nFor example, 3⁄8 has the two continued fraction expansions\n[0; 2, 1, 1, 1]\nand\n[0; 2, 1, 2]\n, and its neighbours in\nF8\nare 2⁄5, which can be expanded as\n[0; 2, 1, 1]\n[0; 2, 1]\n.\n\n## Farey fractions and the least common multiple\nThe [lcm](https://bliptext.com/articles/least-common-multiple) can be expressed as the products of Farey fractions as\nwhere\nψ(N)\nis the second [Chebyshev function](https://bliptext.com/articles/chebyshev-function).\n\n## Farey fractions and the greatest common divisor\nSince the [Euler's totient function](https://bliptext.com/articles/euler-s-totient-function) is directly connected to the [gcd](https://bliptext.com/articles/greatest-common-divisor) so is the number of elements in Fn,\nFor any 3 Farey fractions\na⁄b, c⁄d, e⁄f\nthe following identity between the [gcd](https://bliptext.com/articles/greatest-common-divisor)'s of the 2x2 [matrix determinants](https://bliptext.com/articles/matrix-determinant) in absolute value holds:\n\n## Applications\nFarey sequences are very useful to find rational approximations of irrational numbers.\nFor example, the construction by Eliahou 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\nlog2(3)\n.\nIn physical systems with resonance phenomena, Farey sequences provide a very elegant and efficient method to compute resonance locations in 1D and 2D.\nFarey sequences are prominent in studies of [any-angle path planning](https://bliptext.com/articles/any-angle-path-planning) on square-celled grids, for example in characterizing their computational complexity or optimality.\nThe 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.\nLet Q be the set of vectors\n(q, p)\nsuch that, , and p, q are coprime.\nLet Q* be the result of reflecting Q in the line\ny = x\n. Let.\nThen any r-constrained path can be described as a sequence of vectors from S. There is a bijection between Q and the Farey sequence of order r given by\n(q, p)\nmapping to.\n\n## Ford circles\nThere is a connection between Farey sequence and [Ford circles](https://bliptext.com/articles/ford-circle).\nFor every fraction\np⁄q\n(in its lowest terms) there is a Ford circle\nC[p/q]\n, which is the circle with radius and centre at Two Ford circles for different fractions are either [disjoint](https://bliptext.com/articles/disjoint-sets) or they are [tangent](https://bliptext.com/articles/tangent) to one another—two Ford circles never intersect.\nIf\n0 < p⁄q < 1\nthen the Ford circles that are tangent to\nC[p/q]\nare precisely the Ford circles for fractions that are neighbours of\np⁄q\nin some Farey sequence.\nThus\nC[2/5]\nis tangent to\nC[1/2]\n,\nC[1/3]\n,\nC[3/7]\n,\nC[3/8]\n, etc.\nFord circles appear also in the [Apollonian gasket](https://bliptext.com/articles/apollonian-gasket)\n(0,0,1,1)\n. The picture below illustrates this together with Farey resonance lines.\nApolloinan gasket Farey.png\n(0,0,1,1)\nand the Farey resonance diagram.]]\n# [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 [[Media:Comparison Ford circles Farey diagram.svg|the SVG image]], hover over a circle or curve to highlight it and its terms. | upload.wikimedia.org/wikipedia/commons/0/0f/Comparison///Ford///circles///Farey///diagram.svg]\n\n## Riemann hypothesis\nFarey sequences are used in two equivalent formulations of the [Riemann hypothesis](https://bliptext.com/articles/riemann-hypothesis).\nSuppose the terms of Fn are Define 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.\nIn 1924 [Jérôme Franel](https://bliptext.com/articles/j-r-me-franel) proved that the statement\nis equivalent to the Riemann hypothesis, and then [Edmund Landau](https://bliptext.com/articles/edmund-landau) remarked (just after Franel's paper) that the statement\nis also equivalent to the Riemann hypothesis.\n\n## Other sums involving Farey fractions\nThe sum of all Farey fractions of order n is half the number of elements:\nThe sum of the denominators in the Farey sequence is twice the sum of the numerators and relates to Euler's totient function:\nwhich was conjectured by Harold L. Aaron in 1962 and demonstrated by Jean A. Blake in 1966.\nA one line proof of the Harold L. Aaron conjecture is as follows.\nThe sum of the numerators is The sum of denominators is\nThe quotient of the first sum by the second sum is 1⁄2.\nLet bj be the ordered denominators of Fn, then:\nand\nLet the jth Farey fraction in Fn, then\nwhich is demonstrated in.\nAlso according to this reference the term inside the sum can be expressed in many different ways:\nobtaining thus many different sums over the Farey elements with same result.\nUsing the symmetry around 1/2 the former sum can be limited to half of the sequence as\nThe [Mertens function](https://bliptext.com/articles/mertens-function) can be expressed as a sum over Farey fractions as\nwhere is the Farey sequence of order n.\nThis formula is used in the proof of the [Franel–Landau theorem](https://bliptext.com/articles/).\n\n# Next term\nA surprisingly simple algorithm exists to generate the terms of Fn in either traditional order (ascending) or non-traditional order (descending).\nThe algorithm computes each successive entry in terms of the previous two entries using the mediant property given above.\nIf a⁄b and c⁄d are the two given entries, and p⁄q is the unknown next entry, then\nc⁄d = a + p⁄b + q\n. Since c⁄d is in lowest terms, there must be an integer k such that\nkc = a + p\nand\nkd = b + q\n, giving\np = kc − a\nand\nq = kd − b\n. If we consider p and q to be functions of k, then\nso the larger k gets, the closer p⁄q gets to c⁄d.\nTo give the next term in the sequence k must be as large as possible, subject to\nkd − b ≤ n\n(as we are only considering numbers with denominators not greater than n), so k is the greatest integer ≤ n + b⁄d.\nPutting this value of k back into the equations for p and q gives\nThis is implemented in [Python](https://bliptext.com/articles/python-programming-language) as follows:\nBrute-force searches for solutions to [Diophantine equations](https://bliptext.com/articles/diophantine-equation) in rationals can often take advantage of the Farey series (to search only reduced forms).\nWhile 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.\n\n# Footnotes","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T19:16:52.144Z","updated_at":"2025-01-25T19:16:52.144Z","search_vector":"'farey':1 'sequenc':2","search_content":" \n \n\n# \nIn [mathematics](https://bliptext.com/articles/mathematics), the **Farey [sequence](https://bliptext.com/articles/sequence)** of order n is the [sequence](https://bliptext.com/articles/sequence) of completely reduced [fractions](https://bliptext.com/articles/fraction), either between 0 and 1, or without this restriction, which when [in lowest terms](https://bliptext.com/articles/in-lowest-terms) have [denominators](https://bliptext.com/articles/denominator) less than or equal to n, arranged in order of increasing size.\nWith 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).\nA Farey sequence is sometimes called a Farey series, which is not strictly correct, because the terms are not summed.\n# [Farey diagram to F9 represented with circular arcs. In [[Media:Farey diagram horizontal arc 9.svg|the SVG image]], hover over a curve to highlight it and its terms. | upload.wikimedia.org/wikipedia/commons/9/91/Farey///diagram///horizontal///arc///9.svg]\n\n# Examples\nThe Farey sequences of orders 1 to 8 are :\n\n## Farey sunburst\nPlotting the numerators versus the denominators of a Farey sequence gives a shape like the one to the right, shown for\nF6.\nReflecting this shape around the diagonal and main axes generates the Farey sunburst, shown below.\nThe Farey sunburst of order n connects the visible integer grid points from the origin in the square of side\n2n\n, centered at the origin.\nUsing [Pick's theorem](https://bliptext.com/articles/pick-s-theorem), the area of the sunburst is\n4(\n, where\nis the [[#Sequence_length_and_index_of_a_fraction|number of fractions in\nFn\n]]. [[File:Farey_sunburst_6.svg|thumb|center|300px|Farey sunburst of order 6, with 1 interior (red) and 96 boundary (green) points giving an area of\n1 + 96⁄2 − 1 = 48,\naccording to [Pick's theorem](https://bliptext.com/articles/pick-s-theorem) ]]\n# [Plotting F6 numerators vs denominators | upload.wikimedia.org/wikipedia/commons/d/de/Sunburst///8.png]\n# [Starbursts of iterations 1–10 superimposed | upload.wikimedia.org/wikipedia/commons/3/36/Farey///sunbursts///1-10.svg]\n\n# History\nFarey sequences are named after the [British](https://bliptext.com/articles/united-kingdom) [geologist](https://bliptext.com/articles/geologist) [John Farey, Sr.](https://bliptext.com/articles/john-farey-sr), whose letter about these sequences was published in the [Philosophical Magazine](https://bliptext.com/articles/philosophical-magazine) in 1816.\nFarey conjectured, without offering proof, that each new term in a Farey sequence expansion is the [mediant](https://bliptext.com/articles/mediant-mathematics) of its neighbours.\nFarey's letter was read by [Cauchy](https://bliptext.com/articles/cauchy), who provided a proof in his Exercices de mathématique, and attributed this result to Farey.\nIn fact, another mathematician, [Charles Haros](https://bliptext.com/articles/charles-haros), had published similar results in 1802 which were not known either to Farey or to Cauchy.\nThus it was a historical accident that linked Farey's name with these sequences.\nThis is an example of [Stigler's law of eponymy](https://bliptext.com/articles/stigler-s-law-of-eponymy).\n\n# Properties\n\n## Sequence length and index of a fraction\nThe Farey sequence of order n contains all of the members of the Farey sequences of lower orders.\nIn particular Fn contains all of the members of\nFn−1\nand also contains an additional fraction for each number that is less than n and [coprime](https://bliptext.com/articles/coprime) to n. Thus\nF6\nconsists of\nF5\ntogether with the fractions 1⁄6 and 5⁄6.\nThe middle term of a Farey sequence Fn is always 1⁄2,\nfor\nn > 1\n. From this, we can relate the lengths of Fn and\nFn−1\nusing [Euler's totient function](https://bliptext.com/articles/euler-s-totient-function)\nφ(n)\nUsing the fact that\n= 2\n, we can derive an expression for the length of Fn:\nwhere\nΦ(n)\nis the [summatory totient](https://bliptext.com/articles/totient-summatory-function).\nWe also have :\nand by a [Möbius inversion formula](https://bliptext.com/articles/m-bius-inversion-formula) :\nwhere\nμ(d)\nis the number-theoretic [Möbius function](https://bliptext.com/articles/m-bius-function), and is the [floor function](https://bliptext.com/articles/floor-and-ceiling-functions).\nThe asymptotic behaviour of\nis :\nThe number of Farey fractions with denominators equal to k in Fn is given by\nφ(k)\nwhen\nk ≤ n\nand zero otherwise.\nConcerning the numerators one can define the function that returns the number of Farey fractions with numerators equal to h in Fn.\nThis function has some interesting properties as\nm ≥ 0\n, In particular, the property in the third line above implies and, further, The latter means that, for Farey sequences of even order n, the number of fractions with numerators equal to\nn⁄2\nis the same as the number of fractions with denominators equal to\nn⁄2\n, that is.\nThe index of a fraction a_{k,n} in the Farey sequence is simply the position that a_{k,n} occupies in the sequence.\nThis is of special relevance as it is used in an alternative formulation of the [Riemann hypothesis](https://bliptext.com/articles/riemann-hypothesis), see [below](https://bliptext.com/articles/).\nVarious useful properties follow:\nThe index of\n1⁄k\nwhere\nn⁄i+1 < k ≤ n⁄i\nand n is the [least common multiple](https://bliptext.com/articles/least-common-multiple) of the first i numbers,\nn = lcm([2, i])\n, is given by:\n\n## Farey neighbours\nFractions which are neighbouring terms in any Farey sequence are known as a Farey pair and have the following properties.\nIf\na⁄b\nand\nc⁄d\nare neighbours in a Farey sequence, with\na⁄b < c⁄d\n, then their difference\nc⁄d − a⁄b\nis equal to\n1⁄bd\n. Since\nthis is equivalent to saying that\nThus 1⁄3 and 2⁄5 are neighbours in\nF5\n, and their difference is 1⁄15.\nThe converse is also true.\nIf bc - ad = 1\nfor positive integers\na, b, c, d\nwith\na < b\nand\nc < d\n, then\na⁄b\nand\nc⁄d\nwill be neighbours in the Farey sequence of order\nmax(b,d)\n.\nIf\np⁄q\nhas neighbours\na⁄b\nand\nc⁄d\nin some Farey sequence, with\na⁄b < p⁄q < c⁄d\n, then\np⁄q\nis the [mediant](https://bliptext.com/articles/mediant-mathematics) of\na⁄b\nand\nc⁄d\n– in other words,\nThis follows easily from the previous property, since if\nIt follows that if\na⁄b\nand\nc⁄d\nare neighbours in a Farey sequence then the first term that appears between them as the order of the Farey sequence is incremented is\nwhich first appears in the Farey sequence of order\nb + d\n.\nThus the first term to appear between 1⁄3 and 2⁄5 is 3⁄8, which appears in\nF8\n.\nThe total number of Farey neighbour pairs in Fn is\n2\n.\nThe [Stern–Brocot tree](https://bliptext.com/articles/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.\n\n### Equivalent-area interpretation\nEvery consecutive pair of Farey rationals have an equivalent area of 1.\nSee this by interpreting consecutive rationals\nas vectors\n(p, q)\nin the xy-plane.\nThe area is given by\nAs any added fraction in between two previous consecutive Farey sequence fractions is calculated as the [mediant](https://bliptext.com/articles/mediant-mathematics) (⊕), then\n(since\nr1 = 1⁄0\nand\nr2 = 0⁄1\n, its area must be 1).\n\n## Farey neighbours and continued fractions\nFractions that appear as neighbours in a Farey sequence have closely related [continued fraction](https://bliptext.com/articles/continued-fraction) expansions.\nEvery fraction has two continued fraction expansions — in one the final term is 1; in the other the final term is greater by 1.\nIf\np⁄q\n, which first appears in Farey sequence Fq, has the [continued fraction expansions](https://bliptext.com/articles/simple-continued-fraction)\nthen the nearest neighbour of\np⁄q\nin Fq (which will be its neighbour with the larger denominator) has a continued fraction expansion\nand its other neighbour has a continued fraction expansion\nFor example, 3⁄8 has the two continued fraction expansions\n[0; 2, 1, 1, 1]\nand\n[0; 2, 1, 2]\n, and its neighbours in\nF8\nare 2⁄5, which can be expanded as\n[0; 2, 1, 1]\n[0; 2, 1]\n.\n\n## Farey fractions and the least common multiple\nThe [lcm](https://bliptext.com/articles/least-common-multiple) can be expressed as the products of Farey fractions as\nwhere\nψ(N)\nis the second [Chebyshev function](https://bliptext.com/articles/chebyshev-function).\n\n## Farey fractions and the greatest common divisor\nSince the [Euler's totient function](https://bliptext.com/articles/euler-s-totient-function) is directly connected to the [gcd](https://bliptext.com/articles/greatest-common-divisor) so is the number of elements in Fn,\nFor any 3 Farey fractions\na⁄b, c⁄d, e⁄f\nthe following identity between the [gcd](https://bliptext.com/articles/greatest-common-divisor)'s of the 2x2 [matrix determinants](https://bliptext.com/articles/matrix-determinant) in absolute value holds:\n\n## Applications\nFarey sequences are very useful to find rational approximations of irrational numbers.\nFor example, the construction by Eliahou 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\nlog2(3)\n.\nIn physical systems with resonance phenomena, Farey sequences provide a very elegant and efficient method to compute resonance locations in 1D and 2D.\nFarey sequences are prominent in studies of [any-angle path planning](https://bliptext.com/articles/any-angle-path-planning) on square-celled grids, for example in characterizing their computational complexity or optimality.\nThe 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.\nLet Q be the set of vectors\n(q, p)\nsuch that, , and p, q are coprime.\nLet Q* be the result of reflecting Q in the line\ny = x\n. Let.\nThen any r-constrained path can be described as a sequence of vectors from S. There is a bijection between Q and the Farey sequence of order r given by\n(q, p)\nmapping to.\n\n## Ford circles\nThere is a connection between Farey sequence and [Ford circles](https://bliptext.com/articles/ford-circle).\nFor every fraction\np⁄q\n(in its lowest terms) there is a Ford circle\nC[p/q]\n, which is the circle with radius and centre at Two Ford circles for different fractions are either [disjoint](https://bliptext.com/articles/disjoint-sets) or they are [tangent](https://bliptext.com/articles/tangent) to one another—two Ford circles never intersect.\nIf\n0 < p⁄q < 1\nthen the Ford circles that are tangent to\nC[p/q]\nare precisely the Ford circles for fractions that are neighbours of\np⁄q\nin some Farey sequence.\nThus\nC[2/5]\nis tangent to\nC[1/2]\n,\nC[1/3]\n,\nC[3/7]\n,\nC[3/8]\n, etc.\nFord circles appear also in the [Apollonian gasket](https://bliptext.com/articles/apollonian-gasket)\n(0,0,1,1)\n. The picture below illustrates this together with Farey resonance lines.\nApolloinan gasket Farey.png\n(0,0,1,1)\nand the Farey resonance diagram.]]\n# [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 [[Media:Comparison Ford circles Farey diagram.svg|the SVG image]], hover over a circle or curve to highlight it and its terms. | upload.wikimedia.org/wikipedia/commons/0/0f/Comparison///Ford///circles///Farey///diagram.svg]\n\n## Riemann hypothesis\nFarey sequences are used in two equivalent formulations of the [Riemann hypothesis](https://bliptext.com/articles/riemann-hypothesis).\nSuppose the terms of Fn are Define 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.\nIn 1924 [Jérôme Franel](https://bliptext.com/articles/j-r-me-franel) proved that the statement\nis equivalent to the Riemann hypothesis, and then [Edmund Landau](https://bliptext.com/articles/edmund-landau) remarked (just after Franel's paper) that the statement\nis also equivalent to the Riemann hypothesis.\n\n## Other sums involving Farey fractions\nThe sum of all Farey fractions of order n is half the number of elements:\nThe sum of the denominators in the Farey sequence is twice the sum of the numerators and relates to Euler's totient function:\nwhich was conjectured by Harold L. Aaron in 1962 and demonstrated by Jean A. Blake in 1966.\nA one line proof of the Harold L. Aaron conjecture is as follows.\nThe sum of the numerators is The sum of denominators is\nThe quotient of the first sum by the second sum is 1⁄2.\nLet bj be the ordered denominators of Fn, then:\nand\nLet the jth Farey fraction in Fn, then\nwhich is demonstrated in.\nAlso according to this reference the term inside the sum can be expressed in many different ways:\nobtaining thus many different sums over the Farey elements with same result.\nUsing the symmetry around 1/2 the former sum can be limited to half of the sequence as\nThe [Mertens function](https://bliptext.com/articles/mertens-function) can be expressed as a sum over Farey fractions as\nwhere is the Farey sequence of order n.\nThis formula is used in the proof of the [Franel–Landau theorem](https://bliptext.com/articles/).\n\n# Next term\nA surprisingly simple algorithm exists to generate the terms of Fn in either traditional order (ascending) or non-traditional order (descending).\nThe algorithm computes each successive entry in terms of the previous two entries using the mediant property given above.\nIf a⁄b and c⁄d are the two given entries, and p⁄q is the unknown next entry, then\nc⁄d = a + p⁄b + q\n. Since c⁄d is in lowest terms, there must be an integer k such that\nkc = a + p\nand\nkd = b + q\n, giving\np = kc − a\nand\nq = kd − b\n. If we consider p and q to be functions of k, then\nso the larger k gets, the closer p⁄q gets to c⁄d.\nTo give the next term in the sequence k must be as large as possible, subject to\nkd − b ≤ n\n(as we are only considering numbers with denominators not greater than n), so k is the greatest integer ≤ n + b⁄d.\nPutting this value of k back into the equations for p and q gives\nThis is implemented in [Python](https://bliptext.com/articles/python-programming-language) as follows:\nBrute-force searches for solutions to [Diophantine equations](https://bliptext.com/articles/diophantine-equation) in rationals can often take advantage of the Farey series (to search only reduced forms).\nWhile 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.\n\n# Footnotes","revisionCount":0},"hasMore":false,"nextCursor":null}