From Wikipedia, the free encyclopedia - View original article

In mathematics, the **Farey sequence** of order *n* is the sequence of completely reduced fractions between 0 and 1 which, when in lowest terms, have denominators less than or equal to *n*, arranged in order of increasing size.

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).

A Farey sequence is sometimes called a Farey series, which is not strictly correct, because the terms are not summed.

The Farey sequences of orders 1 to 8 are :

*F*_{1}= { 01_{,}11 }*F*_{2}= { 01_{,}12_{,}11 }*F*_{3}= { 01_{,}13_{,}12_{,}23_{,}11 }*F*_{4}= { 01_{,}14_{,}13_{,}12_{,}23_{,}34_{,}11 }*F*_{5}= { 01_{,}15_{,}14_{,}13_{,}25_{,}12_{,}35_{,}23_{,}34_{,}45_{,}11 }*F*_{6}= { 01_{,}16_{,}15_{,}14_{,}13_{,}25_{,}12_{,}35_{,}23_{,}34_{,}45_{,}56_{,}11 }*F*_{7}= { 01_{,}17_{,}16_{,}15_{,}14_{,}27_{,}13_{,}25_{,}37_{,}12_{,}47_{,}35_{,}23_{,}57_{,}34_{,}45_{,}56_{,}67_{,}11 }*F*_{8}= { 01_{,}18_{,}17_{,}16_{,}15_{,}14_{,}27_{,}13_{,}38_{,}25_{,}37_{,}12_{,}47_{,}35_{,}58_{,}23_{,}57_{,}34_{,}45_{,}56_{,}67_{,}78_{,}11 }

Centered |
---|

F_{1} = { 01_{,} 11 }F_{2} = { 01_{,} 12_{,} 11 }F_{3} = { 01_{,} 13_{,} 12_{,} 23_{,} 11 }F_{4} = { 01_{,} 14_{,} 13_{,} 12_{,} 23_{,} 34_{,} 11 }F_{5} = { 01_{,} 15_{,} 14_{,} 13_{,} 25_{,} 12_{,} 35_{,} 23_{,} 34_{,} 45_{,} 11 }F_{6} = { 01_{,} 16_{,} 15_{,} 14_{,} 13_{,} 25_{,} 12_{,} 35_{,} 23_{,} 34_{,} 45_{,} 56_{,} 11 }F_{7} = { 01_{,} 17_{,} 16_{,} 15_{,} 14_{,} 27_{,} 13_{,} 25_{,} 37_{,} 12_{,} 47_{,} 35_{,} 23_{,} 57_{,} 34_{,} 45_{,} 56_{,} 67_{,} 11 }F_{8} = { 01_{,} 18_{,} 17_{,} 16_{,} 15_{,} 14_{,} 27_{,} 13_{,} 38_{,} 25_{,} 37_{,} 12_{,} 47_{,} 35_{,} 58_{,} 23_{,} 57_{,} 34_{,} 45_{,} 56_{,} 67_{,} 78_{,} 11 } |

Sorted |
---|

F1 = {0/1, 1/1} F2 = {0/1, 1/2, 1/1} F3 = {0/1, 1/3, 1/2, 2/3, 1/1} F4 = {0/1, 1/4, 1/3, 1/2, 2/3, 3/4, 1/1} F5 = {0/1, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 1/1} F6 = {0/1, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1/1} F7 = {0/1, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 2/5, 3/7, 1/2, 4/7, 3/5, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 1/1} F8 = {0/1, 1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8, 1/1} |

*The history of 'Farey series' is very curious*— Hardy & Wright (1979) Chapter III^{[1]}

*... 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) Chapter XVI^{[2]}

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 *Exercises 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.^{[2]} Thus it was a historical accident that linked Farey's name with these sequences. This is an example of Stigler's law of eponymy.

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

From this, we can relate the lengths of *F _{n}* and

Using the fact that |*F*_{1}| = 2, we can derive an expression for the length of *F _{n}* :

We also have:

where µ(*d*) is the number-theoretic Möbius function, and

by a Möbius inversion formula.

The asymptotic behaviour of |*F _{n}*| is :

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

this is equivalent to saying that

*bc*−*ad*= 1.

Thus 13 and 25 are neighbours in *F*_{5}, and their difference is 115.

The converse is also true. If

*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

*a**b*<*p**q*<*c**d*

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

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 increased is

which first appears in the Farey sequence of order *b* + *d*.

Thus the first term to appear between 13 and 25 is 38, which appears in *F*_{8}.

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

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 than 1. If *p**q*, which first appears in Farey sequence *F _{q}*, has continued fraction expansions

- [0;
*a*_{1},*a*_{2}, …,*a*_{n − 1},*a*_{n}, 1] - [0;
*a*_{1},*a*_{2}, …,*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*_{1},*a*_{2}, …,*a*_{n}]

and its other neighbour has a continued fraction expansion

- [0;
*a*_{1},*a*_{2}, …,*a*_{n − 1}]

Thus 38 has the two continued fraction expansions [0; 2, 1, 1, 1] and [0; 2, 1, 2], and its neighbours in *F _{8}* are 25, which can be expanded as [0; 2, 1, 1]; and 13, which can be expanded as [0; 2, 1].

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/(2*q*^{2}) and centre at (*p*/*q*, 1/(2*q*^{2})). 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.

Farey sequences are used in two equivalent formulations of the Riemann hypothesis. Suppose the terms of are . Define , in other words is the difference between the *k*th term of the *n*th Farey sequence, and the *k*th member of a set of the same number of points, distributed evenly on the unit interval. In 1924 Jérôme Franel^{[3]} proved that the statement

is equivalent to the Riemann hypothesis, and then Edmund Landau^{[4]} remarked (just after Franel's paper) that the statement

is also equivalent to the Riemann hypothesis.

A surprisingly simple algorithm exists to generate the terms of *F _{n}* 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

This is implemented in Python as:

def farey( n, asc=True ): """Python function to print the nth Farey sequence, either ascending or descending.""" if asc: a, b, c, d = 0, 1, 1 , n # (*) else: a, b, c, d = 1, 1, n-1 , n # (*) print "%d/%d" % (a,b) while (asc and c <= n) or (not asc and a > 0): k = int((n + b)/d) a, b, c, d = c, d, k*c - a, k*d - b print "%d/%d" % (a,b)

Brute-force searches for solutions to Diophantine equations in rationals can often take advantage of the Farey series (to search only reduced forms). The lines marked (*) can also be modified to include any two adjacent terms so as to generate terms only larger (or smaller) than a given term.^{[5]}

**^**Hardy, G.H. & Wright, E.M. (1979)*An Introduction to the Theory of Numbers*(Fifth Edition). Oxford University Press. ISBN 0-19-853171-0- ^
^{a}^{b}Beiler, Albert H. (1964)*Recreations in the Theory of Numbers*(Second Edition). Dover. ISBN 0-486-21096-0. Cited in Farey Series, A Story at Cut-the-Knot **^**"Les suites de Farey et le théorème des nombres premiers", Gött. Nachr. 1924, 198-201**^**"Bemerkungen zu der vorstehenden Abhandlung von Herrn Franel", Gött. Nachr. 1924, 202-206**^**Norman Routledge, "Computing Farey Series,"*The Mathematical Gazette*, Vol.**92**(No. 523), 55–62 (March 2008).

- Allen Hatcher, Topology of Numbers
- Ronald L. Graham, Donald E. Knuth, and Oren Patashnik,
*Concrete Mathematics: A Foundation for Computer Science*, 2nd Edition (Addison-Wesley, Boston, 1989); in particular, Sec. 4.5 (pp. 115–123), Bonus Problem 4.61 (pp. 150, 523–524), Sec. 4.9 (pp. 133–139), Sec. 9.3, Problem 9.3.6 (pp. 462–463). ISBN 0-201-55802-5. - Linas Vepstas.
*The Minkowski Question Mark, GL(2,Z), and the Modular Group.*http://linas.org/math/chap-minkowski.pdf reviews the isomorphisms of the Stern-Brocot Tree. - Linas Vepstas.
*Symmetries of Period-Doubling Maps.*http://linas.org/math/chap-takagi.pdf reviews connections between Farey Fractions and Fractals. - Scott B. Guthery,
*A Motif of Mathematics: History and Application of the Mediant and the Farey Sequence*, (Docent Press, Boston, 2010). ISBN 1-4538-1057-9. - Cristian Cobeli and Alexandru Zaharescu,
*The Haros-Farey Sequence at Two Hundred Years. A Survey*, Acta Univ. Apulensis Math. Inform. no. 5 (2003) 1–38, pp. 1–20 pp. 21–38 - A.O. Matveev,
*A Note on Boolean Lattices and Farey Sequences II*, Integers 8(1), 2008, #A24 - A.O. Matveev,
*Neighboring Fractions in Farey Subsequences*, arXiv:0801.1981

- Alexander Bogomolny. Farey series and Stern-Brocot Tree at Cut-the-Knot
- Hazewinkel, Michiel, ed. (2001), "Farey series",
*Encyclopedia of Mathematics*, Springer, ISBN 978-1-55608-010-4 - Weisstein, Eric W., "Stern-Brocot Tree",
*MathWorld*. - Farey Sequence from The On-Line Encyclopedia of Integer Sequences.