题目243：分数的弹性
本帖最后由 永恒的蓝色梦想 于 2020-8-30 19:13 编辑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:
1/12 , 2/12 , 3/12 , 4/12 , 5/12 , 6/12 , 7/12 , 8/12 , 9/12 , 10/12 , 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) = 4/11 .
In fact, d = 12 is the smallest denominator having a resilience R(d) < 4/10 .
Find the smallest denominator d, having a resilience R(d) < 15499/94744 .
题目：
分子小于分母的正分数叫做真分数。
对于任何分母 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 的最小分母。
求最小的分母 d，使得弹性 R(d) < 15499/94744 。
本帖最后由 jerryxjr1220 于 2017-8-28 14:35 编辑
这题是“欧拉计划”的第243题，做完这题解锁了一个新的成就{:5_93:}
程序的话，先贴个Bruce Force的方法，大概要500多秒才能出结果。
import numpy as np
from numba import jit
@jit
def euler243(target, limit):
primes = np.ones(limit, dtype='int8')
for i in range(2, int(limit**0.5+1)):
primes = 0
plist=np.nonzero(primes).tolist()
PHI = np.zeros(limit+1, dtype='int32')
PHI[:2:1] = -1
for p in plist:
PHI = p - 1
for p in plist:
for k in range(p*p, limit+1, p):
PHI = PHI*(p-1)
for j in range(p*p, limit+1, p*p):
PHI = PHI*p
x = 2
while (PHI/(x-1)) >= target:
x += 1
else:
print(x)
return
euler243(15499/94744, 1000000000)
页:
[1]