Problem 242

242 Odd Triplets

ある条件を満たす三つ組（実質的には二組）の奇数は，10^12以下では何個ありますか？

という問題．探索範囲が広いので，真面目にやると大変．

しかし，小さい数で試してみると…

計算される数列が自己相似性を持つことが分かる．

これはProblem 148と同様の状況．

そして，出来たコードがこれ．

import Data.List (unfoldr)
main :: IO ()
main = print.p242 $ 10^12
p242 :: Integer -> Integer
p242 = fst.foldl g (,).unfoldr f.(`div` 4).(+3)
f :: Integer -> Maybe (Int, Integer)
f  = Nothing
f n =let (q,r) = divMod n 2 in Just(fromIntegral r,q)
g :: (Integer, Int) -> Int -> (Integer, Int)
g (a, k)  = (a, k + 1)
g (a, k) 1 = (3^k + 2 * a, k + 1)

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

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

コンテンツ