调和级数相关——质数的倒数和增长速度为O(ln ln n)

我们先来分析调和级数和质数的倒数和的增长速度，最后聊一聊关于调和级数的有趣的事情。

调和级数

我们常用级数来表示一个数列的前缀和。调和级数就是自然数倒数序列 $\{\frac{1}{n}\}$ 的和，其表达式为:

$\sum_{i=1}^{\infty}\frac{1}{n}=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+...$

这个和发散，但发散地极慢。举例来说，调和序列前 $10^{43}$ 项的和还不足 $100$。人们甚至一度认为这个数列收敛。欧拉精准地估计了这个和，并标明这个和的增长速度与自然对数的增长速度相同。具体来说：

$\sum_{i=1}^{n} \frac{1}{i} = \ln n + \gamma + O(1/n)$

其中，误差项 $O(\frac{1}{n})$ 在 $n$ 增大时趋近于零，可以忽略不计。

欧拉的证明附于文尾。

质数的倒数和

事实上，质数的倒数和的增长速度是 $O(\ln \ln n)$ 下面给出简单证明：

我们先来观察这样一个等式:

$\sum_{i=1}^{\infty}\frac{1}{n}=(1+\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+...)(1+\frac{1}{3}+\frac{1}{3^2}+\frac{1}{3^3}+...)(1+\frac{1}{5}+\frac{1}{5^2}+\frac{1}{5^3}+...)$ $=\frac{1}{1-\frac{1}{2}}\times\frac{1}{1-\frac{1}{3}}\times\frac{1}{1-\frac{1}{5}}\times...$ $=\prod_{p_i \in \mathbb{P}} \frac{1}{1-\frac{1}{p_i}}$

这是由于算术基本定理，即每一个 $n$ 只有唯一一种质因数分解。(之后的每一个等式都应该使用大O表示，但这里为了等式的完整美观暂时忽略大O表示）故：

$\ln(\sum_{i=1}^{n} \frac{1}{i}) = \ln(\prod_{p_i \leq n} \frac{1}{1-\frac{1}{p_i}})$ $= \sum_{p_i \leq n}\ln( \frac{1}{1-\frac{1}{p_i}})$ $= -\sum_{p_i \leq n}\ln( 1-\frac{1}{p_i})$ $= \sum_{p_i \leq n} \frac{1}{p_i} + O(\frac{1}{p_i^2})$

最后一步考虑 $\ln(1-x)$ 的泰勒展开:

$\ln (1-x) = x + \frac{x^2}{2} + \frac{x^3}{3} + O(x^4)$

于是我们得到(大O表示又回来了）：

$O(\sum_{p_i \leq n} \frac{1}{p_i}) = O(\ln(\sum_{i=1}^{n} \frac{1}{i})) =O(\ln \ln n)$

埃拉托斯特尼筛法的时间复杂度

考虑埃拉托斯特尼筛法的过程，可以得到其复杂度为：

$\sum_{p_i \in \mathbb{P},p_i \leq n} \frac{n}{p_i} = n \sum_{p_i \leq n} \frac{1}{p_i} = O(n \ln \ln n)$

调和级数增长速度————欧拉的证明

我们首先观察 $\ln(1+\frac{1}{x})$ 的泰勒展开：

$\ln(1+\frac{1}{x})=\frac{1}{x}-\frac{1}{2x^2}+\frac{1}{3x^3}-\frac{1}{4x^4}+...$ $\frac{1}{x}=\ln(\frac{x+1}{x})+\frac{1}{2x^2}-\frac{1}{3x^3}+\frac{1}{4x^4}-...$

直接累加得到：

$\sum_{i=1}^{n} \frac{1}{i}=\sum_{i=1}^{n} \ln(\frac{i+1}{i}) + \frac{1}{2} \sum_{i=1}^{n} \frac{1}{x^2}-\frac{1}{3} \sum_{i=1}^{n} \frac{1}{x^3}+\frac{1}{4} \sum_{i=1}^{n} \frac{1}{x^4}-...$ $= \ln(n+1) + \gamma + O(\frac{1}{n})$

其中 $\gamma$ 是一个常数（欧拉常数）。这是因为后面很多项是自然数平方、立方等等的倒数和，之前欧拉证明过他们都将收敛于一个常数（严格来说欧拉只证明了自然数偶数次的倒数和收敛于一个固定的常数，详细请见我的博客《再探π^2/6》）

交错的调和级数的和

考虑 $\ln(1+x)$ 的泰勒展开:

$\ln (1+x) = x - \frac{x^2}{2} + \frac{x^3}{3} - \frac{x^4}{4}+...$

带入 $x=1$ 可得：

$1 - \frac{1}{2} + \frac{1}{3} - \frac{1}{4}+... = \ln 2$

它居然收敛！

交错的奇自然数倒数和

考虑反正切函数 $\arctan x$ 的泰勒展开:

$\arctan x = x - \frac{x^3}{3} + \frac{x^5}{5} - \frac{x^7}{7}+...$

带入 $x=1$ 可得：

$1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7}+... = \frac{\pi}{4}$

这个居然收敛于 $\frac{\pi}{4}$ !
顺便一提，这个公式被称为 $\pi$ 的莱布尼茨公式。