Problem 243

Project Euler Haskell

243 Resilience
Problem 243 - Project Euler
おそらく簡単．
n未満でnを割り切る数の割り合いについて．
これは，どこかでみたような…
オイラーのΦ関数と関係あり．
素因数分解とΦ関数の関係を考えれば良い．

import Number (primes)
import Data.Ratio (Rational, (%))

main :: IO ()
main = print.p243 $ 15499 % 94744

p243 u = head [s * n | s <- [1..], ((s*n) % (s*n - 1)) * r < u]
    where (r, n) = bound u

bound :: Rational -> (Rational, Integer)
bound u = head.dropWhile ((>=u).fst).scanl (\(r, n) p -> (r * ((p-1) % p), n * p)) (1,1) $ primes