两个关于Square Factor的趣题

本文讨论了两个关于square factor的趣题。

首先介绍一下square-free number(虽然和下面的内容没有什么关系)

我们称一个数是square-free的,当且仅当它没有平方因子(关于平方因子的定义在Part\ I中)

我们用S(n)表示1n的square-free number的个数,有它的渐进式

\lim_{n\rightarrow \infty} S(n)=\frac{6}{\pi^2}n+O(\sqrt{n})

如果广义黎曼猜想成立,我们可以进一步减小误差:
S(n)=\frac{6}{\pi^2}n+O(n^{17/54+\epsilon})

Part I

我们称px的平方质因子当且仅当p是质数且p^2|x。定义函数C_k(n)表示[1,n]中恰有k个非平方因子的数的个数。

这里有一个表 (from Project Euler)

\begin{array}{|c|c|c|c|c|c|c|} \hline & k = 0 & k = 1 & k = 2 & k = 3 & k = 4 & k = 5 \\ \hline N=10 & 7 & 3 & 0 & 0 & 0 & 0 \\ \hline N=10^2 & 61 & 36 & 3 & 0 & 0 & 0 \\ \hline N=10^3 & 608 & 343 & 48 & 1 & 0 & 0 \\ \hline N=10^4 & 6083 & 3363 & 533 & 21 & 0 & 0 \\ \hline N=10^5 & 60794 & 33562 & 5345 & 297 & 2 & 0 \\ \hline N=10^6 & 607926 & 335438 & 53358 & 3218 & 60 & 0 \\ \hline N=10^7 & 6079291 & 3353956 & 533140 & 32777 & 834 & 2 \\ \hline N=10^8 & 60792694 & 33539196 & 5329747 & 329028 & 9257 & 78 \\ \hline \end{array}

聪明的你能从中发现什么规律吗?

对于所有非0C_k{10^{16}}\prod_{k}C_k(10^{16})

Solution

其实也不是很难

首先对于k=0的情况是一类经典问题,也就是square-free number。通过简单的推导,我们可以得到这样一个式子。

\large C_0(n)=\sum_{d=1}^{\sqrt{n}}\mu(d)\lfloor\frac{n}{d^2}\rfloor\\

我们考虑这个式子。枚举包含的平方因子,容斥掉含有平方因子的。对于枚举的一个d,首先d不能包含平凡因子,然后可以发现对于一个d,它的容斥系数应当于质因子个数有关,也就是说质因子个数就是它的计算次数。

同样的,我们考虑C_k(n)的情况。

同样的,我们也枚举d,首先去掉所有有平方因子和质因子个数小于kd,然后我们考虑一个d的计算次数。由于我们没有考虑个数小于kd,之后的每一个在除去之后的以后都会被重复计算\binom{cnt_d}{k}次,不难发现容斥系数为\mu(d)\binom{cnt_d}{k}(-1)^k
\large C_k(n)=\sum_{d=1}^{\sqrt{n}}\mu(d)\binom{cnt_d}{k}(-1)^k\lfloor\frac{n}{d^2}\rfloor
同时,显而易见的,对于k\ge 10,C_k(10^{16})=0

于是我们可以在大约10s之内跑出结果了。

Part II

我们定义c_k^{n}=\frac{C_k(n)}{n},现在要求c_7^{\infty}

同样的,有这样一个表 (from Project Euler)
\begin{array}{|c|c|c|c|c|c|} \hline & k = 0 & k = 1 & k = 2 & k = 3 & k = 4 \\ \hline \\ c_k^{\infty} & \frac{6}{\pi^2} & 3.3539\times 10^{-1} & 5.3293\times 10^{-2} & 3.2921\times 10^{-3} & 9.7046\times 10^{-5}\\ \hline \end{array}

聪明的你能再一次发现规律吗?

首先,容易发现
\large c_0^{\infty}=\frac{1}{\sum_{i=1}^{\infty}\frac{1}{i^2}}

通过推导,可以得到这样一个结论
\large c_k^\infty=\sum_{p_1,p_2,\cdots,p_k}\frac{1}{p_1p_2\cdots p_k}\\ \small p1,p_2,\cdots,p_k\ are\ all \ prime\ numbers

推导过程请读者自行思考

发表评论

电子邮件地址不会被公开。 必填项已用*标注