070. 欧拉函数排列(Totient permutation)

欧拉函数\(\varphi(n)\)计算小于\(n\)的自然数中和\(n\)互质的数的个数,比如1, 2, 4, 5, 7和8都小于9并且和9素质,因此\(\varphi(9)=6\)。1被认为和所有的正数素质,所以\(\varphi(1)=1\)

有趣的是,\(\varphi(87109)=79180\),可以看到87109只是79180的重新排列。

求这样一个\(n\),其中\(1<n<10^7\)\(\varphi(n)\)\(n\)的重新排列且\(n/\varphi(n)\)最小。

分析:上一题我们求了\(n/\varphi(n)\)最大时的\(n\)值,然而这一题要求\(n/\varphi(n)\)最小时的\(n\)值。要使得比值\(n/\varphi(n)\)最大,我们只需要在特定范围内找到一个数,它有最多的质因数即可。反之要使得比值\(n/\varphi(n)\)最小,则这个数的质因数数量应该尽量少。第一种情况是只有一个质因数,则这个数是一个质数,此时\(\varphi(n)=n-1\),假设\(n\)的个位数为\(d\),相应的个数为\(c\),比如在313中有两个三,则\(d=3,c=2\),则\(\varphi(n)\)中对应\(d\)的数的个数为\(c-1\),因此两个数不可能互相构成重排列。即当\(n\)是素数时,\(\varphi(n)\)\(n\)不可能互相构成重排列。

第二种情况是\(n\)有两个质因数\(p,q\),则\(n=pq\),则有:

$$ \varphi(n)=pq(1-\frac{1}{p})(1-\frac{1}{q})=(p-1)(q-1) $$

当进一步增加质因数数量时,\(n/\varphi(n)\)会进一步增大,所以要想\(n/\varphi(n)\)最小,则\(n\)应该只有两个质因数。在确定\(n\)只有两个质因数后,为使得\(n/\varphi(n)\)最小,则\(\varphi(n)\)应该足够大,即\(p,q\)应该足够大且\(n=pq<10^7\)。为保证这一点,我们应以\(\sqrt{10^7}\approx3162\)为中心,向两边拓展确定一个区间,在这个区间里选取不同的素数对\(p,q\),使得\(pq<10^7\)\(pq\)\((p-1)(q-1)\)互为重排列,最后我们选择使得\(\frac{pq}{(p-1)(q-1)}\)最小的\(p,q\),计算\(pq\)即为题目所求。

# time cost = 47.4 ms ± 847 µs

from sympy import primerange

def main():
    is_permutation = lambda x,y : "".join(sorted(str(x))) == "".join(sorted(str(y)))
    primes = list(primerange(2000,4000))
    dt = {(x*y,(x-1)*(y-1)):((x*y)/((x-1)*(y-1))) for x in primes for y in primes if x*y<10**7}
    for n,phi_n in sorted(dt,key=dt.get):
        if is_permutation(n,phi_n):
            return n