TOPICS
Search

Farey Sequence

The Farey sequence F_n for any positive integer n is the set of reduced fractions a/b with 1<=b<=n, 0<=a<=b, and gcd(a,b)=1, arranged in increasing order. The first few are

F_1={0/1,1/1}
(1)
F_2={0/1,1/2,1/1}
(2)
F_3={0/1,1/3,1/2,2/3,1/1}
(3)
F_4={0/1,1/4,1/3,1/2,2/3,3/4,1/1}
(4)
F_5={0/1,1/5,1/4,1/3,2/5,1/2,3/5,2/3,3/4,4/5,1/1}
(5)

(OEIS A006842 and A006843). Except for F_1, each F_n has an odd number of terms and the middle term is always 1/2.

Let p/q, p^'/q^', and p^('')/q^('') be three successive terms in a Farey sequence. Then

qp^'-pq^'=1
(6)
(p^')/(q^')=(p+p^(''))/(q+q^('')).
(7)

These two statements are actually equivalent (Hardy and Wright 1979, p. 24). For n>=2, obtain F_n from F_(n-1) by inserting the mediant fraction (a+b)/(c+d) between successive terms a/c and b/d when c+d=n (Hardy and Wright 1979, pp. 25-26; Conway and Guy 1996; Apostol 1997). Given 0<=a/b<c/d<=1 with bc-ad=1, let h/k be the mediant of a/b and c/d. Then a/b<h/k<c/d, and these fractions satisfy the unimodular relations

bh-ak=1
(8)
ck-dh=1
(9)

(Apostol 1997, p. 99).

The number of terms N(n) in the Farey sequence for the positive integer n is

N(n)=1+sum_(k=1)^(n)phi(k)
(10)
=1+Phi(n),
(11)

where phi(k) is the totient function and Phi(n) is the totient summatory function of phi(k), giving 2, 3, 5, 7, 11, 13, 19, ... (OEIS A005728). For large n,

N(n)∼(3n^2)/(pi^2)=0.3039635509...n^2
(12)

(OEIS A104141; Vardi 1991, p. 155).

Ford circles provide a method of visualizing the Farey sequence. The fractions in F_n other than 0/1 define a subtree of the Stern-Brocot tree obtained by pruning unwanted branches (Graham et al. 1994).

The Season 2 episode "Bettor or Worse" (2006) of the television crime drama NUMB3RS features Farey sequences.

See also

Ford Circle, Mediant, Minkowski's Question Mark Function, Sequence Rank, Stern-Brocot Tree

Explore with Wolfram|Alpha

References

Apostol, T. M. "Farey Fractions." §5.4 in Modular Functions and Dirichlet Series in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 97-99, 1997.Beiler, A. H. "Farey Tails." Ch. 16 in Recreations in the Theory of Numbers: The Queen of Mathematics Entertains. New York: Dover, 1966.Bogomolny, A. "Farey Series, A Story." https://www.cut-the-knot.org/blue/FareyHistory.shtml.Conway, J. H. and Guy, R. K. "Farey Fractions and Ford Circles." The Book of Numbers. New York: Springer-Verlag, pp. 152-154 and 156, 1996.Devaney, R. "The Mandelbrot Set and the Farey Tree, and the Fibonacci Sequence." Amer. Math. Monthly 106, 289-302, 1999.Dickson, L. E. History of the Theory of Numbers, Vol. 1: Divisibility and Primality. New York: Dover, pp. 155-158, 2005.Farey, J. "On a Curious Property of Vulgar Fractions." London, Edinburgh and Dublin Phil. Mag. 47, 385, 1816.Graham, R. L.; Knuth, D. E.; and Patashnik, O. Concrete Mathematics: A Foundation for Computer Science, 2nd ed. Reading, MA: Addison-Wesley, pp. 118-119, 1994.Guy, R. K. "Mahler's Generalization of Farey Series." §F27 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 263-265, 1994.Hardy, G. H. and Wright, E. M. "Farey Series and a Theorem of Minkowski." Ch. 3 in An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, pp. 23-37, 1979.Lagarias, J. C. and Tresser, C. "A Walk Along the Branches of the Extended Farey Tree." IBM J. Res. Dev. 39, 283-294, 1995. https://doi.org/10.1147/rd.393.0283.Sloane, N. J. A. Sequences A005728/M0661, A006842/M0041, A006843/M0081, and A104141 in "The On-Line Encyclopedia of Integer Sequences."Sylvester, J. J. "On the Number of Fractions Contained in Any Farey Series of Which the Limiting Number Is Given." London, Edinburgh and Dublin Phil. Mag. (5th Series) 15, 251, 1883.Vardi, I. Computational Recreations in Mathematica. Reading, MA: Addison-Wesley, p. 155, 1991.

Referenced on Wolfram|Alpha

Farey Sequence

Cite this as:

Weisstein, Eric W. "Farey Sequence." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/FareySequence.html

Subject classifications