第n項が n² − (n−1)² で表される級数の総和を求めるC/C++プログラム

数学にはさまざまな種類の級数が存在し、その多くはC言語やC++を使って効率的に計算することができます。本記事では、次の級数の総和を求めるプログラムを紹介します。

Tn = n2 - (n-1)2

この級数のすべての項の総和 S_n を、10⁹ + 7 で割った余り（mod）として求めます。総和は次のように定義されます。

S_n = T₁ + T₂ + T₃ + T₄ + …… + T_n

入力：229137999
出力：218194447

解説

T_n は 2n − 1 の形に変形できます。(n−1)² を展開して、実際に確認してみましょう。

=> Tn = n2 - (n-1)2
=> Tn = n2 - (1 + n2 - 2n)
=> Tn = n2 - 1 - n2 + 2n
=> Tn = 2n - 1

次に、この級数の総和 ∑T_n を求めます。

∑Tn = ∑(2n – 1)

この式をさらに変形すると、

=> ∑(2n – 1) = 2*∑n – ∑1
=> ∑(2n – 1) = 2*∑n – n

ここで、∑n は最初の n 個の自然数の総和を意味します。1 から n までの自然数の和は、有名な公式によって次のように表されます。

∑n = n(n+1)/2

この公式を代入すると、最終的な式は次のようにまとめられます。

∑Tn = (2 * n * (n+1) / 2) – n = n2

つまり、この級数の総和はシンプルに n² になると分かります。ただし、n² の値は非常に大きな数になる可能性があるため、結果は 10⁹ + 7 の mod で管理する必要があります。

そこで、mod乗算の性質を利用して n² をオーバーフローなしに計算します。

(a*b)%k = ((a%k)*(b%k))%k

プログラム例

#include <iostream>
using namespace std;
#define mod 1000000007
int main() {
   long long n = 229137999;
   cout << ((n%mod)*(n%mod))%mod;
   return 0;
}

出力：218194447

このように、数式的に総和が n² になると導くことで、各項を順番に足し合わせることなく、O(1) の計算量で答えを求めることができます。大きな n が与えられても、mod乗算の性質を組み合わせれば高速かつ正確に計算可能です。