Problem 242

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 (,).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).

More Reading
Newer// 進捗
Older// Problem 243