Pythonで解く「強力な整数」問題：x^i + y^j の全組み合わせを効率的に列挙する

「強力な整数」とは何か

正の整数 x と y が与えられたとき、ある整数 n が n = xⁱ + y^j（i ≥ 0、j ≥ 0）の形で表せるとき、n を強力な整数（Powerful Integer）と呼びます。この記事では、bound 以下の値をもつ強力な整数をすべて列挙するアルゴリズムを、Python の実装例とともに分かりやすく解説します。

たとえば x = 2、y = 3、bound = 10 という入力に対しては、出力は [2, 3, 4, 5, 7, 9, 10] になります。それぞれの値は次のように構成されています。

• 2 = 2⁰ + 3⁰
• 3 = 2¹ + 3⁰
• 4 = 2⁰ + 3¹
• 5 = 2¹ + 3¹
• 7 = 2² + 3¹
• 9 = 2³ + 3⁰
• 10 = 2⁰ + 3²

解き方のアプローチ

基本となる考え方はシンプルで、xⁱ を外側のループで固定し、内側のループで y^j を順に増やしながら全探索するというものです。同じ値が異なる (i, j) の組から生まれることがあるため、結果は重複を自動的に排除できる集合（set）に格納します。

実装上の注意点は、x または y が 1 のケースです。1 のべき乗は常に 1 なので、そのままループを回すと無限ループに陥ってしまいます。そこで、該当する変数が 1 の場合には 1 回だけ計算してループを抜けるようにすれば、すべてのケースを統一的に扱えます。

Pythonでの実装例

class Solution:
    def powerfulIntegers(self, x, y, bound):
        res = set()
        i = 0
        # y^j の最小値は 1 なので、x^i + 1 が bound を超えたら探索終了
        while x ** i + 1 <= bound:
            j = 0
            # y^j を増やしながら条件を満たす値を記録
            while x ** i + y ** j <= bound:
                res.add(x ** i + y ** j)
                j += 1
                if y == 1:      # y = 1 のときは無限ループを防止
                    break
            i += 1
            if x == 1:          # x = 1 のときは無限ループを防止
                break
        return sorted(res)

ob = Solution()
print(ob.powerfulIntegers(2, 3, 10))

入力と出力

入力

x = 2, y = 3, bound = 10

出力

[2, 3, 4, 5, 7, 9, 10]

動作のポイント

• ループ終了条件：y^j の最小値は 1（j = 0 のとき）なので、xⁱ + 1 が bound を超えた時点で、それ以上 xⁱ を大きくしても答えは見つかりません。
• 重複の除去：たとえば 5 = 2¹ + 3¹ = 2² + 3⁰ のように、同じ値が複数の組み合わせから現れるため、set による重複管理が有効です。
• 境界ケース：x = 1 かつ y = 1 の場合は候補が 2 のみとなり、bound ≥ 2 のときだけ [2] を返します。

計算量

x^k ≤ bound となる最大の k を K、y^m ≤ bound となる最大の m を M とすると、調べる必要がある組み合わせは多くても (K + 1) × (M + 1) 個です。K ≒ log(bound) / log(x)、M ≒ log(bound) / log(y) であり、べき乗の増加は非常に速いため、bound が大きくなっても現実的な時間で処理できます。