DouKaku?

module Main (main) where

import Data.Tree
import System.Environment

primes :: [Integer]
primes = sieve [2..] where sieve (p:xs) = p:sieve [x | x <- xs, x `mod` p /= 0]

type Label = (Integer, Integer)

powers :: Integer -> [Integer]
powers = flip iterate 1 . (*)

mktree :: Int -> Label -> [[Integer]] -> Tree Label
mktree k l pss = unfoldTree phi (l,pss)
  where phi (x,[])     = (x,[])
        phi (x,ps:pps) = (x,zip (labels x ps) (repeat pps))
        labels (n,g) ps = zip (map (10*n +) [0..9]) (takeWhile (10^k >) (map (g*) ps))

gtree :: Int -> Tree Label
gtree k = snip $ mktree k (0,1) $ map powers $ take k primes
 where snip (Node x ts) = Node x (tail ts)

meertens :: Int -> [Integer]
meertens k = [ n | (n,g) <- flatten $ gtree k, n == g ]

main :: IO ()
main = putStr . unlines . map show . meertens . read . head =<< getArgs