Project Euler Problem 243 Solution


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

For any denominator, dd, there will be d1d - 1 proper fractions; for example, with d=12d = 12:

112,212,312,412,512,612,712,812,912,1012,1112.\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}.

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

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

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

Find the smallest denominator dd, having a resilience R(d)<1549994744R(d) < \frac{15499}{94744}.