Edited at

Multiplicative Persistence

Multiplicative Persistence 11を求めたという話題があったので、Pythonで実装しましたが、Haskellでも実装してみました。私のPCで0.76秒くらい。こういうときには遅延評価は便利ですよね。Python版では探索空間をさらに減らすことで0.02秒を実現しています。

module Main where

import Data.Char (digitToInt)

mps :: [(Integer, Int)]
mps = map calcMP targets
where
calcMP :: Integer -> (Integer, Int)
calcMP t = (t, calcMP' t)
calcMP' :: Integer -> Int
calcMP' t | t < 10 = 0
| otherwise = let t' = foldr (*) 1 $ map (fromIntegral . digitToInt) $ show t
in calcMP' t' + 1
targets :: [Integer]
targets = 2 : 3 : 4 : 5 : 6 : 7 : 8 : 9 : concatMap extend targets
extend :: Integer -> [Integer]
extend i = map (\j -> i * 10 + j) [fromIntegral (i `mod` 10)..9]

getMP :: Int -> (Integer, Int)
getMP limit = head $ dropWhile (\(_, mp) -> mp < limit) $ mps

main :: IO ()
main = print $ getMP 11
-- (277777788888899,11)