module Problem243 where

import Prime
import Data.Ratio (Ratio, (%))

req :: Ratio Integer
req = 15499 % 94744
ps :: [Integer]
ps = map fromIntegral $ getPrimesUpto 100
pLast :: Integer
pLast =
    fst
        $ head
        $ dropWhile (\(n, phinbyn) -> phinbyn * (n % (n - 1)) >= req)
        $ zip ps
        $ scanl1 (*)
        $ map (\p -> (p - 1) % p) ps
ps' :: [Integer]
ps' = map fromIntegral $ takeWhile (<= pLast) ps


main :: IO ()
-- n=p1^a1, p2^a2, ... pk^ak
-- R(n)=phi(n)/(n-1)
main =
    print
        $ fst
        $ minimum
        $ filter (\(x, phix) -> phix % (x - 1) < req)
        $ map go
        $ tail
        $ mapM (\p -> zip (repeat p) [0 .. 3])
        $ reverse ps'
  where
    go = foldl
        (\(x, phix) (p, a) -> if a == 0
            then (x, phix)
            else (x * p ^ a, phix * p ^ (a - 1) * (p - 1))
        )
        (1, 1)
