Pythonで各桁の合計を1桁になるまで繰り返し計算する方法【デジタルルート】

正の整数 n が与えられたとき、そのすべての桁の数字を足し合わせて新しい数を作り、この操作を結果が10未満（1桁）になるまで繰り返すことを考えます。このようにして得られる「1桁に還元された数」はデジタルルート（数根）と呼ばれる有名な概念です。

例えば、入力が 9625 の場合、出力は 4 になります。計算の流れは以下のとおりです。

• 9 + 6 + 2 + 5 = 22
• 2 + 2 = 4

解法のアプローチ

この問題は、再帰呼び出しを利用すると簡潔に解くことができます。具体的な手順は次のとおりです。

• solve() メソッドを定義し、引数として n を受け取る
• n < 10 の場合、これ以上分解できないため n をそのまま返す（再帰の終了条件）
• 合計値 s を 0 で初期化する
• l に n の桁数（log₁₀(n) + 1 の小数点以下切り捨て値）を代入する
• l > 0 の間、以下の処理を繰り返す
  • s に n の最下位桁（n % 10）を加算する
  • n を 10 で整数除算（//）して更新する
  • l を 1 減らす
• すべての桁を加算し終えたら、solve(s) を再帰的に呼び出して結果を返す

Pythonでの実装例

import math

class Solution:
    def solve(self, n):
        if n < 10:
            return n
        s = 0
        l = math.floor(math.log(n, 10) + 1)
        while l > 0:
            s += n % 10
            n //= 10
            l -= 1
        return self.solve(s)

ob = Solution()
print(ob.solve(9625))

入力

9625

出力

4

よりシンプルな別解：文字列変換を活用

実は、math.log を使って桁数を求める必要はありません。数値を一度文字列に変換すれば、各桁の合計をもっと直感的に計算できます。

class Solution:
    def solve(self, n):
        if n < 10:
            return n
        s = sum(int(d) for d in str(n))
        return self.solve(s)

str(n) で数値を文字列化し、各文字を int に変換しながら sum() で合計するだけで、while ループや log 計算が不要になり、コードが大幅に読みやすくなります。

補足：O(1)で求められる数学的な公式

デジタルルートには、剰余演算を使った美しい性質があります。正の整数 n のデジタルルートは、次の式でたった1回の計算（定数時間 O(1)）で求められます。

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

例えば 9625 の場合、1 + (9625 − 1) % 9 = 1 + 3 = 4 となり、先ほどの再帰的な結果と一致します。非常に大きな数でも瞬時に答えが得られるため、競技プログラミングなどではこの公式が特に役立ちます。