さえめろ の めも🐰

さえめろの備忘録です。twitter : @sae_mero_

プロジェクトオイラー#6 について

#6「二乗和の差」についてのお話。


問題は以下↓

最初の10個の自然数について, その二乗の和は,
12 + 22 + ... + 102 = 385
最初の10個の自然数について, その和の二乗は,
(1 + 2 + ... + 10)2 = 3025
これらの数の差は 3025 - 385 = 2640 となる.
同様にして, 最初の100個の自然数について二乗の和と和の二乗の差を求めよ.


この問題に対して、以前の私はこのようなコードをあげていた(Javascript)。

process.stdin.resume();
process.stdin.setEncoding('utf8');

// 和
var a = 0;
for(var i = 100; i>0; i--){
    a = a + i;
}

// 二乗の和
var b = 0;
for(var i = 100; i>0; i--){
    var n = i;
    n = n*n;
    b += n;
}

// 和の二乗 - 二乗の和
var total = a*a - b;
console.log(total);

このコードは足し算200回掛け算100回くらいの計算を行っています。
100までの自然数なので大丈夫ですが、桁が大きくなるにつれ爆発的に時間がかかるようになります。

そこで思い出した数列がこちら。

自然数1からnまでの部分和の公式
 f:id:saemero:20170508172240p:plain

自然数の二乗1からn^2までの部分和の公式
 f:id:saemero:20170508172249p:plain



上2つの数式をコードに落とし込むと、3行で終わります。

process.stdin.resme();
process.stdin.setEncoding('utf8');

var x = (100*101 / 2) * (100*101 / 2);
var y = 100*(100+1)*(200+1)/6;
console.log(x-y);

関数化するとこう

process.stdin.resume();
process.stdin.setEncoding('utf8');

function aaa(n){
    var x = (n*(n+1) / 2) * (n*(n+1) / 2);
    var y = n*(n+1)*(2*n+1)/6;
    return x-y
}
console.log(aaa(100));


10000くらいまでのループなら実行時間が両方0.06sと大して変わらなかったのですが、100000000くらいまでいくとループのコードは0.78s、公式を用いたコードは0.06sのままと大きな差ができました。
これくらいコードをキュッとできると気持ちいいね!!!

ついでにpythonでも同様のコードを書いた。

x = (100*101 / 2)**2
y = 100*(100+1)*(200+1)/6
print(x-y)

0.03sでした。