Project Euler 243: Find fractions that cannot be cancelled down (resilient fraction)

Problem Description

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) < ¹⁵⁴⁹⁹/₉₄₇₄₄ .

Analysis

As you look at the list below some patterns become obvious.
1) All prime numbers, p, have an R(p) of 1.
2) The first and last fraction are always resilient. Always.
3) All fractions with a prime numerator that is not a factor of the denominator are resilient. So, for example, 5/8 is resilient where as 5/10 is not.

R(2) = 1/1 : 1/2
R(3) = 2/2 : 1/3 , 2/3
R(4) = 2/3 : 1/4 , 2/4 , 3/4
R(5) = 4/4 : 1/5 , 2/5 , 3/5 , 4/5
R(6) = 2/5 : 1/6 , 2/6 , 3/6 , 4/6 , 5/6
R(7) = 6/6 : 1/7 , 2/7 , 3/7 , 4/7 , 5/7 , 6/7
R(8) = 4/7 : 1/8 , 2/8 , 3/8 , 4/8 , 5/8 , 6/8 , 7/8
R(9) = 6/8 : 1/9 , 2/9 , 3/9 , 4/9 , 5/9 , 6/9 , 7/9 , 8/9
R(10) = 4/9 : 1/10 , 2/10 , 3/10 , 4/10 , 5/10 , 6/10 , 7/10 , 8/10 , 9/10
R(11) = 10/10 : 1/11 , 2/11 , 3/11 , 4/11 , 5/11 , 6/11 , 7/11 , 8/11 , 9/11 , 10/11
R(12) = 4/11 : 1/12 , 2/12 , 3/12 , 4/12 , 5/12 , 6/12 , 7/12 , 8/12 , 9/12 , 10/12 , 11/12 .

This is the same pattern that presented themselves in problems 69 and 70 where we were minimizing and maximizing n/φ(n). Here we limit φ(d)/(d-1) to 15499/94744.

This reduces the problem, as before, to multiplying sequences of primes. Which primes becomes a trial and error but multiplying over 23 was too much. The range was some multiple of the the product of the prime number from 2 to 23.

Mathworld had a great explanation about the totient function and proved how this would work using the formula below:

So, the easiest way to solve these type of problems would be to multiply as many sequential primes together until φ(d)/(d-1) exceeds the ratio given. Then back down one prime and try smaller primes.

Here’s an example: For this problem we multiply sequential primes up to 29 which exceeds the ratio. We back down one prime to 23 and call the new product (2 x 3 x 5 x … x 23) p’. We now multiply p” by composite numbers (<29): 4(2x2), 6(2x3), 8(2x2x2), 9(3x3) until it exceed the ratio. We remove the last multiplication and the answer is served. [solution tid="abdc2ed36c" t_height="325"] [comments] [/comments]