module Problem70 where

import Control.Arrow
import Data.Function
import Data.List
import Data.Ord
import Prime

main :: IO ()
-- let n = p1.p2.. As we increase the number of primes the ration n/phi(n) falls, so
-- we take two primes, for one prime p & p-1 can never be permutation,
-- also n should be as lrage as possible, we could skip some starting primes
-- given phi(87109)=79180 -> n/phi(n) = 87109/79180
-- p1*p2/(p1-1)(p2-1)<p1/(p1-1)<87109/79180 => 79180p1<87109p1-87109 => p1>87109/7929 = 10.9
-- 2 is the smallest prime so 10^7 >= p1*p2 >= 11*p2 => p2 <= 10^7/11
main =
    print
        . fst
        . minimumBy (comparing snd)
        . map (fst &&& uncurry ((/) `on` fromIntegral))
        . filter (null . uncurry ((\\) `on` show))
        $ [ (p1 * p2, (p1 - 1) * (p2 - 1))
          | p1 <- primes
          , p2 <- takeWhile (<= 10000000 `div` p1) primes
          , p1 < p2
          ]
    where primes = getPrimesUpto (10000000 `div` 11)
