C++で級数 1+(1+2)+(1+2+3)+…+(1+2+3+…+n) の総和を求める方法

問題概要

この問題では、数値 n が与えられます。求めるのは、次の級数の総和です。

1 + (1+2) + (1+2+3) + (1+2+3+4) + … + (1+2+3+4+…+n)

入力例と出力例

入力:

n = 4

出力:

20

説明: (1) + (1+2) + (1+2+3) + (1+2+3+4) = 20

解法1: 二重ループを使う単純な方法

最もシンプルな解法は、外側のループで各項を順に生成し、内側のループでその項の値を計算して加算していく、二重ループを用いる方法です。

アルゴリズム

sum を 0 で初期化する
ステップ1: i を 1 から n までループする（i = 1 ～ n）
    ステップ1.1: j を 1 から i までループする（j = 1 ～ i）
        ステップ1.1.1: sum に j を加算する（sum += j）
ステップ2: sum を返す

実装例

この解法の動作を示すプログラムは以下の通りです。

#include <iostream>
using namespace std;

int calcSeriesSum(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            sum += j;
    return sum;
}

int main() {
    int n = 7;
    cout << "級数 1 + (1+2) + (1+2+3) + ... + (1+2+3+...+" << n << ") の和は " << calcSeriesSum(n);
    return 0;
}

出力

級数 1 + (1+2) + (1+2+3) + ... + (1+2+3+...+7) の和は 84

しかし、このアプローチは時間計算量が O(n²) となるため、n が大きくなると処理に時間がかかり、あまり効率的とは言えません。

解法2: 数学的公式を使う効率的な方法

より効率的な解法は、級数の総和を表す一般公式を導出することです。各項は三角数 k(k+1)/2 で表せるため、これを利用して式を変形できます。

sum = 1 + (1+2) + (1+2+3) + (1+2+3+4) + …
sum = Σ ( k(k+1)/2 )
sum = ½ ( Σk² + Σk )
sum = ½ [ n(n+1)(2n+1)/6 + n(n+1)/2 ]
sum = ½ × n(n+1) × [ (2n+1)/6 + 1/2 ]
sum = ½ × n(n+1) × (2n+1+3)/6
sum = ½ × n(n+1)(2n+4)/6
sum = n(n+1)(2n+4)/12

この公式を使えば、ループ処理を行わずに O(1) の定数時間で答えを求められます。

実装例

この解法の動作を示すプログラムは以下の通りです。

#include <iostream>
using namespace std;

int calcSeriesSum(int n) {
    return (n * (n + 1) * (2 * n + 4)) / 12;
}

int main() {
    int n = 7;
    cout << "級数 1 + (1+2) + (1+2+3) + ... + (1+2+3+...+" << n << ") の和は " << calcSeriesSum(n);
    return 0;
}

出力

級数 1 + (1+2) + (1+2+3) + ... + (1+2+3+...+7) の和は 84

まとめ

二重ループによる解法は直感的で理解しやすいものの、O(n²) の計算量が必要になります。一方、数学的に導出した公式 n(n+1)(2n+4)/12 を使えば、O(1) で瞬時に結果を取得できます。競技プログラミングや大きな n を扱う場面では、公式を活用した解法が圧倒的に有利です。