Pythonでハッピー数（Happy Number）を判定する方法

ハッピー数とは？

ある正の整数 n が与えられたとき、それが「ハッピー数（Happy Number）」であるかどうかを判定することを考えます。

ハッピー数とは、任意の正の整数から出発し、その数を「各桁の数字の二乗の合計」で置き換える操作を繰り返したとき、最終的に 1 に到達する数 のことです。1 に到達できず、同じ値の循環に永遠に陥ってしまう場合はハッピー数ではありません。つまり、1 にたどり着ける数だけがハッピー数となります。

例：19 の場合

入力が 19 のとき、この数はハッピー数であるため結果は true になります。実際の計算の流れを見てみましょう。

• 1² + 9² = 82
• 8² + 2² = 68
• 6² + 8² = 100
• 1² + 0² + 0² = 1

このように 19 は最終的に 1 に到達するため、ハッピー数であると判定できます。

解決のための手順

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

• 動的計画法（メモ化）のアプローチを採用し、再帰によって解きます。
• ベースケース：n = 1 のときは true を返します。
• n がすでに訪問済み（計算済み）の場合は false を返します。これにより無限ループを防止できます。
• n を訪問済みとしてマークします。
• n を文字列に変換し、各桁の数字からなるリストを作成します。
• 各桁の二乗の合計を temp として計算します。
• temp と訪問済みリストを引数として、関数を再帰的に呼び出します。

実装例

以下の実装例を見ると、処理の流れがより理解しやすくなります。

class Solution(object):
    def isHappy(self, n):
        return self.solve(n, {})

    def solve(self, n, visited):
        if n == 1:
            return True
        if n in visited:
            return False
        visited[n] = 1
        n = str(n)
        l = list(n)
        l = list(map(int, l))
        temp = 0
        for i in l:
            temp += i ** 2
        return self.solve(temp, visited)

ob = Solution()
print(ob.isHappy(19))

入力

19

出力

True

コードのポイント

• visited 辞書によるメモ化： 一度計算した値を記録しておくことで、同じ数の循環に陥ったことを検知し、無限再帰を防ぎます。
• 桁ごとの分解： 数値を一度文字列に変換してからリスト化し、map 関数で整数に戻すことで各桁を簡単に取り扱えます。
• 再帰構造： 二乗和を求めるたびに自分自身を呼び出すことで、1 に到達するまで処理を繰り返します。

なお、同じロジックは再帰ではなく while ループを使った反復処理でも実装可能です。また、visited には辞書ではなく set を使うと、より簡潔に記述できます。

まとめ

ハッピー数の判定は、「各桁の二乗和の計算を繰り返し、最終的に 1 に到達するか」を確認するシンプルな問題です。再帰と訪問済み管理を組み合わせることで、循環を検知しながら効率的に判定できる点がポイントです。アルゴリズムの基礎練習としてもおすすめの題材なので、ぜひ自分でも実装してみてください。