题目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:
¹/₁₂ , ²/₁₂ , ³/₁₂ , ⁴/₁₂ , ⁵/₁₂ , ⁶/₁₂ , ⁷/₁₂ , ⁸/₁₂ , ⁹/₁₂ , ¹⁰/₁₂ , ¹¹/₁₂ .

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) = ⁴/₁₁ .
In fact, d = 12 is the smallest denominator having a resilience R(d) < ⁴/₁₀ .

Find the smallest denominator d, having a resilience R(d) < ¹⁵⁴⁹⁹/₉₄₇₄₄ .

题目：

分子小于分母的正分数叫做真分数。

对于任何分母 d，存在 d-1 个真分数；例如 d = 12 时有：
¹/₁₂ , ²/₁₂ , ³/₁₂ , ⁴/₁₂ , ⁵/₁₂ , ⁶/₁₂ , ⁷/₁₂ , ⁸/₁₂ , ⁹/₁₂ , ¹⁰/₁₂ , ¹¹/₁₂ 。

我们称一个不能化简的分数为弹性分数。
进一步我们定义分母的弹性 R(d)，即弹性分数与其真分数的比；例如，R(12) = ⁴/₁₁ 。
实际上, d = 12 为满足弹性R(d) < ⁴/₁₀ 的最小分母。

求最小的分母 d，使得弹性 R(d) < ¹⁵⁴⁹⁹/₉₄₇₄₄ 。

jerryxjr1220

这题是“欧拉计划”的第243题，做完这题解锁了一个新的成就

程序的话，先贴个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[i*i::i] = 0
        plist=np.nonzero(primes)[0][2:].tolist()
        PHI = np.zeros(limit+1, dtype='int32')
        PHI[:2:1] = -1
        for p in plist:
                PHI[p] = p - 1
        for p in plist:
                for k in range(p*p, limit+1, p):
                        PHI[k] = PHI[k//p]*(p-1)
                for j in range(p*p, limit+1, p*p):
                        PHI[j] = PHI[j//p]*p
        x = 2
        while (PHI[x]/(x-1)) >= target:
                x += 1
        else:
                print(x)
                return
euler243(15499/94744, 1000000000)