C++でマジックナンバー（桁の再帰和が1になる数）かどうかを判定する方法

本記事では、ある整数が「マジックナンバー」であるかどうかを判定するC++プログラムを紹介します。マジックナンバーとは、各桁の数字を再帰的に合計していき、最終的に1になる数のことです。

マジックナンバーとは？

例として、50311という数を見てみましょう。

50311 → 5 + 0 + 3 + 1 + 1 = 10
10 → 1 + 0 = 1

このように、桁の合計が最終的に1になれば、その数はマジックナンバーと呼ばれます。判定するには、数が1桁になるまで各桁の合計を繰り返し求める必要があります。

C++での実装例

#include <iostream>
using namespace std;

int isMagicNumber(int n) {
    int digit_sum = 0;
    while (n > 0 || digit_sum > 9) {
        if (n == 0) {
            n = digit_sum;   // 桁の合計を新しい数として再処理
            digit_sum = 0;
        }
        digit_sum += n % 10; // 最下位の桁を加算
        n /= 10;             // 桁を一つ削る
    }
    return (digit_sum == 1);
}

int main() {
    int number = 50311;
    if (isMagicNumber(number)) {
        cout << number << " is magic number";
    } else {
        cout << number << " is not magic number";
    }
}

実行結果

50311 is magic number

アルゴリズムの解説

このプログラムの仕組みは以下の通りです。

1. 各桁の抽出： n % 10 で最下位の桁を取り出し、n /= 10 でその桁を削除します。これを n が0になるまで繰り返し、各桁の合計を digit_sum に蓄積します。

2. 再帰的な合計： n が0になった時点で、まだ合計が2桁以上（digit_sum > 9）であれば、その合計値を新たな n として同じ処理を繰り返します。

3. 判定： ループを抜けたときに digit_sum が1であれば、その数はマジックナンバーです。

なお、マジックナンバーの判定にはデジタルルート（digital root）の性質を利用する方法もあります。数を9で割った余りを用いることで、より効率的に判定することも可能です。具体的には、数が正であり n % 9 == 1 を満たす場合、その数はマジックナンバーであると分かります。