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