No.6 Sum square difference
問題.
Q. 1から10までの平方の和は,
1から10までの和の平方は,
で, その差は になります.
では, 1から100までの平方の和と和の平方の差はいくつになるか.
考え方とプログラム例(python)
この問題は単純に計算すれば良さそうです.LIST と map を利用して計算しました.
sum_square = sum(map(lambda x: x**2, range(1, 101))) square_sum = sum(range(1, 101))**2 print(square_sum - sum_square)
この方法では，1からまでの場合を考えたとき，計算量のオーダーは
になりますが，以下のようにすることで
で計算することもできます．
ちなみに, 1からまでの和と, 平方の和は,
\begin{align*}
1+2+\cdots+n &= \dfrac{1}{2}n(n+1)\\
1^2+2^2+\cdots+n^2 &= \dfrac{1}{6}n(n+1)(2n+1)
\end{align*}
なので, 1からまでの和の平方と平方の和の差は，
\begin{align*}
(1+2+\cdots+n)^2 - (1^2+2^2+\cdots+n^2) &= \left\{\dfrac{1}{2}n(n+1)\right\}^2 - \dfrac{1}{6}n(n+1)(2n+1)\\
&= \dfrac{1}{4}n^2(n+1)^2-\dfrac{1}{6}n(n+1)(2n+1)\\
&= \dfrac{1}{12}n(n+1)\{3n(n+1)-2(2n+1)\}\\
&= \dfrac{1}{12}n(n+1)(n-1)(3n+2)
\end{align*}
となるので,
n = 100 print(n * (n+1) * (n-1) * (3 * n + 2) / 12)
