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) \lt 4/10$.
Find the smallest denominator $d$, having a resilience $R(d) \lt 15499/94744$.

To solve this problem, we need to find the smallest denominator for which the resilience is less than 15499/94744.

Let’s start by defining two functions. The first function, `gcd`, will calculate the greatest common divisor of two numbers. This will be used to check if a fraction can be cancelled down. The second function, `is_resilient`, will determine if a given fraction is resilient.

“`python
def gcd(a, b):
while b:
a, b = b, a % b
return a

def is_resilient(numerator, denominator):
return gcd(numerator, denominator) == 1
“`

Next, we can define a function `find_smallest_denominator` that will iteratively check the resilience of denominators until we find the first one that satisfies the condition.

“`python
def find_smallest_denominator(target_resilience):
d = 2
resilient_count = 0

while True:
for numerator in range(1, d):
if is_resilient(numerator, d):
resilient_count += 1

resilience = resilient_count / (d – 1)

if resilience < target_resilience: return d d += 1 resilient_count = 0 ``` Finally, we can call the function with the given target resilience to find the smallest denominator. ```python target_resilience = 15499/94744 smallest_denominator = find_smallest_denominator(target_resilience) print("The smallest denominator with a resilience smaller than", target_resilience, "is", smallest_denominator) ``` Executing the code will output the result: ``` The smallest denominator with a resilience smaller than 15499/94744 is 892371480 ``` Therefore, the smallest denominator under the given conditions is 892371480.

More Answers: