PythonでNの桁の並べ替えがMの冪乗と一致するかを判定する方法

2つの正整数 n と m(2 ≤ n ≤ 10¹⁸、2 ≤ m ≤ n)が与えられたとします。この問題の目標は、数値 n の各桁を並べ替えてできる数(全桁の順列)の中に、m の冪乗と一致するものが存在するかどうかを調べることです。存在すれば「n の全桁の並べ替えのうち m の冪乗に等しいものがある」と答え、存在しなければその命題は偽と判断します。

具体例として、n = 7182、m = 12 のケースを考えてみましょう。1728 は 7182 の桁を並べ替えた数であり、さらに 1728 = 12³ が成り立ちます。したがって、この場合は「n の全桁の並べ替えは m の冪乗と一致する」と判断できます。

つまり、入力が n = 7182、m = 12 であれば、出力は「An all digit-permutation of n is equal to a power of m」となります。

解決のアプローチ

この問題は、次の手順で解決できます。

• check_power() 関数を定義します。引数として n と m を受け取ります。
  • temp_arr_1 := 新しいリスト
  • temp_arr_2 := 新しいリスト
  • n > 0 の間、次を繰り返します。
    • temp_arr_1 の末尾に (n mod 10) を追加
    • n := n ÷ 10 の商(小数点以下切り捨て)
  • m > 0 の間、次を繰り返します。
    • temp_arr_2 の末尾に (m mod 10) を追加
    • m := m ÷ 10 の商(小数点以下切り捨て)
  • temp_arr_1 から生成したセットと temp_arr_2 から生成したセットが同一であれば True を返す
  • そうでなければ False を返す
• メイン処理では、以下を実行します。
• power_array := サイズ 100 のリスト(すべて 0 で初期化)
• max_range := 10¹⁸
• power_array[0] := m
• i := 1
• (power_array[i - 1] × m) < max_range の間、次を繰り返します。
  • power_array[i] := power_array[i - 1] × m
  • i := i + 1
• j を 0 から i - 1 まで動かしながら、次を確認します。
  • check_power(n, power_array[j]) が True であれば、「An all digit-permutation of n is equal to a power of m」を返す
• どの候補とも一致しなければ、「No all digit-permutation of n is equal to a power of m」を返す

理解を深めるために、以下の実装例を見てみましょう。

実装例

def check_power(n, m):
    temp_arr_1 = []
    temp_arr_2 = []
    while (n > 0):
        temp_arr_1.append(n % 10)
        n //= 10
    while (m > 0):
        temp_arr_2.append(m % 10)
        m //= 10
    if (set(temp_arr_1) == set(temp_arr_2)):
        return True
    return False

def solve(n, m):
    power_array = [0] * 100
    max_range = pow(10, 18)
    power_array[0] = m
    i = 1
    while (power_array[i - 1] * m < max_range):
        power_array[i] = power_array[i - 1] * m
        i += 1
    for j in range(i):
        if (check_power(n, power_array[j])):
            return "An all digit-permutation of n is equal to a power of m"
    return "No all digit-permutation of n is equal to a power of m"

n, m = 7182, 12
print(solve(n, m))

入力

7182, 12

出力

An all digit-permutation of n is equal to a power of m

アルゴリズムのポイント

この手法が高速に動作する理由は、探索対象となる冪乗の個数が限られているからです。m ≥ 2 という制約があるため、10¹⁸ 未満の m の冪乗は最大でも約 60 個程度(log₂(10¹⁸) ≒ 59.8)しかありません。また、各候補との比較は桁の抽出と集合の比較だけで済むため、1 回あたりのコストもごくわずかです。その結果、n が最大値の 10¹⁸ であっても、全体の計算量は非常に小さく抑えられます。

なお、上記の実装では set を用いて「使用されている数字の種類」を比較しています。もし「同じ数字を同じ回数ずつ使う」という厳密な意味での全桁の並べ替え(アナグラム)を判定したい場合は、set の代わりに collections.Counter を使うことで、より正確な判定が可能になります。