【和の2乗-2乗の和】一緒に考えませんか？ #Project Euler

問6

$(1+2+..+10)^2 - (1^2 + 2^2 + .. + 10^2) = 2640$

1～100の場合は？

Project Euler ※解法の公開は問1～100のみ可

考え方

計算すればいい

考え方2

ちょっと面白くないので別解を考えてみる

$(a + b + c + d)^2 = a^2 + b^2 + c^2 + d^2 + a(b+c+d) + b(a+c+d) + c(a+b+d) + d(a+b+c)$

$= a^2 + b^2 + c^2 + d^2 + 2(ab + ac + ad + bc + bd + cd)$

$= a^2 + b^2 + c^2 + d^2 + 2(a(b + c + d) + b (c + d) + c(d))$

つまり

$(a + b + c + d)^2 - (a^2 + b^2 + c^2 + d^2) = 2(a(b + c + d) + b (c + d) + c(d))$

具体的な数値を与えてみる

$(1 + 2 + 3 + 4)^2 = 2( 1(2 + 3 + 4) + 2(3 + 4) + 3(4) )$

x * [x+1..4]の和 (x: 1～4)を2倍しているように見えてくる

畳込みで表してみよう

2 * foldl (\acc x -> acc + (x * sum [x+1..100])) 0 [1..100]

毎回リストを走査するのがもったいない？

• 反対から畳込めば良さそう!!

2 * fst $ foldl (\(ans, total) x -> (ans + x * total, total + x)) (0, 0) [100,99..0]

末筆ながら

ご意見求む!!

2個目の回答は効率が良くなっているのか？

一般項があるはず

Haskellerさんへ

計算量, 見やすさ, 文化的な観点から見て改善点や他回答があればぜひお願いします！

スキル指標

実務1年程度のへっぽこプログラマーなので暖かくも厳しく見守ってください

読んだ本

• すごいH本
• 関数プログラミング実践入門 (途中)

つまり構文を知った程度で、関数型言語っぽい書き方を学び中です