Project Euler 243

题目

Resilience

A positive fraction whose numerator is less than its denominator is called a proper fraction.

For any denominator, $d$, there will be $d−1$ proper fractions; for example, with $d=12$:

$\dfrac{1}{12},\dfrac{2}{12},\dfrac{3}{12},\dfrac{4}{12},\dfrac{5}{12},\dfrac{6}{12},\dfrac{7}{12},\dfrac{8}{12},\dfrac{9}{12},\dfrac{10}{12},\dfrac{11}{12}$

We shall call a fraction that cannot be cancelled down a resilient fraction.

Furthermore we shall define the resilience of a denominator, $R(d)$, to be the ratio of its proper fractions that are resilient; for example, $R(12) = \dfrac{4}{11}$ .

In fact, $d=12$ is the smallest denominator having a resilience $R(d) < \dfrac{4}{10}$.

Find the smallest denominator $d$, having a resilience $R(d) < \dfrac{15499}{94744}$ .

解决方案

令$r=\dfrac{15499}{94799}$

根据欧拉函数$\varphi$的定义，可以知道$R(d)=\dfrac{\varphi(d)}{d-1}$.

如果一个数$n$中质因数越来越多，那么$\dfrac{\varphi(n)}{n-1}$就会显著降低，因为随着$n$的增大这个比值会无限趋近于$\dfrac{\varphi(n)}{n}$。如果一个数$n$，它的质因数的幂指数越大，那么对答案的贡献将会越低。

并且，如果这些质因数越小，$\dfrac{\varphi(n)}{n-1}$下降的越明显。基于这种贪心的思想，假设$n=\prod_{i=1}^m pr[i]$，其中$pr$是一个从小到大的质数列表。

从小到大枚举$m$，计算出$n$的值。如果发现$\dfrac{\varphi(n)}{n-1}< r$，那么可以不必再找下去，$n$将是一个候选的答案。如果$\dfrac{\varphi(n)}{n-1}\ge r$，但是$\dfrac{\varphi(n)}{n}< r$ ，那么可以考虑寻找$n$的最小的倍数$k$，使得$\dfrac{\varphi(k)}{k}< r$，这些$k$也是一个候选答案。

这些候选答案的最小值就是最终答案，枚举速度很快。

代码

from sympy import nextprime
from fractions import Fraction
from math import ceil

U, D = 15499, 94744
f = Fraction(U, D)
p = 2
ans = 10 ** 100
phi, n = 1, 1
while True:
    n *= p
    phi *= p - 1
    if Fraction(phi, n - 1) < f:
        ans = min(ans, n)
        break
    elif Fraction(phi, n) < f:
        # 计算出，k至少是n的c倍时，才会有phi(k)/(k-1)<r。
        x = -f / (phi - n * f)
        c = ceil(x)
        if c == x:
            c += 1
        ans = min(ans, c * n)
    p = nextprime(p)
print(ans)