不可约度

给定分母d，一共有$d-1$个真分数（分子小于分母的正分数），定义d的不可约度$R(d)$为这些真分数中不可约分数（分子分母互素）的比例，例如$R(12)=4/11$。 事实上，$d=12$也是满足$R(d) < 4/10$的最小分母d。 求满足$R(d) < 15499/94744$的最小分母d。

本题难度:

解答

记$\varphi(d)$为欧拉Totient函数，则显然$R(d)=\varphi(d)/(d-1)$。 $\varphi$具有积性，而$(p-1)(q-1) < pq-1$，因此增加不同质因数的数量能降低$R(d)$的值。 另一方面，若$p|d$，则也容易看出 $$\frac{p\varphi(d)}{pd-1}<\frac{\varphi(d)}{d-1},$$ 因此增加已有质因数的次数也可以降低$R(d)$的值。 可以看出增加不同的质因数能快速降低$R(d)$，但d也快速增长，反之增加已有质因数的次数则$R(d)$的降幅较小，但d的增长也较慢。 因此先不断添加质因数找到满足$\phi(d)/(d-1)$超过$15499/94744$但$\phi(d)/d$小于$15499/94744$，再增加其已有质因数的次数。 稍加试算即得结果是 $$892371480=2^3\times3\times5\times7\times11\times13\times17\times19\times23.$$ 本题无需编程。