Life Goes On

まあまあだけど楽しんでる方です

101問目

http://projecteuler.net/index.php?section=problems&id=101
一般項が n 次の多項式となる数列を、より低次の多項式で近似するとき、最初に不一致となる項を求め、その和を答える。
部分数列から次の項を推定して、その和を求めています。そのとき、階差数列を取ると次数が一つ下がるので、階差が定数となるまで繰り返して、そこから逆に元の数列を組み立てていきます。
他にもやり方は色々ありそう。

--import Control.Applicative
import Data.List

main = print $ sum $ euler101

euler101 :: [Integer]
euler101 = map snd $ takeWhile (\ (a, b) -> a /= b) $ zip (tail u) (map next $ tail $ inits u)
--euler101 = map snd $ takeWhile ((/=) . fst <*> snd) $ zip . tail <*> map next . tail . inits $ u

next :: [Integer] -> Integer
next [] = 0
next xs = last xs + next d
    where d = zipWith (-) (tail xs) xs
--next xs = (+) . last <*> next . (zipWith subtract <*> tail) $ xs

u :: [Integer]
u = [ sum $ map ((-n)^) [0..10] | n <- [1..] ]