Project Euler 006を解いてみる。「二乗和の差」

Project Euler 006

006

最初の10個の自然数について, その二乗の和は,

1^2 + 2^2 + ... + 10^2 = 385

最初の10個の自然数について, その和の二乗は,

(1 + 2 + ... + 10)^2 = 3025

これらの数の差は 3025 - 385 = 2640 となる.
同様にして, 最初の100個の自然数について二乗の和と和の二乗の差を求めよ.

->次の問題

考え方①

シンプルに1~100までの配列を作成し、2乗してから足すpow_sumと足してから2乗するsum_powを計算、その差を出します。

コード

euler006.py

import numpy as np


def main():
    n = 100
    num_arr = np.arange(1, n + 1)
    pow_sum = sum(num_arr ** 2)
    sum_pow = sum(num_arr) ** 2
    print(sum_pow - pow_sum)


if __name__ == '__main__':
    main()

考え方②

1~nまでの自然数の和は、等差数列の和の公式より

S_n = \frac{n(n+1)}{2}

で求められるのでこれを2乗すればOKです。
2乗和も公式より

S_n = \frac{n(n+1)(2n+1)}{6}

で算出できます。
あとは差を計算して完了です。
公式を使うとnが増えても計算量が同じでお得ですね。

コード

euler006.py

def main():
    n = 100
    pow_sum = n * (n + 1) * (2 * n + 1) // 6
    sum_pow = (n * (n + 1) // 2) ** 2
    print(sum_pow - pow_sum)


if __name__ == '__main__':
    main()

余談ですが、方法①のコードではn = 77936以上になると、sum_pow=-9223077348122983360とマイナスの値になってしまい正しい答えを返せなくなるようです。数が大きくなりすぎるためでしょうか。