C++で級数 1 + 22 + 333 + 4444 + … の初項からn項までの和をO(1)で求める方法

問題概要

この問題では、整数 N が与えられます。求めるのは、級数 1 + 22 + 333 + 4444 + 55555… の初項から第 N 項までの総和です。

具体例で問題を確認しましょう。

入力: N = 4
出力: 4800

解説:

1 + 22 + 333 + 4444 = 4800

解法のアプローチ

最も単純な解法は、級数の一般項を順に生成しながら第 n 項まで足し合わせることですが、この方法では O(n) の時間がかかります。

そこで、級数の総和を閉じた形の公式として導出すれば、O(1) の定数時間で答えを計算できます。

一般項の導出

対象となる級数は次の通りです。

1 + 22 + 333 + 4444 + 55555…

第 k 項は「数字 k が k 個並んだ数」を意味するため、次のように表せます。

第k項 = k × (10^k − 1) / 9

したがって、総和は以下のように書き直せます。

Sum = Σ[k=1..n] k × (10^k − 1) / 9
    = (1/9) × { (1×10^1 + 2×10^2 + 3×10^3 + … + n×10^n) − (1 + 2 + 3 + … + n) }
    = (1/9) × { (1×10^1 + 2×10^2 + 3×10^3 + … + n×10^n) − n(n+1)/2 }

ここで、等比数列の公式を項別微分することで得られる次の式を利用します。

Σ[k=1..n] k×x^k = x × (1 − (n+1)x^n + n×x^(n+1)) / (1 − x)^2

x = 10 を代入すると、

Σ[k=1..n] k×10^k = ( n×10^(n+2) − (n+1)×10^(n+1) + 10 ) / 81

これを総和の式に代入して整理すると、

Sum = (1/9) × { ( n×10^(n+2) − (n+1)×10^(n+1) + 10 ) / 81 − n(n+1)/2 }

    = (1/1458) × { 2×( n×10^(n+2) − (n+1)×10^(n+1) + 10 ) − 81×n×(n+1) }

    = (1/1458) × { (18n − 2)×10^(n+1) − 81n² − 81n + 20 }

これにより、級数の和を n だけの式で表すことができました。

C++での実装例

上記の公式を実装したプログラムがこちらです。

#include <iostream>
#include <math.h>
using namespace std;

int calcSumNTerms(int n) {
   return ( ( (18*n - 2)*(pow(10, n+1)) - 81*n*n - 81*n + 20 ) / 1458 );
}

int main() {
   int n = 5;
   cout << "The sum of series upto n terms is " << calcSumNTerms(n);
   return 0;
}

実行結果

The sum of series upto n terms is 60355

n = 5 の場合、1 + 22 + 333 + 4444 + 55555 = 60355 となり、公式による計算結果と一致していることがわかります。

計算量の評価

• 時間計算量: O(1) — pow 関数の呼び出しを除けば、定数時間で計算できます。
• 空間計算量: O(1) — 追加のメモリは不要です。

なお、n が大きくなると int 型では桁あふれ（オーバーフロー）が発生するため、実際に大きな n を扱う場合は long long 型や多倍長整数の利用を検討してください。