Title - Wake Up! Good Night*

Project Euler Problem 120

Posted on December 15, 2012

このブログで、数式とソースコードを書くテストとして、Project Eulerから1問を問いてみようと思います。

問題はこちら

まずは (a − 1)n + (a + 1)n を展開していきます。

展開すると以下のとおり偶数番目の項は相殺されます。


(a − 1)n + (a + 1)n = 2an + 2nC2an − 2 + ⋯

さらに、最後の項以外は、a2を項に含むため、

a2を法とした剰余は最後の項だけ考えれば良いことになります。

最後の項は、nが偶数の時は、常に2。nが奇数の時は、最後の項は2naとなるため、

a2 を法とした2naの最大値が rmax となります。

と言った感じで考えて行きまして。

Haskellで書いてみたソースは以下のようになりました。

listA :: [Int]
listA = [3..1000]

make2N :: Int -> Int
make2N a = if mod a 2 == 0 then a-2 else a-1

makeResult :: [Int] -> Int
makeResult = foldr (\a acc -> (make2N a)*a + acc) 0

main = print $ makeResult listA

プログラマではないので、イケてないかもですが、、そこはご容赦を。。

とりあえず、数式もソースコードも書けました。

ただ、書きながらちょっとイマイチなところもあったので、今後要改善ですね。

submit to reddit このエントリーをはてなブックマークに追加