From ProgSoc Wiki

Solutions for Problem 243

A fraction whose numerator is less than its denominator is said to be a proper fraction. For a denominator d, there will be d - 1 proper fractions. A fraction is resilient if it cannot be reduced further.

Define the resilience of a denominator d to be given by R(d), the ratio of its proper fractions that are resilient. For example, if d is 12, the (11) proper fractions are:

1/12 2/12 3/12 4/12 5/12 6/12 7/12 8/12 9/12 10/12 11/12

and the resilient fractions are:

1/12 5/12 7/12 11/12

giving R(d) to be 4/11.

Find the smallest denominator d with R(d) < 15499/94744.

Haskell by SanguineV

Runtime: 7.016 ms

{- Generate prime numbers in the usual way. -}
primes :: [Integer]
primes = 2:3:primes'
  where
    1:p:candidates  = [6*k+r | k <- [0..], r <- [1,5]]
    primes'         = p : filter isPrime candidates
    isPrime n       = all (not . divides n) $ takeWhile (\p -> p*p <= n) primes'
    divides n p     = n `mod` p == 0

{- Determine the Euler Phi of a number "n" (the number of numbers less than "n" 
 - with greatest common divisor with "n" of 1).
 - Note: eulerPhi(a * b) == eulerPhi(a) * eulerPhi(b), although not used here, this
 - will be used later! -}
eulerPhi :: Integer -> Integer
eulerPhi n = sum $ snd $ unzip $ zip (filter (== 1) [gcd k n | k <- [1..n]]) $ repeat 1

{- Generate the list of primorials and their euler phi values. -}
primorialPhis :: [(Integer,Integer)]
primorialPhis = map (\x -> (product (take x primes),product (map eulerPhi (take x primes)))) [1..]

{- Convert a numerator and denominator into a double value. -}
conv :: Integer -> Integer -> Double
conv n  d = (fromIntegral n) / (fromIntegral d)

{- Find a number with a resilience ratio less than the one given.
 - ALGORITHM:
 - Note that the lowest values for resilience are the primorials*k for k in [1..] up
 - to the next primorial.
 - 1. Use the list of primorials and their phi values and a multiplier of 1.
 - 2. If the current head of the list (cpri) * m == the next primorial (npri)
 -    then drop the first element of the list, reset m and continue.
 - 3. If the current primorial * the multiplier has a lower resilience than
 -    the target value then return it, otherwise continue.
 - 4. Increment the multiplier and go to step 2. -}
findRlt :: Double -> Integer
findRlt val = inner primorialPhis 1
  where
    inner :: [(Integer,Integer)] -> Integer -> Integer
    inner ((cpri,cphi):(npri,nphi):pps) m | cpri * m == npri = inner ((npri,nphi):pps) 1
    inner ((cpri,cphi):pps) m | conv (cphi * m) ((cpri * m) - 1) < val = cpri * m
    inner pps m = inner pps (m + 1)

{- Find the first denominator with resilience less than 15499/94744. -}
main = print (findRlt (15499 / 94744))