0070 欧拉函数重排
* * * *
拉格朗日计划
* * * *
欧拉函数重排

欧拉函数$\varphi(n)=$小于n且与n互质的正整数的数量。例如1、2、4、5、7、8与9互质,因此$\varphi(9)=6$。

1和任意正整数都互质,因此$\varphi(1)=1$。

有趣的是,$\varphi(87109)=79180$,而79180可由重新排列87109中各位数字得到。

在大于1且小于$10^7$的n中还存在满足同样性质(即$\varphi(n)$是n中各位数字的重排)的n,求这些n中使$n/\varphi(n)$最小的n。

本题难度:



解答

用筛法找出所有的素因子,再从中找出满足条件的n,结果是$n=8319823$(此时$\varphi(n)=8313928$)。

target=10**7

d=[[] if i%2 else [2] for i in range(target)]
p,q,n=target,1,3
while n < target:
    if d[n]:
        m=n
        for k in d[n]:
            m=m*(k-1)/k
        if sorted(list(str(n)))==sorted(list(str(m))) and n*q < m*p:
            p,q=n,m
    else:
        for k in range(n,target,n):
            d[k].append(n)
    n+=1
print p,q