1からnまでのすべての数値の桁の合計を計算するアルゴリズム

この記事では、1からnまでの範囲に含まれるすべての整数について、それぞれの桁の合計を求め、その総和を計算するアルゴリズムを解説します。

例えば、54という数値の桁の合計は 5 + 4 = 9 です。このように、範囲内のすべての数値に対して桁の合計を求め、それらを足し合わせる必要があります。

ここで重要なのは、d桁の数値は全部で 10^{d - 1} 個存在するという事実です。これらのd桁の数値すべての桁の合計を求めるには、次のような再帰的な漸化式（漸化関係）を利用できます。

sum(10d − 1) = sum(10d−1 − 1) × 10 + 45 × (10d−1)

入力と出力

入力：
このアルゴリズムでは、範囲の上限値を受け取ります。例として 20 を指定します。
出力：
1からnまでのすべての数値の桁の合計。この場合、結果は 102 になります。

アルゴリズム

digitSumInRange(n)

入力： 範囲の上限値 n。

出力： 範囲（1〜n）内のすべての数値の桁の合計。

Begin
    if n < 10, then
        return n(n+1)/2
    digit := 数値nの桁数
    d := digit − 1
    digitサイズの place 配列を定義
    place[0] := 0
    place[1] := 45

    for i := 2 to d, do
        place[i] := place[i-1]*10 + 45 * ceiling(10^(i-1))
        power := ceiling(10^d)
        msd := n/power
        res := msd*place[d] + (msd*(msd-1)/2)*power +
               msd*(1+n mod power) + digitSumInRange(n mod power)
        return res
    done
End

処理の流れのポイント

• nが10未満の場合は、公式 n(n+1)/2 を使って直接計算できます。
• place配列には、1から10ⁱまでの桁の合計が格納され、計算の高速化に役立ちます。
• msd（最上位桁）を求めることで、大きな数値でも再帰的に分割して効率よく計算できます。

C++による実装例

#include<iostream>
#include<cmath>
using namespace std;

int digitSumInRange(int n) {
    if (n<10)
        return n*(n+1)/2;          // 1桁の数値なら公式で直接計算
    int digit = log10(n)+1;        // 数値nの桁数
    int d = digit-1;               // 桁数から1を引く

    int *place = new int[d+1];     // 1〜10^place[i]までの合計を格納する配列
    place[0] = 0;
    place[1] = 45;

    for (int i=2; i<=d; i++)
        place[i] = place[i-1]*10 + 45*ceil(pow(10,i-1));

    int power = ceil(pow(10, d));  // 10の冪乗を計算
    int msd = n/power;             // 最上位桁を求める
    return msd*place[d] + (msd*(msd-1)/2)*power +
        msd*(1+n%power) + digitSumInRange(n%power);   // 再帰的に合計を求める
}

int main() {
    int n;
    cout << "Enter upper limit of the range: ";
    cin >> n;
    cout << "Sum of digits in range (1 to " << n << ") is: " << digitSumInRange(n);
}

実行結果

Enter upper limit of the range: 20
Sum of digits in range (1 to 20) is: 102

このように、単純に各数値の桁を一つずつ足していく方法よりも、漸化式と再帰を組み合わせたこのアプローチの方が、大きなnに対してもはるかに高速に計算できる点が大きな利点です。