---
tag: 0PN4QJE969
kind: definition
name: Farey sequence
msc: [11B57]
defines: 0XRDYJQES6
uses: [02WF878BH1]
sources:
  - url: https://en.wikipedia.org/wiki/Farey_sequence
    locator: lead section
---

## 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|0VV04M41AN]].
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$.