Pythonで数値の順列が3の倍数かつ回文になるかを判定する方法

はじめに

大きな正整数 N が与えられたとき、その数字を並べ替えてできる数（順列）の中に、「回文（逆から読んでも同じ数）」であり、かつ「3で割り切れる」ものが存在するかどうかを判定する問題を考えてみましょう。

例えば、132213 という数が与えられたとします。この数字を並べ替えると 123321 が作れます。123321 は回文であり、同時に3でも割り切れます。したがって、入力が 132213 の場合、出力は「1つ以上の順列が回文であり、3で割り切れる」となります。

解法の考え方

すべての順列を実際に生成して1つずつ確認するのは、桁数が大きくなると非現実的です。そこで、次の2つの数学的な性質を利用します。

• 3の倍数判定： 整数が3で割り切れるかどうかは、その各桁の合計で決まります。桁の並べ替えでは桁の合計は変わらないため、元の数が3の倍数なら、そのすべての順列も3の倍数になります。逆に、元の数が3の倍数でなければ、どの順列も3の倍数にはなりません。
• 回文の成立条件： 数字を並べ替えて回文を作れるためには、奇数個現れる数字が高々1種類である必要があります。回文では左右対称に同じ数字がペアで配置され、長さが奇数の場合にのみ中央に1つだけ余る数字が許されるためです。

アルゴリズムの手順

1. サイズ10の配列 digit_array を0で初期化し、input_sum を0にします。
2. input_num が0になるまで次を繰り返します。
   • input_sum に input_num の下一桁を加算します。
   • digit_array の対応するインデックスのカウントを1増やします。
   • input_num を10で整数除算します。
3. input_sum を3で割った余りが0でない場合は False を返します。
4. digit_array の中でカウントが奇数になっている数字の個数 index_odd を数えます。
5. index_odd が1より大きい場合は「回文かつ3の倍数となる順列は存在しない」を返します。
6. それ以外の場合は「1つ以上の順列が回文であり、3で割り切れる」を返します。

実装例

def solve(input_num):
    digit_array = [0] * 10
    input_sum = 0
    while (input_num):
        input_sum += input_num % 10
        digit_array[input_num % 10] += 1
        input_num //= 10
    if (input_sum % 3 != 0):
        return False
    index_odd = 0
    for i in range(10):
        if (digit_array[i] % 2 != 0):
            index_odd += 1
    if (index_odd > 1):
        return "No permutation is a palindrome and is divisible by three"
    else:
        return "One or more permutation is a palindrome and is divisible by three"

input_num = 132213
print(solve(input_num))

入力

132213

出力

One or more permutation is a palindrome and is divisible by three

まとめ

このアルゴリズムは、すべての順列を生成することなく、桁数に比例した時間計算量 O(d) で判定できます。「3の倍数の各桁の和に関する性質」と「回文における数字の出現回数の偶奇の条件」を組み合わせることで、非常に大きな数でも効率的に答えを求めることができます。