Stern-Brocot 树与 Farey 序列

What · 是什么

Stern-Brocot 树是一棵以 0/1、1/0（表示 +∞）为边界、通过反复插入相邻分数中位分数 (a+c)/(b+d) 构造的无限二叉搜索树，包含全部正的最简有理数且每个恰好出现一次。每个节点对应一个三元组 ((a/b),(p/q),(c/d))，实际存储的分数是中间元素 p/q。三条基本性质：①单调性——第 k 阶 Stern-Brocot 序列单调递增；②最简性——相邻分数满足 bc−ad=1（因此由裴蜀定理所有分数互素）；③完全性——任意正有理数都在树上（否则搜索无限长，可证明每一步 a+b+c+d 严格增大而 p+q 有界，矛盾）。Stern-Brocot 树同时是分子分母的二叉搜索树、堆与笛卡尔树。每个分数 p/q 可由连分数 [t0;t1;…;tn;1] 表示，连分数系数恰好编码从根到该节点的路径（偶数项向右、奇数项向左）。Farey 序列 F(n) 是分母不超过 n 的 0..1 间既约分数按序排列，可从 Stern-Brocot 树裁剪得到，长度 L(n)=1+Σ_{k=1}^n φ(k)。矩阵视角：左/右子节点移动分别对应乘以 L=[[1,1],[0,1]] 与 R=[[1,0],[1,1]]。

Why · 为什么

How · 实现

伪代码

# 朴素查找: O(p+q), 每步一次中位数比较
bounds = (0/1, 1/0)
while True:
    m = mediant(l, r)
    if m == target: break
    if target < m: r = m; path += 'L'
    else:          l = m; path += 'R'

# 快速查找(目标分数已知): O(log min(p,q)), 连分数/辗转相除
res = []
right = True
while q:
    res.append((p // q, 'R' if right else 'L'))
    p, q = q, p % q
    right ^= 1
res[-1].first -= 1   # 最后一个系数减 1

# Farey 序列长度: L(n) = 1 + sum phi(k)

Python 实现

# -*- coding: utf-8 -*-
# Stern-Brocot 树：朴素查找（O(p+q) 路径串）
def stern_naive(p, q):
    """返回从根到 p/q 的路径串（'L'/'R'）。"""
    # 边界 (pa/pb, qa/qb) = (0/1, 1/0)
    pa, pb, qa, qb = 0, 1, 1, 0
    res = []
    while True:
        pm, qm = pa + qa, pb + qb
        if pm == p and qm == q:
            break
        if p * qm < pm * q:          # p/q < pm/qm -> 向左
            qa, qb = pm, qm
            res.append('L')
        else:                        # 否则向右
            pa, pb = pm, qm
            res.append('R')
    return ''.join(res)


# 快速查找：连分数/辗转相除得到游程编码（目标分数已知）
def stern_fast(p, q):
    """返回 [(次数, 方向)]，方向交替，复杂度 O(log min(p,q))。"""
    res = []
    right = True
    while q:
        res.append((p // q, 'R' if right else 'L'))
        p, q = q, p % q
        right ^= 1
    res[-1] = (res[-1][0] - 1, res[-1][1])   # 最后一个系数减 1
    return res


# Farey 序列长度 L(n) = 1 + sum_{k=1}^n phi(k)
def farey_len(n):
    phi = list(range(n + 1))
    for i in range(2, n + 1):
        if phi[i] == i:
            for j in range(i, n + 1, i):
                phi[j] -= phi[j] // i
    return 1 + sum(phi[1:])


if __name__ == '__main__':
    # 朴素与快速查找在随机互素小数据上对拍
    import random
    for _ in range(300):
        p = random.randint(1, 40)
        q = random.randint(1, 40)
        g = __import__('math').gcd(p, q)
        p, q = p // g, q // g          # 只有最简分数在树上
        a = stern_naive(p, q)
        b = []
        for cnt, dd in stern_fast(p, q):
            b.extend(dd * cnt)
        assert ''.join(b) == a, (p, q, b, a)
    # 已知小例子
    assert stern_naive(1, 2) == 'L'
    assert stern_naive(2, 1) == 'R'
    assert stern_naive(1, 1) == ''
    assert stern_naive(3, 5) == 'LRL'
    # Farey 序列长度 F(5)=11, F(6)=13, F(10)=33
    assert farey_len(5) == 11, farey_len(5)
    assert farey_len(6) == 13
    assert farey_len(10) == 33
    print('stern-brocot tests passed')

易错点

• 1/0 不是分数而是 +∞ 的记号，作为右边界参与中位数计算但不能输出
• 中位分数 (a+c)/(b+d) 的分子分母分别相加即可，不必约分（行列式性质保证互素）
• 朴素查找路径长度可达 O(p+q)（如 1/n 的情形），大分数必须用连分数快速查找
• 连分数编码最后一项系数要减 1（[t0;t1;…;tn;1] 中末尾的 1），漏掉会错位
• 对无理数逼近时近似序列误差不是严格递减的，结尾要比较左右端点距目标的距离
• Farey 序列含 0/1 与 1/1 两个端点，长度公式 1+Σφ 的 1 是端点 0/1

例题

信源

• OI Wiki✓ https://oi-wiki.org/math/number-theory/stern-brocot/
• CP-Algorithms✓ https://cp-algorithms.com/others/stern_brocot_tree_farey_sequences.html