一道初等数论题

大佬最帅

除了穷举还有啥方法吗 虽然穷举也没举出来

uk702

尝试一下，编程穷举或许不难。

case 1， n = 某个素数 $p^k$，则 d(n)=k+1，$\varphi(n)=p^{k-1}(p-1)$，$d(n)+\varphi(n)=2020 \implies  2020 - k - 1 = p^{k-1}(p-1)$，k=1 显然不符合，再对 k >= 2 时逐个验证，...（暂略）

case 2，n = $p^{i}q^{j}$，p、q 均为素数，于是 d(n)=(i+1)(j+1)，$\varphi(n)=p^{i-1}(p-1)q^{j-1}(q-1)$，对 i 和 j 逐个验证，...（暂略）

case 当 n 有更多不同的素因子时，这时 $p_1、p_2、p_3$（、...）可选择的对数有限，也易验证。

uk702

不知好不好证明（或否定），存在 N > 0，当 n > N 时，$\phi(n)$ > 2020。有这个结论的话，那题目就只需要对 n < N 进行验证，验证代码写起来就简单直接了。

uk702

假设 $n=p_1p_2.....p_k$，显然 1~n 中所有异于 $p_i$ 的素数均与 n 互素，因此，$\varphi(n)$ > $\pi(n) - log_{2}(n)$ 趋于无穷。由此，只需选取 N ，满足 $\pi(N)-log_{2}N$ > 2020，那么，当 n > N 时，必有 $\varphi(n)$ > 2020.

由于 $\pi(18000) = 2064$，且 $log_{2}(n)$ < 15，故对 1~18000 的 n 求解 $d(n)+\varphi(n)=2020$ 即可。

uk702

使用 gp 可一行代码搞定: select((i)->eulerphi(i)+numdiv(i)==2020, [1..18000])
解得 n=[2117, 2147, 2159, 2359, 3027, 4034, 5000, 6036] 共有 8 个解。