Some Results In Arithmetic Functions

数学

---

看论文啊 看论文啊

翻译论文Masum Billal, Number of Ways To Write as Product of Co-prime Numbers, arXiv:1909.07823 [math.GM], 2019.

译者的话:

论文中错误有点多 我尽自己的能力修改 如果还有问题的请私信我修改 有些还没看懂的最后会更的

定义:

定义$\omega(x)$是$x$的质因子个数

例如:$\omega(6)=2,\omega(8)=1$

定义$\rho(n,k)$表示将$n$写成$k$个两两互质的正整数乘积的方案数

例如:$\rho(2,3)=3,\rho(6,2)=4$

定义$\varphi(x,a)=\displaystyle\sum\limits_{i=1}^x[gcd(i,a)==1]$

定义$rad(x)$表示$x$的质因数的乘积

定义$R(n,k)=\displaystyle\sum\limits_{i=1}^n\rho(i,k)$

特别地:$S(n)=R(n,2)$

定义$T(n)=\displaystyle\sum\limits_{i=1}^n\tau(i)=\displaystyle\sum\limits_{i=1}^n\lfloor\frac{n}{i}\rfloor$

定理1:

$$\text{对于任意正整数k,有}\rho(n,k)=k^{\omega(n)} \tag{1}$$

Proof.

$$\begin{array}{} &\text{设}n=\displaystyle\prod\limits_{i=1}^r p_i^{q_i}\\ &\text{我们先证明}k=2\text{满足上式:}\\ &\text{假设}a,b\in Z\text{且}gcd(a,b)=1,s.t.\ ab=n\\ &\text{所以我们有}gcd(rad(a),rad(b))=1,\text{且}rad(a)|rad(n),rad(b)|rad(n)\\ &\text{所以我们考虑把}n\text{的质因数分成2组},\text{这件事情显然有}2^{\omega(n)}\text{种方案}\\ &\text{具体地我们考虑}\omega(rad(a))可以是[0,\omega(n)],\text{所以方案数是}\displaystyle\sum\limits_{i=0}^{\omega(n)}C_{\omega(n)}^i=2^{\omega(n)}\\ &\text{假设}k=l\text{时,有}\rho(n,k)=k^{\omega(n)}\\ &\text{下证明当}k=l+1\text{时,有}\rho(n,k)=k^{\omega(n)}\\ &\text{类似于}k=2\text{的情形,我们假设:}\\ &n=\displaystyle\prod\limits_{i=1}^rp_i^{q_i}=\displaystyle\prod\limits_{i=1}^{k}a_i,\text{且对于任意}1\leq i<j\leq k\text{有}gcd(a_i,a_j)=1\\ &\displaystyle\prod\limits_{i=1}^{k}rad(a_i)=rad(n),a_k=\displaystyle\prod\limits_{i=1}^{r_k}p_i^{q_i}\\ &\text{那么有}\cfrac{n}{a_k}=\displaystyle\prod\limits_{i=1}^{k-1}a_i\\ &\text{而}\rho(\cfrac{n}{a_k},k-1)=(k-1)^{\omega(\frac{n}{a_k})}=(k-1)^{r-r_k}\\ &\text{所以}\rho(n,k)=\displaystyle\sum\limits_{i=1}^rC_r^i(k-1)^{r-i}=k^r=k^{\omega(n)} \end{array}$$

接下来我们将先用2种方法计算$S(n)$首先证明两个引理:

引理1:

$$\displaystyle\sum\limits_{d|n}\mu^2(d)=2^{\omega(n)} \tag{2}$$

Proof.

$$\begin{aligned}{} \text{设}n=\displaystyle\prod\limits_{i=1}^r p_i^{q_i}\\ \displaystyle\sum\limits_{d|n}\mu^2(d)&=\displaystyle\prod\limits_{d|n}\mu^2(\displaystyle\prod\limits_{i=1}^rp_i^{q_i})\\ &=\displaystyle\prod\limits_{i=1}^r\displaystyle\sum\limits_{j=0}^{q_i}\mu^2(p_i^j)\\ &=\displaystyle\prod\limits_{i=1}^r(1+1)\\ &=2^r\\ &=2^{\omega(n)} \end{aligned}$$

引理2:

$$\text{若}F(i)=\displaystyle\sum\limits_{d|n}f(d)\\ \displaystyle\sum\limits_{i=1}^nF(i)=\displaystyle\sum\limits_{i=1}^n\lfloor\frac{n}{i}\rfloor f(i) \tag{3}$$

易证

定理2:

$$S(n)=\displaystyle\sum\limits_{i=1}^{\lfloor\sqrt n\rfloor}(\varphi(\frac{n}{i},i)-\varphi(i))-1 \tag{4}$$

Proof.

$$\begin{aligned} &\text{我们不难发现}S(n)=|\{(a,b)|a,b\in Z,gcd(a,b)=1,s.t.\ ab\leq n\}|\\ &\text{这里|A|表示集合A中的元素个数}\\ &\text{我们不妨设}a\leq b\\ &\text{那么}S(n)=2\times|\{(a,b)|a,b\in Z,gcd(a,b)=1,s.t.\ ab\leq n,a\leq b\}|-1\\ &\text{这里减一注意到}a=b\text{时仅当}a=b=1\text{时满足条件且显然}(1,1)=(1,1)\\ &\text{我们发现}b=\frac{n}{a}\text{因此方案数有}\varphi(\frac{n}{a},a)-\varphi(a)\\ &\text{所以最后的答案就是}\displaystyle\sum\limits_{i=1}^{\lfloor\sqrt n\rfloor}(\varphi(\frac{n}{i},i)-\varphi(i))-1 \end{aligned}$$

定理3:

$$S(n)=T(n)+\displaystyle\sum\limits_{i=2}^{\lfloor\sqrt n\rfloor}\mu(i)T(\lfloor\frac{n}{i^2}\rfloor) \tag{5}$$

Proof.

$$\begin{aligned} S(n)&=\displaystyle\sum\limits_{i=1}^n\rho(i,2)\\ &=\displaystyle\sum\limits_{i=1}^n2^{\omega(i)}&\text{(定理1)}\\ &=\displaystyle\sum\limits_{i=1}^n\displaystyle\sum\limits_{d|i}\mu^2(d)&\text{(引理1)}\\ &=\displaystyle\sum\limits_{i=1}^n\mu^2(i)\lfloor\frac{n}{i}\rfloor&\text{(引理2)}\\ &=\displaystyle\sum\limits_{i=1}^n\lfloor\frac{n}{i}\rfloor-\displaystyle\sum\limits_{i=1,x^2|i}^n\lfloor\frac{n}{i}\rfloor\\ &=T(n)+\displaystyle\sum\limits_{i=2}^n\mu(i)\displaystyle\sum\limits_{d=1}^{\lfloor\frac{n}{i^2}\rfloor}\lfloor\frac{n}{i^2d}\rfloor\\ &=T(n)+\displaystyle\sum\limits_{i=2}^n\mu(i)T(\lfloor\frac{n}{x^2}\rfloor)\\ &=\displaystyle\sum\limits_{i=1}^{\lfloor\sqrt n\rfloor}\mu(i)T(\lfloor\frac{n}{i^2}\rfloor) \end{aligned}$$

定理4:

$$\displaystyle\sum\limits_{i=1}^{\lfloor\sqrt n\rfloor}(\varphi(\frac{n}{i},i)-\varphi(i))-1=\displaystyle\sum\limits_{i=1}^{\lfloor\sqrt n\rfloor}\mu(i)T(\lfloor\frac{n}{i^2}\rfloor) \tag{6}$$

???证你马

注意到 定理三并不使用于求$R(n,k)$但是5式右边的内容给了我们推广的灵感 我们先定义这么一个东西:

定义$d(n,k)$表示把$n$写成$k$个正整数乘积的方案数

定义$D(n,k)=\displaystyle\sum\limits_{i=1}^nd(i,k)$

在给出一般性结论之前 我们先看一个引理:

引理3

$$\text{设}n=\displaystyle\prod\limits_{i=1}^r p_i^{q_i}\text{ ,则 }d(n,k)=\displaystyle\prod\limits_{i=1}^rC_{q_i+k-1}^{k-1} \tag{7}$$

类似于定理1的证明方法依然在引理3上适用 证明留给读者自行完成

我们发现当$k=2$的时候$d(n,2)=\tau(n)$ 所以同样有$D(n,2)=T(n)$

这样我们一般性的结论应该大胆地猜测一下 就可以得到:

定理5:

$$R(n,k)=D(n,k)+\displaystyle\sum\limits_{i=2}^kC_k^i\displaystyle\sum\limits_{j=2}^{\sqrt[i]{n}}\mu(i)D(\lfloor\frac{n}{j^i}\rfloor,j)$$

Proof.

我不会 先咕咕咕