阅读理解（一）
m256i
·
·
算法·理论
原文
stO pzq Orz
居然有一天能看懂神的文章了，这不得写篇纪念一下（
算是一种通俗演义吧？
\rm I
求 n 以内的 powerful number（不含次数为 1 质因子的数）数量的渐近表达式。
经典结论，PN 可以写成 a^2b^3 形式。首先对于一个 p^k，如果 k 为奇数就提一个 p^3 出来放 b 里面，否则直接放 a 里面。这样假如 b 不含平方因子的话表示法是唯一的。
枚举 b 然后统计：
\begin{aligned}
&\sum_{k\le\lfloor\sqrt[3]n\rfloor}\mu^2(k)\left\lfloor\sqrt\dfrac{n}{k^3}\right\rfloor\\
={}&\sum_{k\le\lfloor\sqrt[3]n\rfloor}\mu^2(k)\sqrt\dfrac{n}{k^3}+\mathcal O\left(n^{\frac{1}{3}}\right)\\
={}&\sqrt n\sum_{k\le\lfloor\sqrt[3]n\rfloor}\mu^2(k)k^{-\frac{3}{2}}+\mathcal O\left(n^{\frac{1}{3}}\right)\\
={}&\sqrt n\sum_{k \ge 1}\mu^2(k)k^{-\frac{3}{2}}+\sqrt n\sum_{k \ge \lfloor\sqrt[3]n\rfloor}\mathcal O(1)k^{-\frac{3}{2}}+\mathcal O\left(n^{\frac{1}{3}}\right)\\
={}&\sqrt n\sum_{k \ge 1}\mu^2(k)k^{-\frac{3}{2}}+\sqrt n\mathcal O\left(\int_{n^{\frac{1}{3}}}^\infty x^{-\frac{3}{2}} \mathrm dx\right)+\mathcal O\left(n^{\frac{1}{3}}\right)\\
={}&\sqrt n\sum_{k \ge 1}\mu^2(k)k^{-\frac{3}{2}}+\sqrt n\mathcal O\left(n^{-\frac{1}{6}}\right)+\mathcal O\left(n^{\frac{1}{3}}\right)\\
={}&\sqrt n\sum_{k \ge 1}\mu^2(k)k^{-\frac{3}{2}}+\mathcal O\left(n^{\frac{1}{3}}\right)
\end{aligned}
和式就是 \mu^2 的 DGF 在 \dfrac{3}{2} 处的值，\mu^2 的 DGF 就是 \displaystyle\prod_{p \in \mathbb P}(1+p^{-z})=\displaystyle\prod_{p \in \mathbb P}\dfrac{1-p^{-2z}}{1-p^{-z}}=\dfrac{\zeta(z)}{\zeta(2z)}，所以结果是 \dfrac{\zeta(1.5)}{\zeta(3)}，即 n 以内 PN 的数量是：
\dfrac{\zeta(1.5)}{\zeta(3)}\sqrt n+\mathcal O\left(n^{\frac{1}{3}}\right)
\rm II
求 \displaystyle\sum_{k \le n}\dfrac{1}{\varphi(k)} 的渐近表达式。
里面这玩意没见过，尝试拿贝尔级数搞一下：
\begin{aligned}
F_p(x)&=1+\sum_{k \ge 1}\dfrac{x^k}{p^k-p^{k-1}}\\
&=1+\dfrac{1}{p-1}\sum_{k \ge 1}\dfrac{x^k}{p^{k-1}}\\
&=1+\dfrac{1}{p-1}x\sum_{k \ge 0}\dfrac{x^k}{p^k}\\
&=1+\dfrac{x}{(p-1)\left(1-\frac{x}{p}\right)}\\
&=\dfrac{p-1+\frac{x}{p}}{(p-1)\left(1-\frac{x}{p}\right)}
\end{aligned}
提取一个 1-\dfrac{x}{p}（也就是 \mathrm{id}_{-1}）出来，剩下的部分是 \dfrac{p-1+\frac{x}{p}}{p-1}=1+\dfrac{x}{p(p-1)} 也就是 \dfrac{\mu^2\mathrm{id}_{-1}}{\varphi}。代入到原来式子里就有：
\begin{aligned}
\sum_{k \le n}\dfrac{1}{\varphi(k)}&=\sum_{k \le n}\dfrac{\mu^2(k)}{k\varphi(k)}\Sigma\mathrm{id}_{-1}\left(\left\lfloor\dfrac{n}{k}\right\rfloor\right)\\
&=\sum_{k \le n}\dfrac{\mu^2(k)}{k\varphi(k)}H_{\left\lfloor\frac{n}{k}\right\rfloor}\\
&=\sum_{k \le n}\dfrac{\mu^2(k)}{k\varphi(k)}\left(\log\dfrac{n}{k}+\gamma+\mathcal O\left(\dfrac{k}{n}\right)\right)\\
&=(\log n+\gamma)\sum_{k \le n}\dfrac{\mu^2(k)}{k\varphi(k)}-\sum_{k \le n}\dfrac{\mu^2(k)\log k}{k\varphi(k)}+\mathcal O\left(\dfrac{1}{n}\sum_{k \le n}\dfrac{\mu^2(k)}{\varphi(k)}\right)
\end{aligned}
先看右边部分。欧拉函数肯定不会太小（平均阶就是 \Phi 渐近表达式的导数即 \dfrac{n}{\zeta(2)}=\dfrac{6n}{\pi^2}，最小阶可以证明一定大于 n^{1-\delta}，其中 \delta>0，具体论述看这里），但是我们其实没必要关心这个，就假设它是 n^\epsilon，其中 \epsilon>0。
这样 \mathcal O 的部分就是 \displaystyle\mathcal O\left(\dfrac{1}{n}\sum_{k \le n}\dfrac{\mathcal O(1)}{\Omega(k^{\epsilon})}\right)=\mathcal O\left(\dfrac{1}{n}\int_1^nx^{-\epsilon}\mathrm dx\right)=\mathcal O(n^{-\epsilon})。
右边的和式还是把上限拉满，余项是 \displaystyle\sum_{k>n}\dfrac{\mathcal O(1)\log k}{k\Omega(k^\epsilon)}=\mathcal O\left(\int_n^\infty x^{-1-\epsilon}\log x\mathrm dx\right)=\mathcal O(n^{-\epsilon}\log n)。
剩下部分显然收敛，假设 \dfrac{\mu^2}{\varphi} 的狄利克雷级数是 \tilde F 那么剩下部分是 -\tilde F'(1)，可惜 \tilde F 并没有封闭形式。但是我们可以把它转换成一个不含积性函数的形式。
$$
\begin{aligned}
\dfrac{\tilde F'(z)}{\tilde F(z)}&=\sum_{p \in \mathbb P}\dfrac{(p^{z+1}-p^z+1)'}{p^{z+1}-p^z+1}-\sum_{p \in \mathbb P}\dfrac{(p^{z+1}-p^z)'}{p^{z+1}-p^z}\\
&=\sum_{p \in \mathbb P}\dfrac{(p^{z+1}-p^z)'}{p^{z+1}-p^z+1}-\sum_{p \in \mathbb P}\dfrac{(p^{z+1}-p^z)'}{p^{z+1}-p^z}\\
&=\sum_{p \in \mathbb P}\dfrac{(p-1)(p^z)'}{(p-1)(p^{z+1}-p^z+1)p^z}\\
&=\sum_{p \in \mathbb P}\dfrac{p^z \log p}{(p^{z+1}-p^z+1)p^z}\\
&=\sum_{p \in \mathbb P}\dfrac{\log p}{p^{z+1}-p^z+1}
\end{aligned}
$$
代入 $z=1$ 就有 $\tilde F'(1)=\tilde F(1)\displaystyle\sum_{p \in \mathbb P}\dfrac{\log p}{p^2-p+1}$。
左边的和式部分同理，上限拉到无穷，余项 $\displaystyle\sum_{k>n}\dfrac{\mathcal O(1)}{k\Omega(k^\epsilon)}=\mathcal O\left(\int_n^\infty x^{-1-\epsilon}\mathrm dx\right)=\mathcal O(n^{-\epsilon})$。
这样剩下部分是：
$$
\begin{aligned}
\sum_{k \ge 1}\dfrac{\mu^2(k)}{k\varphi(k)}
&=\tilde F(1)\\
&=\prod_{p \in \mathbb P}\dfrac{p^2-p+1}{p^2-p}\\
&=\prod_{p \in \mathbb P}\dfrac{1-p^{-1}+p^{-2}}{1-p^{-1}}\\
&=\prod_{p \in \mathbb P}\dfrac{1+p^{-3}}{(1-p^{-1})(1+p^{-1})}\\
&=\prod_{p \in \mathbb P}\dfrac{1-p^{-6}}{(1-p^{-2})(1-p^{-3})}\\
&=\dfrac{\zeta(2)\zeta(3)}{\zeta(6)}
\end{aligned}
$$
所以渐近表达式为：
$$\dfrac{\zeta(2)\zeta(3)}{\zeta(6)}\left(\log n+\gamma-\sum_{p \in \mathbb P}\dfrac{\log p}{p^2-p+1}\right)+\mathcal O\left(\dfrac{\log n}{n^\epsilon}\right)$$
[这篇文章](//zhuanlan.zhihu.com/p/371082286)进一步证明了 $\epsilon=1$。
> **免责声明**
>
> 作者并不会解析数论，唯一的学习来源是混凝土 7.7 章和 9.3 章的一点内容，不保证与原文理解一致，假如推导有问题概不负责。
Update on 2023.12.29：修复了答案错误（因为某人以为 $\mathcal O(n^{-\epsilon}\log n)$ 比 $\mathcal O(1)$ 大），更改了一些格式（整齐起见把和式全部从上下标改成了下标形式）。