069. 欧拉函数最大值(Totient maximum)

欧拉函数\(\varphi(n)\)计算小于\(n\)的自然数中和\(n\)互质的数的个数,比如1, 2, 4, 5, 7和8都小于9并且和9素质,因此\(\varphi(9)=6\)。下表列示了小于等于十的数的欧拉函数值:

img

可以看到对于\(n\le10\)\(n=6\)\(n/\varphi(n)\)取得最大值,求对于\(n\le1,000,000\),在\(n\)等于多少时\(n/\varphi(n)\)取得最大值?

分析:欧拉函数是数论中经常会遇到的一个函数,我们可以通过一个公式将它和数\(n\)的质因数连接起来。一般地,对于正整数\(n\),设\(p|n\)表示所有整除\(n\)的质数,实际上就是\(n\)的质因数,则我们有:

$$ {\displaystyle \varphi (n)=n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right),} $$

如对于\(\varphi(36)\),可以如下计算:

$$ {\displaystyle \varphi (36)=\varphi \left(2^{2}3^{2}\right)=36\left(1-{\tfrac {1}{2}}\right)\left(1-{\tfrac {1}{3}}\right)=36\cdot {\tfrac {1}{2}}\cdot {\tfrac {2}{3}}=12.} $$

因此,题目中要求\(n/\varphi(n)\)的最大值,则有:

$$ n/\varphi(n)=\frac{n}{n\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)}=\frac{1}{\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)}=\prod\limits_{p|n}\dfrac{p}{p-1} $$

因为\(p/(p-1)>1\),则要使\(n/\varphi(n)\)最大,只需要使得求出对于\(n\le10^6\)中质因数最多的数即可。我们可以通过从小到大把质数依次相乘,保证其乘积不超过一百万,但再乘一个质数就会超过一百万。经过尝试,我们发现这个数是\(2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17=510510\),即为题目所求。显然,这道题只需要笔算即可,不过我还是写了一段小代码,如下:

# time cost = 6.91 ms ± 154 µs

from sympy import prime

def main(N=10**6):
    i,prod,arr = 1,1,[]
    while prod <= N:
        prod *= prime(i)
        arr.append(prod)
        i += 1
    return arr[-2]