关于数学:欧拉项目-243题-最简分数

原文公布于我的小站

题目链接

分子小于分母的分数被称为真分数。比方 $d=12$，那么有 11 个真分数
$$\frac{1}{12},\frac{2}{12},\frac{3}{12},\frac{4}{12},\frac{5}{12},\frac{6}{12},\frac{7}{12},\frac{8}{12},\frac{9}{12},\frac{10}{12},\frac{11}{12}$$
其中分子分母不能约分的分数成为最简分数，用 $R(d)$ 来示意最简分数的个数与 $d-1$ 之比，比方 $R(12)=\frac{4}{11}$，事实上，$d=12$ 是最小的整数满足 $R(d)<\frac{4}{10}$ 的。
求最小的 $d$，使得 $R(d)<\frac{15499}{94744}$

一开始，我应用了暴力算法遍历 $d$，然而大概几十秒过来了，$d$ 都到了大几百万还是不满足题意。我须要先推理简化问题再写程序。
令 $d$ 有 $k$ 个质因数，那么 $d$ 能够写作
$$d=p_1^{q_1}p_2^{q_2}\cdots p_k^{q_k}$$
和 $d$ 互斥的因数个数是
$$(p_1-1)p_1^{q_1-1}(p_2-1)p_2^{q_2-1}\cdots (p_k-1)p_k^{q_k-1}$$
那么
$$\begin{aligned}R(d)&=\frac{(p_1-1)p_1^{q_1-1}(p_2-1)p_2^{q_2-1}\cdots (p_k-1)p_k^{q_k-1}}{d-1}\\&=\frac{d\cdot \frac{p_1-1}{p_1}\frac{p_2-1}{p_2}\cdots\frac{p_k-1}{p_k}}{d-1}\\&=\frac{d}{d-1}\frac{(p_1-1)(p_2-1)\cdots (p_k-1)}{p_1p_2\cdots p_k}\end{aligned}$$
因为后面我曾经晓得 $d$ 很大，那么 $\frac{d}{d-1}\to 1$。所以要先找到一些质数，使得
$$\frac{(p_1-1)(p_2-1)\cdots (p_k-1)}{p_1p_2\cdots p_k}<\frac{15499}{94744}$$
且再多一个质数就会不满足这个不等式。
要使得 $d$ 最小化，那么这些质数就是从 2 开始的后面这些质数，而后 $d$ 就是这些质数之积。当然，这个时候的 $d$ 可能不满足题意，因为疏忽了系数 $\frac{d}{d-1}$，然而 $d$ 的若干倍（倍数小于下一个质数）就会满足题意的。
其中 $c,d$ 要应用 long 的起因是 $p$ 很小但乘积可能超过 int 的示意范畴。

int[] primes = Utils.GenPrimes(50).Where(l => l != 0).Select(Convert.ToInt32).ToArray();
long c = 1;
long d = 1;
foreach (var p in primes)
{
    c *= p - 1;
    d *= p;
    if (c * 94744L < d * 15499L)
    {break;}
}
for (int i = 2; i <= primes.Last(); i++)
{
    long n = d * i;
    if (c * n * 94744L < d * (n - 1) * 15499L)
    {return n.ToString();
    }
}