先用筛法找出给定范围内的素数，再从大到小依次考虑以第k个素数$p_k$为最大素因子的数，枚举$p_k$的幂并作深度优先搜索。
搜索时注意到$\varphi(n^2)=n\varphi(n)$，因此若$p_k$在n中的幂是$a_k$，那么它在$\varphi(n^2)$中的幂是$2a_k-1$。
以$(k, n, \varphi(n))$作为搜索状态，$\varphi(n)$中还会产生因子$p_k-1$，对该因子的分解可以递延到之后的搜索步骤。
最终结果是$5943040885644$。
注：以下代码为Python 3。本题递归深度超过了系统默认值，需要用sys.setrecursionlimit重新设置。大约需要数分钟运行，但因递归进度难以估计，因此未打印进度。
import sys
sys.setrecursionlimit(10**6)
bound=10**10
target=100000
d=[0]*target
n=2
while n < target:
for i in range(n*n,target,n):
d[i]=d[i]+1
n=n+1
while n < target and d[n]>0:
n=n+1
primeList=[k for k in range(2,target) if d[k]==0]
def check(k,n,phi):
if k < 0:
return n
t=phi
c=0
while t%primeList[k]==0:
t//=primeList[k]
c+=1
c%=3
r=check(k-1,n,phi) if c==0 else 0
x=1
n*=primeList[k]
while n < bound:
if (x+x-1+c)%3==0:
r+=check(k-1,n,phi*(primeList[k]-1))
x+=1
n*=primeList[k]
return r
print(check(len(primeList)-1,1,1)-1)
|
