两个关于Square Factor的趣题

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

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

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

我们用$S(n)$表示$1$到$n$的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

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

对于所有非$0$的$C_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$,首先去掉所有有平方因子和质因子个数小于$k$的$d$,然后我们考虑一个$d$的计算次数。由于我们没有考虑个数小于$k$的$d$,之后的每一个在除去之后的以后都会被重复计算$\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}$
首先,容易发现
$$
\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
$$

推导过程十分Trivail,请读者自行思考

发表评论

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