Farey sequence

Definition

Let $n$ be a positive integer. The Farey sequence $F_n$ of order $n$ is the increasing sequence of all fractions $\frac{a}{b}$ with $0 \le a \le b \le n$ and $\gcd(a, b) = 1$. Each fraction is in lowest terms, and $F_n$ starts with $\frac{0}{1}$ and ends with $\frac{1}{1}$.

Remarks

For example, $F_5 = \left( \frac{0}{1}, \frac{1}{5}, \frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \frac{1}{1} \right)$. If $\frac{a}{b} < \frac{c}{d}$ are neighbours in $F_n$, then $bc - ad = 1$. The length of $F_n$ is $1 + \sum_{k=1}^{n} \varphi(k)$, with $\varphi$ Euler's totient function. The sequences are named after John Farey, whose letter about them appeared in 1816.

Explanations

L1 human

Write all fractions between $0$ and $1$ with denominators up to $n$, in lowest terms and in increasing order. Neighbouring fractions in this list are always very close in a precise sense: their cross difference is $1$.