Farey

Farey sequences, denoted F_n, are the ascending lists of fractions between 0 and 1 whose denominators do not exceed n, written in reduced form. Each F_n begins with 0/1 and ends with 1/1, and contains every rational a/b with 0 ≤ a ≤ b ≤ n and gcd(a,b) = 1, arranged in increasing order.

Two neighboring terms a/b and c/d in F_n satisfy bc − ad = 1. The mediant, (a + c)/(b + d), lies between them and appears in F_n precisely when b + d ≤ n. This mediant property provides a constructive way to generate Farey sequences and explains how new terms are inserted as n increases.

The size of F_n is given by |F_n| = 1 + ∑_{m=1}^n φ(m), where φ is Euler’s totient function. As n grows, |F_n| is asymptotically about 3 n^2 / π^2, reflecting the density of reduced fractions with bounded denominators.

Farey sequences are named after John Farey, who described the mediant relation in the early 19th century. They have applications in Diophantine approximation and are closely related to the Stern–Brocot tree, a binary tree that represents positive rational numbers and encodes neighboring relations similar to those in Farey sequences.