和の二乗差

Project Euler 6

1 から 10 までを二乗した和は \[1^2 + 2^2 + ･･･ + 9^2 + 10^2 = 385\] また、1 から 10 までの和を二乗した値は \[(1 + 2 + ･･･ + 9 + 10)^2 = 55^2 = 3025\] したがって、1 から 10 までの和を二乗した値と 1 から 10 までを二乗した和の差は、3025 - 385 = 2640 となる。
1 から 100 までの和を二乗した値と 1 から 100 までを二乗した和の差は？

---

もっとも単純にコーディングすると、以下の通りとなる。

# SAMPLE_1

N = 100

s = 0
p = 0
for i in range(1, N + 1):
    s += i ** 2
    p += i
print p ** 2 - s

一方、$(x + y)^2 - (x^2 + y^2)= x^2 + y^2 + 2xy - x^2 - y^2 = 2xy$ となるため、$(\sum x_n)^2 - \sum x_n^2 = \sum_{i\neq j}2x_ix_j$ である。
これを応用すると、累乗の計算が不要になる。

# SAMPLE_2

N = 100

ans = 0
for i in range(1, N + 1):
    for j in range(i + 1, N + 1):
        ans += 2 * i * j
print ans

しかし、最も単純なのは、数列の和の公式を利用することであろう。 \[1 + 2 + … + n = \frac{n(n + 1)}{2}\] \[1^2 + 2^2 + … + n^2 = \frac{n(2n+1)(n+1)}{6}\] これらを用いると、以下のようにコーディングできる。

# SAMPLE_3

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