problem070.hs

-- Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive
-- numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all
-- less than nine and relatively prime to nine, φ(9)=6.
--
-- The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.
--
-- Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.
--
-- Find the value of n, 1 < n < 10^7, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

import Data.Ord
import Data.List (permutations, sortOn, sort)
import Data.Ratio
import Control.Monad (guard)
import Primes (eulerTotient)

permOf x n = sort (show n) == sort (show x)

solve n = fst . head . sortOn (uncurry (%)) $ totientsTo n
  where
    totientsTo n = do
      x <- [2..(n-1)]
      let tot = eulerTotient x
      guard $ eulerTotient x `permOf` x
      return (x, tot)

main = print $ solve (10 ^ 7)