# Euler Solution 243

### 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))