243. 最简分数(Resilience)

分子小于分母的正分数被称为真分数。对于分母\(d\)共有\(d-1\)个真分数,例如当\(d = 12\)时为:

$$ 1/12、2/12、3/12、4/12、5/12、6/12、7/12、8/12、9/12、10/12、11/12 $$
我们称不能被约简的分数为最简分数。进一步地,我们可以定义分母的不可约度\(R(d)\)为它的真分数中不可约分数的比例,如\(R(12) = 4/11\)

事实上,\(d = 12\)是不可约度\(R(d) < 4/10\)的最小分母。求不可约度\(R(d) < 15499/94744\)的最小分母\(d\)

分析:这道题与我们在第六十九题第七十题比较类似,都是求欧拉函数\(\varphi(n)\)的最值。首先来看一下题目对分母不可约度\(R(d)\)的定义,它等于分母\(d\)对应的真分数中最简分数的比例,比如当分母为\(12\)时,真分数显然有\((12-1=11)\)个,而最简分数的个数即为小于\(12\)中数中与其素质的数的个数,也就是\(\varphi(12)=4\)。题目要求\(R(d)\)小于一个特定真分数的最小\(d\)值,所以我们有:

$$ R(d)=\frac{\varphi(d)}{d-1}<\frac{a}{b}, where\ a<b $$

我们知道可以用数\(n\)的质因数计算\(\varphi(n)\),即:

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

则我们有:

$$ R(d)=\frac{\varphi(d)}{d-1}=\frac{d}{d-1}\prod _{p\mid n}\left(1-{\frac {1}{p}}\right)=\frac{d}{d-1}\cdot\frac{\prod_{p|n}(p-1)}{\prod_{p|n}p}<\frac{a}{b} $$

我们设\(x=\prod_{p|n}(p-1),y=\prod_{p|n}p\),且设\(d=ky\),即\(d\)为连续素数乘积\(y\)的整数倍。则有:

$$ \frac{ky}{ky-1} \cdot \frac{x}{y} < \frac{a}{b} \Rightarrow ( bx-ay) k< -a $$

显然为解此不等式,\((bx-ay)\)必须要小于零,否则\(k\)就会成为一个负数,则有:

$$ ( bx-ay) < 0\Rightarrow \frac{y}{x} >\frac{b}{a} $$

因此,我们需要选择一定数量的连续素数,使其满足这个条件,假设满足这个条件的最小数量为\(n\),则当\(a=15499,b=94744\)时,\(n=9\),也就是至少需要前九个连续素数乘积才能满足这个条件。

在已知前九个连续素数相乘的情况下,我们可以求出\(y\)\(x\),我们有:

$$ k >\frac{a}{ay-bx} $$

我们需要满足这个条件的最小正整数\(k\),则有:

$$ k >\frac{a}{ay-bx} =\frac{15499}{15499\cdot 223092870-94744\cdot 36495360} \approx 3.61 $$

则显然\(k=4\),则有:

$$ d=ky=4\cdot 223092870=892371480 $$

显然这个题目在不写代码的情况下也可以解决,不过还是写了一小段代码,如下:

# time cost = 49.4 ms ± 395 µs

from sympy import prime
from fractions import Fraction as f
from math import prod

def main(a=15499,b=94744):
    fy = lambda n:prod([prime(i) for i in range(1,n+1)])
    fx = lambda n:prod([prime(i)-1 for i in range(1,n+1)])
    n = 1
    while True:
        if f(fy(n),fx(n)) > f(b,a):
            break
        n = n + 1
    k = int(a/(a*fy(n)-b*fx(n)))+1
    return k * fy(n)