Stern-Brocot 树与 Farey 序列

Stern-Brocot 树

Stern-Brocot 树是一种维护分数的优雅的结构。它分别由 Moritz Stern 在 1858 年和 Achille Brocot 在 1861 年发现这个结构。

概述

Stern-Borcot 树从两个简单的分数开始：

这个 可能看得你有点懵逼。不过我们不讨论这方面的严谨性，你只需要把它当作 就行了。

每次我们在相邻的两个分数 中间插入一个分数 ，这样就完成了一次迭代，得到下一个序列。于是它就会变成这样

既然我们称它为 Stern-Brocot 树，那么它总得有一个树的样子对吧。来一张图：

你可以把第 层的序列当作是深度为 的 Stern-Brocot 树的中序遍历。

性质

接下来讨论一下 Stern-Brocot 树的性质。

单调性

在每一层的序列中，真分数是单调递增的。

略证：只需要在 的情况下证明

就行了。这个很容易，直接做一下代数变换即可

另一边同理可证。

最简性

序列中的分数（除了 ）都是最简分数。

略证：为证明最简性，我们首先证明对于序列中连续的两个分数 ：

显然，我们只需要在 的条件下证明 的情况成立即可。

后半部分同理。证明了这个，利用扩展欧几里德定理，如果上述方程有解，显然 。这样就证完了。

有了上面的证明，我们可以证明 。

有了这两个性质，你就可以把它当成一棵平衡树来做了。建立和查询就向平衡树一样做就行了。

实现

构建实现

1
2
3
4
5
6
7
8

// C++ Version
void build(int a = 0, int b = 1, int c = 1, int d = 0, int level = 1) {
  int x = a + c, y = b + d;
  // ... output the current fraction x/y
  // at the current level in the tree
  build(a, b, x, y, level + 1);
  build(x, y, c, d, level + 1);
}

1
2
3
4
5
6
7

# Python Version
def build(a = 1, b = 1, c = 1, d = 0, level = 1):
    x = a + c; y = b + d
    # ... output the current fraction x/y
    # at the current level in the tree
    build(a, b, x, y, level + 1)
    build(x, y, c, d, level + 1)

查询实现

1
2
3
4
5
6
7
8
9

// C++ Version
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

# Python Version
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)

Farey 序列

Stern-Brocot 树与 Farey 序列有着极其相似的特征。第 个 Farey 序列记作 ，表示把分母小于等于 的所有最简真分数按大小顺序排列形成的序列。

显然，上述构建 Stern-Brocot 树的算法同样适用于构建 Farey 序列。因为 Stern-Brocot 树中的数是最简分数，因此在边界条件（分母）稍微修改一下就可以形成构造 Farey 序列的代码。你可以认为 Farey 序列 是 Stern-Brocot 第 次迭代后得到的序列的子序列。

Farey 序列同样满足最简性和单调性，并且满足一个与 Stern-Brocot 树相似的性质：对于序列中连续的三个数 ，有 。这个可以轻松证明，不再赘述。

由 Farey 序列的定义，我们可以得到 的长度 公式为：

中间分数

对于 ，记中间分数为

中间分数还包含这样的分数：

这些中间分数介于 与 之间。

对于给定的 ，第 个中间分数 与最后一个中间分数 是渐进分数。

对比上述表达式与

可以得到 。因此，中间分数也是某个连分数展开的渐进分数，中间分数表达式的分子分母也一定互素。

两个相邻中间分数的差为

对于确定的 ，中间分数随着 的增加递增或递减。

定理：对实数 与渐进分数 ，有

证明：

一种证法可以定量计算。根据连分数中的定理有

由于

因此

取倒数即证毕。

另一种证法使用中间分数。首先，两个相邻渐进分数之间的距离有

由于 本身介于两个相邻渐进分数之间，到其中一个渐进分数的距离 一定小于 。不等式右边即证毕。

对于不等式左边，由于对于固定的 ，两头的中间分数就是渐进分数，因此有位置关系

因此有距离关系

更换下标，不等式左边即证毕。

在使用中这个定理经常放缩一下。由于 ，有

右半部分 无需计算更高阶的渐进分数，很常用，即下文 Dirichlet 逼近定理的连分数证法。

Dirichlet 逼近定理

Dirichlet 逼近定理是说，对于任意的一个无理数 ，均能找到无穷个有理数逼近它，满足不等式：

由于任一实数 到最近的整数距离不超过 ，显然存在整数 和 使得

Dirichlet 逼近定理将右侧优化到了 。等价的写法， 总有解。

当 是无理数的时候，可以让渐进分数的分母任意大， 任意小。

另外还有瓦伦定理：实数 连续两个渐进分数至少有一个满足 ，由瓦伦（Vahlen）在 1895 年证明。

另外还有伯雷尔定理：实数 连续两个渐进分数至少有一个满足 ，由伯雷尔（Borel）在 1903 年证明。

这个 是最优的，在无理数为例如黄金分割 等连分数展开自某位起均为 的时候取等。这些后续的定理也同样表明，在 Dirichlet 逼近定理中的小于等于号事实上也可以是小于号。

另外还有定理：实数 连分数展开无穷项不小于 ，则存在无穷多渐进分数满足 。这种条件的极端情形例如 。

其他的，还有 Kronecker 逼近定理：

如果 为无理数， 为实数，则对任意正数 , 存在整数 和整数 ，使得：

Dirichlet 逼近定理和 Kronecker 逼近定理，都可以用抽屉原理来解决。事实上，正是 Dirichlet 为了解决 Pell 方程，研究有理数逼近条件，抽屉原理才在历史上被第一次正式提出。

当然，采用抽屉原理的证明可以发现，下文中提到的最佳逼近有理数列，每项满足定理中右边改成分母为一次式的不等式。

进一步有结论，渐进有理数列中，每一项均满足 Dirichlet 逼近定理的不等式。

最佳有理逼近

讨论如何用有理数“最佳地”逼近无理数，不妨假设无理数落入 区间。

“最佳”一词的概念：选定的有理数必须保证，比它与无理数的距离更近的有理数，分母都比它大。不存在分母比它小的有理数，到给定无理数的距离更近。

最佳有理数：在 Farey 数列的某一行中，与给定无理数距离最近的那个有理数。

这个有理数可能在下面几行依旧与无理数“距离最近”，但一定有某一行，会找到一个新的有理数，与无理数距离更近。因此去重复后可以得到 最佳逼近有理数列，分母严格递增，距离递减。

更加严谨的叙述为：

对实数 和有理数 ，如果对于任意的整数 和整数 ，，均有

则称 是 的一个最佳有理逼近。

比无理数大的称为上逼近，否则为下逼近。由于无理数和有理数之间一定有有理数，最佳逼近有理数列必然为若干个上逼近，之后若干个下逼近，交替进行的形式。

有结论：

渐进分数必然为最佳有理逼近。

偶项渐进分数全都是下逼近，奇项渐进分数全都是上逼近。渐进分数列是下上交错的逼近。

在最佳逼近有理数列中，渐进分数是下上关系改变之前的倒数第一个数。如果将最佳逼近有理数列都写成有限简单连分数，那么在渐进分数之后（下上关系改变之后），连分数长度加一。

例如， 是 减去 的一个渐进分数。

那么它的渐进分数列是：

它的最佳逼近有理数列是：

从每个渐进分数（不包含）开始，到下一个渐进分数（包含）为止，同为上逼近，或同为下逼近。

在最佳逼近列中，每一个最佳分数是上一个最佳分数与再往前一个渐进分数的分子分母对应求和。

性质

定理：最佳有理逼近一定是中间分数。

它的逆定理并不成立，中间分数不一定是最佳有理逼近。

证明：

首先， 与 中必有一个是 的分母为 的最佳有理逼近。它们分别是 和 。其他分母更大的第一类最优逼近肯定介于这两个数中间。

当然，除非 为半奇数。这时两边距离一样， 没有分母为 的最佳有理逼近，不过这属于连分数太短的情况。

当 增加时，渐近分数从 和 两边向中间排布。由于 ，有分布

因为中间分数可以任意接近 ，从而任何一个不是中间分数的有理数 ，一定介于两个同阶的渐近分数 F{k,r} 与 F{k,r+1} 之间。其位置分布情况为：

于是有

另一方面， 与中间分数 ，有

因此有 。介于 和 之间的有理数，分母一定大于 的分母。由位置分布可以看出

分母更小的分数 到 的距离更近。因此，非中间分数的 不可能是最佳有理逼近。证毕。

渐进分数的等价性质

实数 的渐进分数 等价于这样的一类分数：

对于任意的整数 和整数 ，，均有

也就是

根据等价性，这可以直接作为渐进分数的另一个定义方法。这个性质比最佳逼近更加严格，因此根据这个性质，渐进分数必然为最佳逼近。

证明：

首先有 。对于一个非渐近分数的中间分数 ，有位置分布

于是有

即 。由于 ，因此 劣于比它分母更小的 。

接下来证明，满足这个条件的都是渐进分数。

首先，越高阶的渐近分数越靠近 ，具有严格单调性。如果有 ，就有 。

这是因为 ，有

整理即为上式。

接下来找出分母为 的满足上述性质的数，并指出它是渐进分数。

在给定 的时候，，并且取到最小的 最多只有两个取值。

当 在范围 遍历的时候，将上述的最小值继续比较其中的最小值，并记取到最小值中的最小值的多个 中，最小的 为 ，对应的 为 。

这里的 至多有两个，而事实上只有一个，可以证明其唯一性。唯一性的证明补在最后。

从上述选取方式可以看出 也满足定理的条件，因此它是一个渐进分数 。

又根据严格单调性，在 时无法取到最小，只能有 。

至此距离证毕只剩下 的唯一性。

如果给定 ，取到 的 不唯一，而是相邻的两个数，只能有 。此时记较小的一个为 。于是有

如果它们不互素，记 ，则有

使得 。这与上述选取方式中 的最小性矛盾。

此时将有理数 做连分数展开，则最后一个渐进分数的分子分母就是

由于 ，，得到 。于是

此时有更小的 可以取到最小值，仍旧与上述 的选取方式矛盾。证毕。

勒让德判别法

对实数 与分数 ，如果有

则 一定是 的渐近分数。

勒让德判别法的原始形式更加复杂，由勒让德（Legendre）于 1797 年发表在他的专著中。

勒让德判别法的原始表述是一个等价关系，这里给出的形式相对简化与宽松，是一个渐进分数的充分条件而非必要条件。

证明：

假设 不是渐进分数，则存在 ，且 使得