如何证明一个数 n 的因子之和是 O(n) 的？ 第1页

第一步：渐近上界

根据题主定义，有 ，因此f是积性函数，所以我们只需要通过考虑n为素数幂的情况来得到更具体的计算公式。当p为素数 时

于是根据算术基本定理，我们得到：

现在进行放缩，得：

其中M满足 ，在确定M前我们可以考虑先代入Mertens公式：

^[1]

得

第二步：确定M^[2]

设 满足当 表示第j个素数时 ，则 且：

对两侧同时除以 ，得：

现在利用素数定理，我们得知以下两个结论：

其中第二个式子意味着 ，所以根据夹逼定理我们得知 。而根据 的定义，我们可以设 ，回代至(2)我们就得到了：

而(4)意味着以下不等式成立：

第三步：(5)的取等条件

虽然(5)意味着 但这不足以说明 。此时设 则根据(1)，有：

其中最后一个等号利用了zeta函数的欧拉乘积和Mertens公式。再根据 和(3)，我们有：

对两侧同时取对数，便有：

最后利用 我们就发现 是(5)的取等条件。综上所述我们得到了因子和的渐近上确界（Gronwall定理）：

这预示着题主的猜想是错误的，因子和的阶不是O(n)而是O(nloglogn)。

参考

1. ^当数论遇上分析（6）——Mertens定理与素数定理 - 知乎 https://zhuanlan.zhihu.com/p/338578631
2. ^ Gronwall, T. H. (1913). Some asymptotic expressions in the theory of numbers. Transactions of the American Mathematical Society, 14(1), 113–122.