连分数

引入

连分数可以将实数表示为一个收敛的有理数数列的极限。这个数列中的有理数易于计算，而且提供了这个实数的最佳逼近，因而在算法竞赛中常常会用到连分数。除此之外，连分数还和欧几里得算法密切相关，因而可以应用到一系列数论问题中。

连分数

连分数（continued fraction）本身只是一种形式记号。

有限连分数

对于数列 ，连分数 表示展开式

连分数有意义，当且仅当对应的展开式有意义。这些 称为连分数的 项（term）或 系数（coefficient）。

当然，连分数还可以推广到无穷数列的情形。

无限连分数

对于无穷数列 ，连分数 表示极限

连分数有意义，当且仅当对应的极限有意义。其中， 称为 的第 个 渐近分数（convergent）或 收敛子，而 称为 的第 个 余项 或 完全商（complete quotient）。相应地，项 有时也称为第 个 部分商（partial quotient）。

简单连分数

数论中，主要考虑连分数的项都是整数的情形。

除非特别说明，本文提到的连分数都指的是简单连分数。可以证明，无限的简单连分数必然是收敛的，而且简单连分数的余项也一定是正的。

连分数有如下基本性质：

有限连分数对应的是有理数。每个有理数都有且仅有两种方式可以表示成连分数，长度必然一奇一偶。这两种方式唯一的区别在于最后一项是否为 ，即

这两个连分数称为有理数 的 连分数表示（continued fraction representation）。其中，末项不为一的称为标准表示，末项为一的称为非标准表示。¹

例子

有理数 的连分数表示为

无限连分数对应的是无理数。而且，每个无理数仅有唯一的方式表示为连分数，称为无理数的连分数表示。

连分数表示的求法

要求某个实数 的连分数表示，只需要注意到它的余项 如果不是整数，就一定满足

而且，。因此，可以从 开始递归地计算

这个过程产生的数列 总是唯一确定的，除非某个余项 成为整数。如果出现了 是整数，则说明过程应当终止，可以选择输出相应的标准表示或者非标准表示。

在算法竞赛中，往往处理的都是有理数 的情形。此时，每个余项 都是有理数 ，而且对于 ，因为 ，就总有 。具体计算上述递推关系，可以发现

此时的计算过程实际上是对 和 做 辗转相除法。这也说明，对于有理数 ，连分数表示的长度是 的。计算有理数 的复杂度也是 的。

1
2
3
4
5
6
7
8
9

// Find the continued fraction representation of P/Q.
auto fraction(int p, int q) {
  std::vector<int> a;
  while (q) {
    a.push_back(p / q);
    std::tie(p, q) = std::make_pair(q, p % q);
  }
  return a;
}

1
2
3
4
5
6
7

# Find the continued fraction representation of P/Q.
def fraction(p, q):
    a = []
    while q:
        a.append(p // q)
        p, q = q, p % q
    return a

渐近分数

在连分数的定义中介绍了渐近分数的概念。实数的渐近分数就是它的连分数表示的渐近分数：在实数 的连分数表示中，只保留前 个项，得到的连分数 就称为实数 的第 个渐近分数。实数 的渐近分数 都是有理数，而且序列 收敛于实数 。

例子：黄金分割比的渐近分数

连分数 的前几个渐近分数分别是

可以归纳地证明

其中， 是 斐波那契数列。根据它的通项公式可知，

其中的 是黄金分割比。当 趋于无穷时，有

因而，连分数 表示的是黄金分割比 。

这些渐近分数趋近于相应的实数，所以可以用于逼近该实数。为此，有必要了解渐近分数的性质。

递推关系

首先，要解决这些渐近分数的计算问题。虽然渐近分数总是在连分数的后面添加一项，但是并不需要每次都重新计算它的值。其实，渐近分数有如下递推关系：

递推公式

对于连分数 ，设它的第 个渐近分数 可以写成分数 。那么，有

递推的起点是（形式）分数

证明

渐近分数 的分子和分母可以看作 的多元多项式：

根据渐近分数的定义，有

和上式比较，不妨设 ，就可以将渐近分数写作

且多项式 有递推关系

因为

所以，递推的起点是

如果设

可以验证对于 也成立上述递推关系。这相当于规定了形式分数 和 。

满足上述递推关系的多项式列 称为 连项式²（continuant）。它可以写作行列式的形式：

这是一个 三对角矩阵 的行列式，从左上角开始展开，可以验证它具有上面的递推关系和初值条件。反过来，从右下角开始展开，则又能得到递推关系

这就是所要求证的。

这个递推式说明

介于 和 之间。

作为渐近分数的递推关系的推论，成立如下的反序定理和倒数定理：

反序定理

设实数 的第 个渐近分数是 ，则相邻两个渐近分数的分子和分母的比值分别为

如果 ，则第一个连分数应当理解为在倒数第二项处截断，即 。

证明

在 和 的递推关系中，左右两侧分别同除以 和 ，就得到

迭代这两个式子，就可以得到两个连分数。再代入初始值 和 即可。至于 的情形，将得到的连分数理解为形式表达式，则它的余项

因而可以直接略去最后两项。如果需要严格的证明，只要注意到这个式子可以看作 的极限即可。

利用本节得到的递推关系，可以得到计算渐近分数的算法如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// Find the convergents of a continued fraction A.
// Numerators and denominators stored separately in P and Q.
auto convergents(std::vector<int> a) {
  std::vector<int> p = {0, 1};
  std::vector<int> q = {1, 0};
  for (auto it : a) {
    p.push_back(p.back() * it + p.end()[-2]);
    q.push_back(q.back() * it + q.end()[-2]);
  }
  return std::make_pair(p, q);
}

1
2
3
4
5
6
7
8
9

# Find the convergents of a continued fraction A.
# Numerators and denominators stored separately in P and Q.
def convergents(a):
    p = [0, 1]
    q = [1, 0]
    for it in a:
        p.append(p[-1] * it + p[-2])
        q.append(q[-1] * it + q[-2])
    return p, q

误差估计

利用渐近分数的递推公式，可以估计用渐近分数逼近实数产生的误差。

首先，可以计算相邻的渐近分数的差值：

渐近分数的差分

设 是实数 的第 个渐近分数。那么，有

因此，相邻两项的渐近分数的差分是

证明

根据递推关系，有

这就是 。对两边同除以 ，就得到关于 的结论。

因而，奇数项渐近分数总是大于相邻两项，偶数项渐近分数总是小于相邻两项：渐近分数是交错变化的。

如果只看偶数项（奇数项）渐近分数，序列也是单调递增（递减）的。这是因为

当 为偶数（奇数）时为正（负）。同时，因为成立递推关系 ，分母 的增长速度不会慢于斐波那契数列的速度。所以，相邻两项的差一定趋近于零。这就说明，偶数项和奇数项渐近分数分别自下而上和自上而下地逼近同一极限。这就证明了无限简单连分数一定收敛。渐近分数趋近于相应实数的动态可以见下图：

前面已经说明，上渐近分数就是奇数项渐近分数，下渐近分数就是偶数项渐近分数。

利用差分公式，可以将实数 写成交错级数的形式：

连分数定义中的渐近分数和余项就是该级数的部分和和余项。

利用差分公式，还可以直接对渐近分数逼近实数产生的误差做出估计：

误差

设 是实数 的第 个渐近分数。那么，有

其中， 是实数 的第 个余项。进而，有

证明

因为 ，而且对形式连分数也成立渐近分数的差分公式，所以有

其中， 就是按照递推公式得到的这个形式连分数的第 个渐近分数的分母。

要完成随后的不等式估计，只需要注意到当 时，总成立

所以有

因此，有不等式

要得到外侧的放缩，再注意到 就可以了。

本节的差分公式还有一个简单推论：渐近分数 都是既约的。

其实，线性同余方程的解可以通过连分数的方法求解。