７０問目

http://projecteuler.net/index.php?section=problems&id=70
1 < n < 10⁷ で、かつ φ(n) が元の数の並べ替えになっているような n について、n/φ(n) が最小となるものを求める。
最初に書いたコードはこれです。brute force で素因数分解しながら、題意の条件を満たすものを抽出していきます。
やっぱり少し遅い。（コンパイル済みのコードで1〜2分）

import Data.List
import Data.Ord
import Data.Ratio

main = print $ euler070 9999999

euler070 :: Integer -> Integer
euler070 d = fst $ minimumBy (comparing (\ (a, b) -> a % b)) $
    filter perm [ (n, phi n) | n <- [2..d] ]

perm :: (Integer, Integer) -> Bool
perm (n, p) = (sort $ show n) == (sort $ show p)

phi :: Integer -> Integer
phi n = foldl (\ m d -> m - (div m d)) n $ nub $ factors n primes

factors :: Integer -> [Integer] -> [Integer]
factors n (p:ps)
    | q < p = [n]
    | r == 0 = p : factors q (p:ps) 
    | otherwise = factors n ps
    where (q, r) = divMod n p

primes :: [Integer]
primes = 2 : filter isPrime [3..]

isPrime :: Integer -> Bool
isPrime x = all ((/= 0) . mod x) $
    takeWhile (<= (floor $ sqrt $ fromIntegral x)) primes

φ(n) を最大にしたいんだから n の素因数の種類が少ないほどいいよね、n が素数だと駄目だけど、2つの素数の積ならいいんじゃない？ということがフォーラムに載ってました。それにしたがって修正。
2つの素数を √n に近い値にした方が φ(n) は大きくなるのですが、どこで足きりするかが微妙なところです。とりあえず1000以上の素数だけ調べることにしました。
1000というマジックナンバーが出てきてしまったのが嫌ですが、速いことは速いです。（コンパイルせずに数秒）

import Data.List
import Data.Ord
import Data.Ratio

main = print $ euler070 10000000 1000

euler070 :: Integer -> Integer -> Integer
euler070 m1 m2 = fst $ minimumBy (comparing (\ (a, b) -> a % b)) $
    filter perm [ (p1 * p2, (p1 - 1) * (p2 - 1)) |
    p1 <- takeWhile (< (div m1 m2)) ps,
    p2 <- takeWhile (< (div m1 p1)) ps ]
    where ps = dropWhile (< m2) primes

perm :: (Integer, Integer) -> Bool
perm (a, b) = (sort $ show a) == (sort $ show b)

primes :: [Integer]
primes = 2 : filter isPrime [3..]

isPrime :: Integer -> Bool
isPrime x = all ((/= 0) . mod x) $
    takeWhile (<= (floor $ sqrt $ fromIntegral x)) primes