Problem 242

Project Euler Haskell

242 Odd Triplets
Problem 242 - Project Euler
ある条件を満たす三つ組（実質的には二組）の奇数は，10^12以下では何個ありますか？
という問題．探索範囲が広いので，真面目にやると大変．
しかし，小さい数で試してみると…
計算される数列が自己相似性を持つことが分かる．
これはProblem 148と同様の状況．
そして，出来たコードがこれ．

import Data.List (unfoldr)

main :: IO ()
main = print.p242 $ 10^12

p242 :: Integer -> Integer
p242 = fst.foldl g (0,0).unfoldr f.(`div` 4).(+3)

f :: Integer -> Maybe (Int, Integer)
f 0 = Nothing
f n =let (q,r) = divMod n 2 in Just(fromIntegral r,q)

g :: (Integer, Int) -> Int -> (Integer, Int)
g (a, k) 0 = (a, k + 1)
g (a, k) 1 = (3^k + 2 * a, k + 1)

foldとunfoldがあるので，fusionできそうだが…（どうなんでしょう，融合規則は聞きかじった程度）

結局，二進展開して(unfoldr f)，ある規則で畳み込んでいる(foldl g)．