关于一个最小质因数个数分布的猜想证明

· · 算法·理论

摘要

本文需要证明以下极限的敛散性

\lim\limits_{n\to\infty}\frac{\sum\limits_{i=1}^nf^k(i)}n

其中 k\in\R 是参数，f(x) 为 x 的最小质因子在质因子分解中的幂次，例如 f(12)=f(2^2\times3)=2，我们规定 f(1)=0。

我们将证明 k\le1 时上述极限收敛，否则发散。

关键词

极限理论，积性函数，线性筛法，Mertens 定理，积分估值

引言

我们知道，如果一个积性函数 f 可以在 O(1) 的时间内算出 f(p^k) 的值，我们就可以以线性时间筛出前 n 项的值，但是如果函数 f 没有足够良好的性质，只能在 O(P(k)) （P 是有理函数）的时间复杂度是否仍然能做到理论线性复杂度呢？如果前文所述极限收敛，我们就可以做到线性复杂度，否则就可能无法做到了。

本文将证明，如果 P 的次数不超过 1，线性筛出的复杂度是可以保证的。

k>1 的情况

设 p_i 表示第 i 小的质数，枚举每个质数作为最小质因数，计算其贡献，可以得到以下表达式：

\lim\limits_{n\to\infty}\frac{\sum\limits_{i=1}^nf^k(i)}n=\sum\limits_{i=1}^\infty\left(\sum\limits_{j=1}^\infty\frac{j^k-(j-1)^k}{p_i^j}\right)\left(\prod\limits_{j=1}^{i-1}1-\frac1{p_j}\right)\tag{1}

首先我们需要对如下表达式估界：

\sum\limits_{t=1}^\infty\frac{t^k-(t-1)^k}{x^t}=k\sum\limits_{t=1}^\infty\frac{t^{k-1}}{x^t}+o\left(\sum\limits_{t=1}^\infty\frac{t^{k-2}}{x^t}\right)

注意到函数 \frac{t^{k-1}}{x^t} 是单峰函数，在 \frac {k-1}{\ln x} 取到最大值，令 m=\lfloor\frac{k-1}{\ln x}\rfloor，我们将求和分为两段，补上 t=0 项分别使用广义积分进行估计：

\sum\limits_{t=1}^\infty\frac{t^{k-1}}{x^t}&=\sum\limits_{t=0}^m\frac{t^{k-1}}{x^t}+\sum\limits_{t=m+1}^\infty\frac{t^{k-1}}{x^t}\\ &\ge\int_0^{m}\frac{t^{k-1}}{x^t}dt+\int_{m+1}^\infty\frac{t^{k-1}}{x^t}dt\\ &=\int_0^\infty\frac{t^{k-1}}{x^t}dt-\int_m^{m+1}\frac{t^{k-1}}{x^t}dt\\ &\ge\int_0^\infty\frac{t^{k-1}}{x^t}dt-\frac{(k-1)^{k-1}}{e^{k-1}\ln^{k-1}x}\tag{3} \end{aligned}

第二个不等式将 t 放缩到 \frac {k-1}{\ln x}，所以不等式成立。

然后令 u=t\ln x，有

\int_0^\infty\frac{t^{k-1}}{x^t}dt&=\int_0^\infty t^{k-1}e^{-e\ln x}dt\\ &=\frac1{\ln^{k-2}}\int_0^\infty u^{k-1}e^{-u}du\\ &=\frac{\Gamma(k)}{\ln^{k-2}x} \end{aligned}

带入 (3) 得

\sum\limits_{t=1}^\infty\frac{t^{k-1}}{x^t}\ge\frac{\Gamma(k)}{\ln^{k-2}x}-\frac{(k-1)^{k-1}}{e^{k-1}\ln^{k-1}x}

同理有

\sum\limits_{t=1}^\infty\frac{t^{k-1}}{x^t}\le\frac{\Gamma(k)}{\ln^{k-2}x}+\frac{(k-1)^{k-1}}{e^{k-1}\ln^{k-1}x}

使用 Stirling 公式对 \Gamma(k) 估值，可以得到

\frac{\Gamma(k)}{\ln^{k-2}x}=\sqrt{2\pi (k-1)}\frac{(k-1)^{k-1}}{e^{k-1}\ln^{k-2}x}\gg \frac{(k-1)^{k-1}}{e^{k-1}\ln^{k-1}x}

于是我们有

O\left(\sum\limits_{t=1}^\infty\frac{t^{k-1}}{x^t}\right)=O\left(\frac{\Gamma(k)}{\ln^{k-2}x}\right)\tag4

然后我们再使用 Mertens 定理得到

\prod\limits_{p\le x}\left(1-\frac1{p}\right)=\frac{e^{-\gamma}}{\ln x}+O\left(\frac1{\ln^2x}\right)\tag{5}

将 (4)(5) 带入 (1) ，并使用质数定理可得，

O\left(\lim\limits_{n\to\infty}\frac{\sum\limits_{i=1}^nf^k(i)}n\right)=O\left(\Gamma(k)e^{-\gamma}\sum\limits_{i=1}^\infty\frac1{\ln^{k-1}p_i}\right)=O\left(\Gamma(k)e^{-\gamma}\sum\limits_{i=1}^\infty\frac1{\ln^{k-1}i}\right)

注意到

\frac1{\ln^{k-1}i}\gg \frac1i

所以上述极限发散。

k=1 的情况

使用质数定理和泰勒公式 \sum\limits_{j=1}^\infty\frac1{p_i^j}=\frac1{p_i-1}，得到

O\left(\lim\limits_{n\to\infty}\frac{\sum\limits_{i=1}^nf^k(i)}n\right)=O\left(\sum\limits_{i=2}^\infty\frac1{i\ln i}\right)

使用积分估值即可，注意到 \int\frac1{x\ln^2x}dx=-\frac1{\ln x}+C：

O\left(\sum\limits_{i=2}^\infty\frac1{i\ln i}\right)=O\left(\int_2^\infty\frac1{x\ln^2x}dx\right)=O(1)

于是收敛。

k<1 的情况

注意到

\sum\limits_{j=1}^\infty\frac{j^k-(j-1)^k}{p_i^j}\le\sum\limits_{j=1}^\infty\frac1{p_i^j}

收敛性显然。

结论

本文主要内容是关于极限

\lim_{n\to\infty}\frac{\sum_{i=1}^nf^k(i)}{n}

的敛散性，其中 k\in\mathbb{R} 是参数，f(x) 定义为 x 的最小质因子在质因子分解中的幂次。具体结论如下：

这些结论意味着，对于给定的积性函数 f，如果其计算复杂度不超过线性（即 O(P(k)) 中 P 的次数不超过 1），那么我们可以通过线性筛法在线性时间内计算出 前 n 项的值。这为处理具有特定性质的积性函数提供了理论基础，特别是当涉及到最小质因子的幂次时。此外，这些结果还暗示了当 k>1 时，由于极限发散，可能无法保证线性时间复杂度的筛法的有效性。

鸣谢

robinyqc 积性函数线性筛(https://www.luogu.com/article/7xe1pdud)