Skip to content

Stern–Brocot Tree and Farey Sequence

Introduction

This article introduces data structures for storing reduced fractions and other related concepts. They are closely related to continued fractions and can be used in algorithm competitions to solve a series of number theory problems, and may also appear as implicit background in certain problems.

Stern–Brocot Tree

The Stern–Brocot tree is an elegant structure for maintaining fractions, containing all distinct positive rational numbers. This structure was independently discovered by Moritz Stern in 1858 and Achille Brocot in 1861.

Construction

Layer-by-Layer Construction

The Stern–Brocot tree can be obtained during the iterative construction of the \(k\)-th order Stern–Brocot sequence. The \(0\)-th order Stern–Brocot sequence consists of two simple fractions:

\[ \frac{0}{1},\ \frac{1}{0}. \]

Here, \(\dfrac{1}{0}\) is not strictly a rational fraction; it can be understood as the reduced fraction representing \(\infty\).

Between two adjacent fractions \(\dfrac{a}{b}\) and \(\dfrac{c}{d}\) in the \(k\)-th order Stern–Brocot sequence, insert their mediant1 \(\dfrac{a+c}{b+d}\) to obtain the \((k+1)\)-th order Stern–Brocot sequence. Although the definition of the mediant itself allows reduction of fractions, in the construction of the Stern–Brocot tree, it is sufficient to directly add the numerators and denominators separately without worrying about reduction. Thus, all orders of Stern–Brocot sequences can be iteratively constructed. The results of the first few iterations are as follows:

\[ \begin{array}{ccccccccc} &&&\dfrac{0}{1}, & \dfrac{1}{1}, & \dfrac{1}{0} &&&\\\\ &&\dfrac{0}{1}, & \dfrac{1}{2}, & \dfrac{1}{1}, & \dfrac{2}{1}, & \dfrac{1}{0} &&\\\\ \dfrac{0}{1}, & \dfrac{1}{3}, & \dfrac{1}{2}, & \dfrac{2}{3}, & \dfrac{1}{1}, & \dfrac{3}{2}, & \dfrac{2}{1}, & \dfrac{3}{1}, & \dfrac{1}{0} \end{array} \]

Connecting the newly added fractions from each iteration into a tree structure yields the Stern–Brocot tree. As shown in the figure below:

The \(k\)-th order Stern–Brocot sequence, excluding the endpoints, is the in-order traversal of the Stern–Brocot tree of depth \(k-1\).

Triple Construction

Another equivalent construction method uses the triple

\[ \left(\dfrac{0}{1},\dfrac{1}{1},\dfrac{1}{0}\right) \]

as the root node, and for each node

\[ \left(\dfrac{a}{b},\dfrac{p}{q},\dfrac{c}{d}\right) \]

adds

\[ \left(\dfrac{a}{b},\dfrac{a+p}{b+q},\dfrac{p}{q}\right),\ \left(\dfrac{p}{q},\dfrac{p+c}{q+d},\dfrac{c}{d}\right) \]

as left and right child nodes, respectively, to construct the entire Stern–Brocot tree. In the triple stored at each node of the Stern–Brocot tree, the actual fraction stored is the middle fraction \(\dfrac{p}{q}\), while the left and right fractions \(\dfrac{a}{b}\) and \(\dfrac{c}{d}\) are fractions that appeared earlier. Moreover, considering the previous construction, the fraction \(\dfrac{p}{q}\) is exactly obtained by inserting the mediant of \(\dfrac{a}{b}\) and \(\dfrac{c}{d}\).

Matrix Representation and Stern–Brocot Number System

The triple construction implies that each node on the Stern–Brocot tree corresponds to a matrix

\[ S = \begin{pmatrix} b & d\\ a & c \end{pmatrix}. \]

The root node of the Stern–Brocot tree is the identity matrix \(I\), and moving to the left child and right child corresponds to right-multiplying the current node matrix by matrices

\[ L=\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix},~ R=\begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}. \]

The actual fraction corresponding to each node is \(f(S)=\dfrac{a+c}{b+d}\). The matrix \(S\) of each node can be written as a product of matrices \(L\) and \(R\), which can also be understood as a string composed of \(L\) and \(R\), representing the path from the root node to it. Representing all positive rational numbers uniquely as such strings can be seen as obtaining a representation of positive rational numbers, hence it is also called the Stern–Brocot number system.

Implementation of Tree Construction

The tree construction algorithm simply simulates the above process. Below is the code for performing an in-order traversal of the Stern–Brocot tree for the first \(n\) layers.

Tree Construction 
1
2
3
4
5
6
7
8
// In-Order Transversal of Stern-Brocot Tree till Layer N.
void build(int n, int a = 0, int b = 1, int c = 1, int d = 0, int level = 1) {
  if (level > n) return;  // Only first n layers.
  int x = a + c, y = b + d;
  build(n, a, b, x, y, level + 1);
  std::cout << x << '/' << y << ' ';  // Output the current fraction.
  build(n, x, y, c, d, level + 1);
}

1
2
3
4
5
6
7
8
# In-Order Transversal of Stern-Brocot Tree till Layer N.
def build(n, a=0, b=1, c=1, d=0, level=1):
    if level > n:
        return
    x, y = a + c, b + d
    build(n, a, b, x, y, level + 1)
    print(f"{x}/{y}", end=" ")
    build(n, x, y, c, d, level + 1)

The complexity of the tree construction algorithm is \(O(n^2)\).

Properties

Next, we discuss the properties of the Stern–Brocot tree. In short, the Stern–Brocot tree is a binary search tree containing all positive reduced rational fractions, it is also a heap of numerators and denominators, and a Cartesian tree of pairs formed by denominators and numerators. Considering the intervals formed by the left and right endpoints in the triple construction mentioned earlier, the Stern–Brocot tree can also be seen as a segment tree on \([0,\infty]\). These statements can be derived from the following three fundamental properties:

Monotonicity

In the construction above, the fractions at each layer are monotonically increasing. This can be proven by induction. Because if \(\dfrac{a}{b} < \dfrac{c}{d}\), then necessarily

\[ \dfrac{a}{b} < \dfrac{a+c}{b+d} < \dfrac{c}{d}. \]

This can be derived by clearing denominators in the inequality. The induction base is \(\dfrac{0}{1} < \dfrac{1}{0}\), and monotonicity obviously holds.

Reducedness

In the construction above, each fraction is reduced. Similarly, we need to prove by induction that in the construction above, for each layer, adjacent fractions \(\dfrac{a}{b}\) and \(\dfrac{c}{d}\) satisfy the equation

\[ bc-ad = \det\begin{pmatrix} b & d\\ a & c \end{pmatrix} = 1. \]

At the root node, it is the identity matrix, which obviously holds. When moving downward, the matrices \(L\) and \(R\) multiplied have determinant \(1\). According to the properties of determinants, it follows that at the next layer, we also have

\[ \det\begin{pmatrix}b & b+d \\ a & a+c \end{pmatrix} = \det\begin{pmatrix}b+d & d \\ a+c & c\end{pmatrix} = 1. \]

For the induction base \(\dfrac{0}{1}\) and \(\dfrac{1}{0}\), this is also obvious. Thus, by Bézout's theorem, it necessarily follows that the numerator and denominator of each fraction are coprime, i.e., all fractions are reduced.

Completeness

Finally, we need to show that the Stern–Brocot tree includes all positive reduced fractions. Because the first two properties already show that the Stern–Brocot tree is a binary search tree, and any positive reduced fraction \(\dfrac{p}{q}\) must lie between \(\dfrac{0}{1}\) and \(\dfrac{1}{0}\). According to the search method on a binary search tree, the only possibility for \(\dfrac{p}{q}\) not to be in the binary search tree is that the search process is infinitely long. This is impossible.

Suppose we already know

\[ \dfrac{a}{b} < \dfrac{p}{q} < \dfrac{c}{d}, \]

then necessarily

\[ bp-aq \ge 1,\ cq-dp \ge 1. \]

Multiplying the two inequalities by \((c+d)\) and \((a+b)\) respectively, we obtain

\[ (c+d)(bp-aq) + (a+b)(cq-dp) \ge a+b+c+d. \]

Using the previously established equation \(bc-ad=1\), we have

\[ p+q \ge a+b+c+d. \]

Each time the search goes one level deeper, the right side of the equation strictly increases, while the left side remains unchanged. Therefore, the search must stop within a finite number of steps.

Finding Fractions

In practical applications of the Stern–Brocot tree, it is often necessary to query the position of a given fraction in the Stern–Brocot tree.

Naive Algorithm

Since the Stern–Brocot tree is a binary search tree, we can determine the path from the root node to a given fraction by comparing the size relationship between the current fraction and the target fraction. Denoting moving to the left child and right child as \(L\) and \(R\) respectively, each path corresponds to a string composed of \(L\) and \(R\), which is the representation of the rational number in the Stern–Brocot number system mentioned above. The process of finding the path to a rational number is equivalent to obtaining the representation of that rational number in the Stern–Brocot number system.

The implementation of the naive fraction finding algorithm is as follows:

Naive Fraction Finding 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// Locate a given fraction in the Stern-Brocot tree.
std::string find(int x, int y, int a = 0, int b = 1, int c = 1, int d = 0) {
  int m = a + c, n = b + d;
  if (x == m && y == n) return "";
  if (x * n < y * m) {
    return 'L' + find(x, y, a, b, m, n);
  } else {
    return 'R' + find(x, y, m, n, c, d);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
# Locate a given fraction in the Stern-Brocot tree.
def find(x, y, a=0, b=1, c=1, d=0):
    m = a + c
    n = b + d
    if x == m and y == n:
        return ""
    if x * n < y * m:
        return "L" + find(x, y, a, b, m, n)
    else:
        return "R" + find(x, y, m, n, c, d)

The complexity of the algorithm is \(O(p+q)\), making it impractical for algorithm competitions.

In the Stern–Brocot number system, each positive irrational number corresponds to a unique infinite string. The same algorithm can be used to construct this string. Each prefix of this infinite string corresponds to a reduced rational fraction. Arranging these reduced fractions in a sequence, the denominators of the fractions in the sequence are strictly increasing, and the limit of the sequence is that irrational number. Therefore, the Stern–Brocot tree can be used to find rational approximations of any precision for an irrational number. However, it should be noted that the difference between this rational sequence and the irrational number is not strictly decreasing. For a rigorous theory of rational approximation, refer to the Diophantine approximation section on the continued fractions page. In practical applications of the Stern–Brocot tree to find the best approximation of a real number within a denominator limit, one should finally compare the distances from the left and right interval endpoints to that real number.

Fast Algorithm

The naive algorithm for finding fractions is not efficient, but a simple optimization yields a fast finding algorithm with complexity \(O(\log(p+q))\). The key optimization is to merge consecutive \(L\) and \(R\) moves.

If the target fraction \(\dfrac{p}{q}\) falls between \(\dfrac{a}{b}\) and \(\dfrac{c}{d}\), then when moving right \(t\) times consecutively, the right boundary remains unchanged, while the left node moves to \(\dfrac{a+tc}{b+td}\); conversely, when moving left \(t\) times consecutively, the left boundary remains unchanged, while the right node moves to \(\dfrac{ta+c}{tb+d}\). Therefore, the number of right and left moves can be directly determined by \(\dfrac{a+tc}{b+td}<\dfrac{p}{q}\) or \(\dfrac{p}{q}<\dfrac{ta+c}{tb+d}\). Here, strict inequality is used because the algorithm moves the left and right endpoints, and the fraction being sought appears as the mediant of the finally obtained endpoints.

Fast Fraction Finding 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
// Locate a given fraction in the Stern-Brocot tree.
auto find(int x, int y) {
  std::vector<std::pair<int, char>> res;
  int a = 0, b = 1, c = 1, d = 0;
  bool right = true;
  while (x != a + c || y != b + d) {
    if (right) {
      auto t = (b * x - a * y - 1) / (y * c - x * d);
      res.emplace_back(t, 'R');
      a += t * c;
      b += t * d;
    } else {
      auto t = (y * c - x * d - 1) / (b * x - a * y);
      res.emplace_back(t, 'L');
      c += t * a;
      d += t * b;
    }
    right ^= 1;
  }
  return res;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
# Locate a given fraction in the Stern-Brocot tree.
def find(x, y):
    res = []
    a, b, c, d = 0, 1, 1, 0
    right = True
    while x != a + c or y != b + d:
        if right:
            t = (b * x - a * y - 1) // (y * c - x * d)
            res.append((t, "R"))
            a += t * c
            b += t * d
        else:
            t = (y * c - x * d - 1) // (b * x - a * y)
            res.append((t, "L"))
            c += t * a
            d += t * b
        right ^= 1
    return res

The current finding algorithm requires the fraction \(\dfrac{p}{q}\) to be known. If the target fraction is unknown, it is often necessary to perform a doubling search or binary search on the number of moves each time moving right or left. In this case, the complexity of the fraction finding algorithm is \(O(\log^2(p+q))\).

Algorithm Based on Continued Fractions

For the case where the fraction is known, a simpler algorithm can be given using continued fractions. Assume without loss of generality that the first group of moves is to the right; if not, set the number of moves in the first group to zero. Alternately moving the endpoints right and left, arrange the endpoint positions after each group of moves as follows:

\[ \dfrac{p_0}{q_0},~\dfrac{p_1}{q_1},~\dfrac{p_2}{q_2},~\cdots,~\dfrac{p_{n-2}}{q_{n-2}},~\dfrac{p_{n-1}}{q_{n-1}},~\dfrac{p_n}{q_n}. \]

Here, even-indexed groups of moves are to the right, so they record the position of the left endpoint; odd-indexed groups of moves are to the left, so they record the position of the right endpoint. Add two more endpoints before this sequence:

\[ \dfrac{p_{-2}}{q_{-2}}=\dfrac{0}{1},~\dfrac{p_{-1}}{q_{-1}}=\dfrac{1}{0}. \]

Let the number of moves in the \(k\)-th group be \(t_k\). Then, according to the relationship between the number of moves and endpoint positions obtained above, we have

\[ \dfrac{p_k}{q_k} = \dfrac{t_kp_{k-1}+p_{k-2}}{t_kq_{k-1}+q_{k-2}}. \]

According to the recurrence relation of continued fractions, we know that the endpoint

\[ \dfrac{p_k}{q_k} = [t_0,t_1,\cdots,t_k]. \]

The final continued fraction obtained is

\[ \dfrac{p}{q} = \dfrac{p_k+p_{k-1}}{q_k+q_{k-1}} = [t_0,t_1,\cdots,t_{n-1},t_n,1]. \]

Therefore, in the continued fraction representation of the target fraction ending with one, excluding the final one, the preceding terms encode the path from the root node to the current node in the Stern–Brocot tree. Among them, even-indexed terms (starting from index \(0\)) correspond to edges to the right child, and odd-indexed terms correspond to edges to the left child.

The continued fraction representation of a rational number can be obtained by the Euclidean algorithm, so the complexity of the fraction finding algorithm based on continued fraction representation is \(O(\log\min\{p,q\})\).

Fraction Finding Based on Continued Fractions 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
// Locate a given fraction in the Stern-Brocot tree.
auto find(int x, int y) {
  std::vector<std::pair<int, char>> res;
  bool right = true;
  while (y) {
    res.emplace_back(x / y, right ? 'R' : 'L');
    x %= y;
    std::swap(x, y);
    right ^= 1;
  }
  --res.back().first;
  return res;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
# Locate a given fraction in the Stern-Brocot tree.
def find(x, y):
    res = []
    right = True
    while y:
        res.append([x // y, ("R" if right else "L")])
        x, y = y, x % y
        right ^= 1
    res[-1][0] -= 1
    return res

Using the continued fraction representation, the parent node and child nodes of a node can be simply expressed. For node \([t_0,t_1,\cdots,t_n,1]\), its parent node is the node obtained by moving one step less in the last direction: when \(t_k>1\), the parent node is \([t_0,t_1,\cdots,t_n - 1,1]\); otherwise, the parent node is \([t_0,t_1,\cdots,t_{n-1},1]\). Its two child nodes are \([t_0,t_1,\cdots,t_n+1,1]\) and \([t_0,t_1,\cdots,t_n,1,1]\) respectively; which one is the left child and which is the right child depends on the parity of \(n\).

Calkin–Wilf Tree

Another simpler structure for storing positive rational fractions is the Calkin–Wilf tree. It is usually depicted as follows:

pic

The root node of the tree is \(\dfrac{1}{1}\). Then, for a node containing fraction \(\dfrac{p}{q}\), its left and right children are \(\dfrac{p}{p+q}\) and \(\dfrac{p+q}{q}\) respectively. Similar to the Stern–Brocot tree, each fraction in it is reduced, and it includes every positive reduced fraction exactly once.

Relation to Continued Fractions

Unlike the Stern–Brocot tree, the Calkin–Wilf tree is not a binary search tree, so it cannot be used for binary search of rational numbers.

In the Calkin–Wilf tree, when \(p>q\), the parent node of fraction \(\dfrac{p}{q}\) is \(\dfrac{p-q}{q}\); when \(p<q\), it is \(\dfrac{p}{q-p}\). For the first case, starting from \(\dfrac{p}{q}\), it is the right child of its parent node, and we can move upward along the parent's right side until the numerator is no longer greater than the denominator. At that point, the fraction stored at the node is \(\dfrac{p\bmod q}{q}\), and the number of moves in this group is \(\left\lfloor\dfrac{p}{q}\right\rfloor\); for the second case, it is the left child of its parent node, and we can move upward along the parent's left side until the denominator is no longer greater than the numerator. At that point, the fraction stored at the node is \(\dfrac{p}{q\bmod p}\), and the number of moves in this group is \(\left\lfloor\dfrac{q}{p}\right\rfloor\).

Using the language of continued fractions, let the current node store the remainder \(s_k\) of some continued fraction. Then moving upward along the parent's right side \(\lfloor s_k\rfloor\) times reaches the fraction \(\dfrac{1}{s_{k+1}}\), and then moving upward along the parent's left side \(\lfloor s_{k+1}\rfloor\) times reaches the fraction \(s_{k+2}\). Therefore, the path from node \(s_0=\dfrac{p}{q}\) upward to the root node \(\dfrac{1}{1}\) is encoded by the continued fraction \([t_0,t_1,\cdots,t_n,1]\): excluding the final \(1\), even-indexed terms (starting from index \(0\)) represent the number of moves along the parent's right side, and odd-indexed terms represent the number of moves along the parent's left side.

For the node containing fraction \(\dfrac{p}{q}=[t_0,t_1,\cdots,t_n,1]\), its parent node has the following representation:

  1. When \(t_0>0\), its parent node is \(\dfrac{p-q}{q}=[t_0 - 1, t_1, \cdots, t_n,1]\);
  2. When \(t_0=0\) and \(t_1>1\), its parent node is \(\dfrac{p}{q-p} = [0, t_1 - 1, t_2, \cdots, t_n,1]\);
  3. When \(t_0=0\) and \(t_1=1\), its parent node is \(\dfrac{p}{q-p} = [t_2, t_3, \cdots, t_n,1]\).

Conversely, its child nodes are \(\dfrac{p+q}{q}=[t_0+1,t_1,\cdots,t_n,1]\) and \(\dfrac{p}{p+q}=[0,1,t_0,t_1,\cdots,t_n,1]\) respectively. For the continued fraction representation of the second child node, when \(t_0=0\), it should be understood as \([0,1+t_1,\cdots,t_n,1]\).

Relation to Stern–Brocot Tree

Similarly establishing a connection with continued fractions, the nodes on the path in the Stern–Brocot tree exhibit the recurrence relation of convergents, while the nodes on the path in the Calkin–Wilf tree exhibit the recurrence relation of remainders. The continued fraction representation of the same fraction is fixed, so the encoding of the path from it to the root node in the Calkin–Wilf tree is exactly the same as the encoding of the path from the root node to it in the Stern–Brocot tree. However, because the directions of the paths are opposite, although the fractions stored at the same layer in the Stern–Brocot tree and the Calkin–Wilf tree are the same, their positions are different.

If we perform breadth-first search on both trees and number the nodes sequentially, with the root node numbered \(1\), then the left and right children of node numbered \(v\) are \(2v\) and \(2v+1\) respectively. From the binary representation of the number, excluding the leading \(1\), each \(1\) from high to low represents a move to the right child, and each \(0\) represents a move to the left child. On the Calkin–Wilf tree, the node number of the rational number represented by the continued fraction \([t_0,t_1,\cdots,t_n,1]\) is

\[ 1\cdots \underbrace{0\cdots 0}_{t_3}\underbrace{1\cdots 1}_{t_2}\underbrace{0\cdots 0}_{t_1}\underbrace{1\cdots 1}_{t_0}. \]

Correspondingly, on the Stern–Brocot tree, the node number of the rational number represented by the continued fraction \([t_0,t_1,\cdots,t_n,1]\) is

\[ 1\underbrace{1\cdots 1}_{t_0}\underbrace{0\cdots 0}_{t_1}\underbrace{1\cdots 1}_{t_2}\underbrace{0\cdots 0}_{t_3}\cdots. \]

Removing the initial \(1\), the remaining binary bits form a number that is exactly the left-to-right index of the vertex at the same layer (starting from \(0\)). This derivation shows that the arrangement of fractions at the same layer in the Stern–Brocot tree and the Calkin–Wilf tree are bit-reversal permutations of each other, i.e., the permutation on \(0\sim (2^k-1)\) obtained by reversing the binary digits (padding with leading zeros) of the index.

Because of this, nodes on the Stern–Brocot tree are sometimes numbered according to the corresponding node numbers on the Calkin–Wilf tree, resulting in the numbering shown in the figure below:

pic

This numbering can be constructed recursively: the root node is numbered \(1\), each time moving to the left child, replace the leading \(1\) with \(10\), and when moving to the right child, replace the leading \(1\) with \(11\). Reading the number from right to left gives the path from the root node to that node.

Stern Diatomic Sequence

Arranging all fractions in the Calkin–Wilf tree in the order of breadth-first search numbering, or arranging all fractions in the Stern–Brocot tree according to the numbering shown in the above figure, yields the following sequence:

\[ \frac{1}{1},~\dfrac{1}{2},~\dfrac{2}{1},~\dfrac{1}{3},~\dfrac{3}{2},~\dfrac{2}{3},~\dfrac{3}{1},~\dfrac{1}{4},~\dfrac{4}{3},~\dfrac{3}{5},~\dfrac{5}{2},\cdots. \]

Using the construction process of the Calkin–Wilf tree, it can be proven that in this sequence, the denominator of the previous fraction must equal the numerator of the next fraction. Listing the numerators separately gives the Stern diatomic sequence (OEIS A002487), also known as the Stern–Brocot sequence. The numbering of the above sequence starts from \(1\), and it is additionally stipulated that the \(0\)-th number is \(0\).

Let \(a_n\) be the \(n\)-th number in the Stern diatomic sequence. Then it satisfies the following recurrence relation:

\[ \begin{aligned} a_{2n} &= a_n,\\ a_{2n+1} &= a_n + a_{n+1}. \end{aligned} \]

The base cases are \(a_0=0\) and \(a_1=1\). To find the value of \(a_n\) in the Stern diatomic sequence, directly using the recurrence relation has complexity \(O(\log^2n)\), which is not optimal. A better approach is to treat it as the numerator of the fraction with index \(n\) in the Calkin–Wilf tree and solve using the recurrence relation based on continued fractions described above, with complexity \(O(\log n)\).

Farey Sequence

Farey sequences have extremely similar characteristics to the Stern–Brocot tree. Denote the Farey sequence of order \(n\) as \(F_n\). It represents the sequence formed by arranging all reduced fractions between \([0,1]\) with denominators less than or equal to \(n\) in increasing order:

\[ \begin{array}{lllllllllllll} F_1=\bigg\{&\dfrac{0}{1},&&&&&&&&&&\dfrac{1}{1}&\bigg\}\\\\ F_2=\bigg\{&\dfrac{0}{1},&&&&&\dfrac{1}{2},&&&&&\dfrac{1}{1}&\bigg\}\\\\ F_3=\bigg\{&\dfrac{0}{1},&&&\dfrac{1}{3},&&\dfrac{1}{2},&&\dfrac{2}{3},&&&\dfrac{1}{1}&\bigg\}\\\\ F_4=\bigg\{&\dfrac{0}{1},&&\dfrac{1}{4},&\dfrac{1}{3},&&\dfrac{1}{2},&&\dfrac{2}{3},&\dfrac{3}{4},&&\dfrac{1}{1}&\bigg\}\\\\ F_5=\bigg\{&\dfrac{0}{1},&\dfrac{1}{5},&\dfrac{1}{4},&\dfrac{1}{3},&\dfrac{2}{5},&\dfrac{1}{2},&\dfrac{3}{5},&\dfrac{2}{3},&\dfrac{3}{4},&\dfrac{4}{5},&\dfrac{1}{1}&\bigg\} \end{array} \]

According to the definition of Farey sequences, they naturally satisfy monotonicity, reducedness, and completeness. As shown in the figure above, the new fractions added in \(F_k\) compared to \(F_{k-1}\) are always the mediants of adjacent fractions in \(F_{k-1}\).

The algorithm for constructing the Stern–Brocot tree described above also applies to constructing Farey sequences. Since the Stern–Brocot tree includes all reduced fractions, by modifying the boundary conditions to restrict denominators, we obtain code for constructing Farey sequences. The \(n\)-th order Farey sequence \(F_n\) can be viewed as a subsequence of the \((n-1)\)-th order Stern–Brocot sequence.

Constructing Farey Sequence 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
// Farey Sequence of Order N.
void build(int n, int a = 0, int b = 1, int c = 1, int d = 1,
           bool init = true) {
  int x = a + c, y = b + d;
  if (y > n) return;              // Only first n layers.
  if (init) std::cout << "0/1 ";  // Output 0/1;
  build(n, a, b, x, y, false);
  std::cout << x << '/' << y << ' ';  // Output the current fraction.
  build(n, x, y, c, d, false);
  if (init) std::cout << "1/1 ";  // Output 1/1;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
# Farey Sequence of Order N.
def build(n, a=0, b=1, c=1, d=1, init=True):
    x, y = a + c, b + d
    if y > n:
        return
    if init:
        print("0/1", end=" ")
    build(n, a, b, x, y, False)
    print(f"{x}/{y}", end=" ")
    build(n, x, y, c, d, False)
    if init:
        print("1/1", end=" ")

Directly constructing the Farey sequence has complexity \(O(|F_n|)=O(n^2)\).

Sequence Length and Fraction Finding

The length of a Farey sequence can be derived recursively. Compared to \(F_{n-1}\), the additional fractions in sequence \(F_n\) all have denominator \(n\), and numerators not exceeding \(n\) and coprime with \(n\), thus:

\[ \begin{aligned} |F_n| &= |F_{n-1}| + \varphi(n) = 1 + \sum_{k=1}^n\varphi(k). \end{aligned} \]

Here, \(\varphi(n)\) is the Euler's totient function. This formula can be computed in \(O(n)\) using a linear sieve, and using the Dirichlet hyperbola method can reduce the complexity to \(O(n^{2/3})\).

Compared to directly computing the length of the sequence, a more common scenario is to find the index of a given fraction \(r=\dfrac{p}{q}\) in the sequence \(F_k\). This is equivalent to evaluating

\[ 1 + \sum_{k = 1}^n\sum_{i=1}^{\lfloor rk\rfloor}[i\perp k] = 1 + \sum_{d=1}^n\mu(d)\sum_{j=1}^{\lfloor n/d\rfloor}\lfloor rj\rfloor. \]

To obtain the right-hand side, Möbius inversion is applied. Combining linear sieve and enumerating divisors allows \(O(n)\) preprocessing and \(O(n\log n)\) queries; combining Dirichlet hyperbola method and Euclidean-like algorithm allows \(O(n^{2/3})\) preprocessing and \(O(\sqrt n\log n)\) queries.

Conversely, given an index to find the fraction requires binary search on real numbers in \([0,1]\), or binary search on the Stern–Brocot tree. The former may be limited by floating-point precision, with the number of queries on fraction indices being \(O(\log V)\), where \(V\) is the precision range; the latter is not limited by floating-point precision, but the number of queries on fraction indices is \(O(\log^2n)\).

Farey Neighbors

If fractions \(\dfrac{a}{b}\) and \(\dfrac{c}{d}\) are adjacent in some Farey sequence, they are called Farey neighbors, also known as a Farey pair.

Let \(\dfrac{a}{b}<\dfrac{c}{d}\). From the construction process of Farey sequences, the later added fraction between two adjacent fractions must be the mediant of the other fraction and its previous neighbor. Therefore, Farey neighbors are also adjacent in some order Stern–Brocot sequence. According to the conclusion proven in the reducedness section, we necessarily have

\[ bc-ad=1. \]

Conversely, this is also a sufficient condition for two reduced proper fractions to be Farey neighbors. Now we explain this. Without loss of generality, assume \(\dfrac{a}{b}\) is the one with the larger denominator among the two fractions. Then both fractions will appear in \(F_b\). Let \(\dfrac{e}{f}\) be the item to the right of \(\dfrac{a}{b}\) in sequence \(F_b\). By the necessity already shown, we have \(be-af=1\). However, the linear Diophantine equation \(bx-ay=1\) has only one positive integer solution with \(y\le b\), so necessarily \((e,f)=(c,d)\).

In fact, because the next reduced fraction that will appear between them must be \(\dfrac{a+c}{b+d}\), \(\dfrac{a}{b}\) and \(\dfrac{c}{d}\) are adjacent in Farey sequences from order \(\max\{b,d\}\) to order \((b+d-1)\).

The Farey neighbor relationships for denominators not exceeding \(9\) are shown in the following figure:

The circles in the figure are called Ford circles: for each reduced fraction \(\dfrac{p}{q}\) in \([0,1]\), draw a circle with center \(\left(\dfrac{p}{q},\dfrac{1}{2q^2}\right)\) and radius \(\dfrac{1}{2q^2}\). The illustration shows that the Ford circles corresponding to two fractions can only be tangent or disjoint, and two circles are tangent if and only if the two fractions are Farey neighbors. Moreover, for any two tangent circles in the figure, there always exists a unique third circle tangent to both. The fraction corresponding to this third circle is the mediant of the fractions corresponding to the two circles.

To verify that tangent circles always correspond to Farey neighbors, we can directly compute the distance between the centers:

\[ \left(\dfrac{a}{b}-\dfrac{c}{d}\right)^2 + \left(\dfrac{1}{2b^2}-\dfrac{1}{2d^2}\right)^2 = \left(\dfrac{1}{2b^2}+\dfrac{1}{2d^2}\right)^2+\frac{(bc-ad)^2-1}{b^2d^2}. \]

Since the two reduced fractions are not identical, \(|bc-ad|\ge 1\), so the two circles can only be tangent or disjoint. Moreover, they are tangent if and only if \(|bc-ad|=1\), which is equivalent to the two fractions being Ford neighbors.

Finally, to compute the number of Farey neighbor pairs. Except for \(\left(\dfrac{0}{1},\dfrac{1}{1}\right)\), the denominators of other Farey neighbors are different. Without loss of generality, let \(\dfrac{p}{q}\) be the one with the larger denominator. Then the other fraction must be a solution to the linear Diophantine equation

\[ qx-py=\pm 1. \]

Each equation has exactly one positive integer solution with \(y<q\), corresponding to the neighbor to the left and right of \(\dfrac{p}{q}\) respectively. Thus, each proper fraction in \((0,1)\) has two Farey neighbors with denominators smaller than its own, plus \(\dfrac{0}{1}\) and \(\dfrac{1}{1}\). This shows that there are a total of \((2|F_n|-3)\) Farey neighbor pairs in sequence \(F_n\).

Of course, the fractions \(\dfrac{a}{b}<\dfrac{c}{d}\) found in this process are exactly the left and right neighbors of \(\dfrac{p}{q}\) when it is inserted into the sequence. Therefore, they are already Farey neighbors and \(\dfrac{p}{q}\) is their mediant. Let \(\dfrac{p}{q}=[t_0,t_1,\cdots,t_n,1]\), then these two Farey neighbors with smaller denominators are \([t_0,t_1,\cdots,t_n]\) and \([t_0,t_1,\cdots,t_{n-1}]\) respectively.

To compute other Farey neighbors of the current fraction \(\dfrac{p}{q}\), simply use the extended Euclidean algorithm to find all eligible solutions.

Recurrence Relation

Farey sequences have a concise recurrence relation that allows sequentially computing all fractions of the \(n\)-th order Farey sequence from left to right.

First, the previous analysis indicates that in \(F_n\), the newly added term \(\dfrac{p}{n}\) is always the mediant of the two adjacent fractions. In fact, this relationship holds for all fractions in \(F_n\) (except the endpoints). Let \(\dfrac{a}{b}<\dfrac{p}{q}<\dfrac{c}{d}\). According to the necessary and sufficient condition for Farey neighbors, we always have

\[ bp-aq = 1 = cq-dp \iff \frac{p}{q} = \dfrac{a+c}{b+d}. \]

However, for the general case, the fraction \(\dfrac{a+c}{b+d}\) may need reduction.

Using this observation, we can construct the following recurrence relation. Let \(\dfrac{a}{b}\) and \(\dfrac{p}{q}\) be known, and we want to find the value of the third fraction \(\dfrac{c}{d}\). Then, there exists \(k\) such that

\[ a+c = kp,\ b+d=kq \]

holds. Because the difference

\[ \frac{kp-a}{kq-b} - \dfrac{p}{q} = \dfrac{bp-aq}{q(kq-b)} = \dfrac{1}{q(kq-b)} \]

decreases as \(k\) increases, and the fraction immediately following \(\dfrac{p}{q}\) should be the one with the smallest such difference among all fractions satisfying \(kq-d\le n\). Thus, necessarily

\[ k = \left\lfloor\dfrac{n+b}{q}\right\rfloor. \]

It can be verified that the fraction obtained in this way must be in \(F_n\). Therefore, the numerators and denominators of fractions in \(F_n\) satisfy the recurrence relation:

\[ \begin{aligned} p_k &= \left\lfloor\frac{n + q_{k-2}}{q_{k-1}}\right\rfloor p_{k-1} - p_{k-2},\\ q_k &= \left\lfloor\frac{n + q_{k-2}}{q_{k-1}}\right\rfloor q_{k-1} - q_{k-2}. \end{aligned} \]

The base cases are \((p_0,q_0)=(0,1)\) and \((p_1,q_1)=(1,n)\).

Exercises

Problems based on the material in this article:

Problems requiring binary search on the Stern–Brocot tree:

References and Notes

Part of this page is translated from the blog post Дерево Штерна-Броко. Ряд Фарея and its English translation The Stern-Brocot Tree and Farey Sequences. The Russian version is licensed under Public Domain + Leave a Link; the English version is licensed under CC-BY-SA 4.0. Another part of this page is translated from the blog post Continued fractions, licensed under CC-BY-SA 4.0. Content has been modified.

  1. The translation of the term comes from Section 4.5 of Concrete Mathematics translated by Zhang Mingyao and Zhang Fan. ↩

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用