Pythonで数値のスーパーディジット（デジタルルート）を求めるプログラム

スーパーディジットとは？

ある数値 n が与えられたとき、そのスーパーディジット（super digit）を求めることを考えます。スーパーディジットとは、1桁の数であればその数字そのものを指しますが、複数桁の数の場合は「各桁の合計」を計算し、その結果が1桁になるまでこの操作を繰り返した最終的な数字のことです。なお、この概念は一般的にデジタルルート（digital root）とも呼ばれています。

例えば、入力が n = 513682 の場合、出力は 7 になります。

(5 + 1 + 3 + 6 + 8 + 2) = 25
(2 + 5) = 7

解法のアルゴリズム

この問題は、次の手順に従って解くことができます。

• 合計値を格納する変数 s を 0 で初期化する
• n > 0 または s > 9 の間、以下を繰り返す
  • n が 0 になったら、n に s を代入し、s を 0 に戻す（次の桁合計のラウンドへ）
  • s に n を 10 で割った余り（最下位の桁）を加算する
  • n を 10 で整数除算して桁を一つずらす
• ループ終了後の s を返す

Pythonでの実装例

それでは、実際のコードを見てみましょう。

def solve(n):
    s = 0
    while(n > 0 or s > 9):
        if n == 0:
            n = s
            s = 0

        s += n % 10
        n //= 10

    return s

n = 513682
print(solve(n))

入力

513682

出力

7

補足：O(1)で求める数学的なテクニック

上記の実装は直感的で分かりやすい方法ですが、実はスーパーディジットには剰余演算（mod 9）を使った数学的な性質があります。デジタルルートは次の式で一度に求められます。

def solve_fast(n):
    if n == 0:
        return 0
    return 1 + (n - 1) % 9

これは「9で割った余り」とデジタルルートが密接に関係しているためです。大きな数値でも定数時間で計算できるため、競技プログラミングなどではこちらの方法が有効です。