グッドスタイン数列

• 今日はハスケル勉強会
• Integer タイプという無限大桁の型を知る
• 以前気にして書いたグッドスタイン数列のハスケル関数を使ってみる
• nでのグッドスタイン数列の最初のm個を表示するには、こちらを使って

data Gen = G [Gen]

instance Show Gen
    where show (G x) = show x

main = do
    print $ goodstein 3
    print $ take 10 $ goodstein 4

goodstein :: Integer -> [Integer]
goodstein = takeWhile (> 0) . map snd . iterate next . (,) 2

next :: (Integer, Integer) -> (Integer, Integer)
next (e, n) = (e + 1, num (e + 1) (gen e n) - 1)

gen :: Integer -> Integer -> Gen
gen e 0 = G []
gen e n = G (x : xs)
    where i = floor $ (log $ fromIntegral n) / (log $ fromIntegral e)
          x = gen e i
          G xs = gen e (n - e ^ i)

num :: Integer -> Gen -> Integer
num e (G [])  = 0
num e (G (x:xs))  = (e ^ num e x) + num e (G xs)

mygoodstein n m = print $ take m $ goodstein n

*Main> mygoodstein 4 15
[4,26,41,60,83,109,139,173,211,253,299,348,401,458,519]