Farey Sequence

The Farey sequence $F_n$ for any Positive Integer $n$ is the set of irreducible Rational Numbers $a/b$ with $0\leq a\leq b\leq n$ and $(a,b)=1$ arranged in increasing order.

$$F_1 = \{{\textstyle{0\over 1}}, {\textstyle{1\over 1}}\}$$ (1)

$$F_2 = \{{\textstyle{0\over 1}}, {\textstyle{1\over 2}}, {\textstyle{1\over 1}}\}$$ (2)

$$F_3 = \{{\textstyle{0\over 1}}, {\textstyle{1\over 3}}, {\textstyle{1\over 2}}, {\textstyle{2\over 3}}, {\textstyle{1\over 1}}\}$$ (3)

$$F_4 = \{{\textstyle{0\over 1}}, {\textstyle{1\over 4}}, {\textstyle{1\o... ...r 2}}, {\textstyle{2\over 3}}, {\textstyle{3\over 4}}, {\textstyle{1\over 1}}\}$$ (4)

$$F_5 = \{{\textstyle{0\over 1}}, {\textstyle{1\over 5}}, {\textstyle{1\o... ... 3}}, {\textstyle{3\over 4}}, {\textstyle{4\over 5}}, {\textstyle{1\over 1}}\}.$$ (5)

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 series. Then

$$qp'-pq'=1$$ (6)

$${p'\over q'}={p+p''\over q+q''}.$$ (7)

These two statements are actually equivalent.

The number of terms $N(n)$ in the Farey sequence for the Integer $n$ is

$$N(n)=1+\sum_{k=1}^n \phi(k)=1+\Phi(n),$$ (8)

where $\phi(k)$ is the Totient Function and $\Phi(n)$ is the Summatory Function of $\phi(k)$, giving 2, 3, 5, 7, 11, 13, 19, ... (Sloane's A005728). The asymptotic limit for the function $N(n)$ is

$$N(n)\sim {3n^2\over\pi^2} = 0.3039635509n^2$$ (9)

(Vardi 1991, p. 155). For a method of computing a successive sequence from an existing one of $n$ terms, insert the Mediant fraction $(a+b)/(c+d)$ between terms $a/c$ and $b/d$ when $c+d\leq n$ (Hardy and Wright 1979, pp. 25-26; Conway and Guy 1996).

Ford Circles provide a method of visualizing the Farey sequence. The Farey sequence $F_n$ defines a subtree of the Stern-Brocot Tree obtained by pruning unwanted branches (Graham et al. 1994).

See also Ford Circle, Mediant, Rank (Sequence), Stern-Brocot Tree

References

Beiler, A. H. ``Farey Tails.'' Ch. 16 in Recreations in the Theory of Numbers: The Queen of Mathematics Entertains. New York: Dover, 1966.

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.

Dickson, L. E. History of the Theory of Numbers, Vol. 1: Divisibility and Primality. New York: Chelsea, pp. 155-158, 1952.

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. An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, 1979.

Sloane, N. J. A. Sequences A005728/M0661, A006842/M0041, and A006843/M0081 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

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.

Weisstein, E. W. ``Plane Geometry.'' Mathematica notebook PlaneGeometry.m.