Pythonでgcd(N^M, N&M)が最大になる正の整数Mを求める方法

問題概要

正の整数 N が与えられたとき、M ＜ N を満たす正の整数 M のうち、gcd(N^M, N&M)（N^M はビットごとのXOR、N&M はビットごとのAND）が最大になるものを見つけます。そして、得られた最大のgcdの値を返します。

例えば、入力が 20 の場合、出力は 31 になります。

解法のポイント

この問題の鍵は、XORとANDのビットレベルでの性質にあります。あるビット位置において、N と M のビットが異なれば XOR では 1 になり、両方とも 1 のときにだけ AND が 1 になります。

N のビット長を k とすると、M として「N の各ビットを k ビットの範囲で反転した値（補数）」を選ぶと、N^M はすべてのビットが 1 の値 2^k − 1 になり、N&M は 0 になります。gcd(2^k − 1, 0) = 2^k − 1 となるため、これが最大値になります。

ただし、N 自体が 2^k − 1 の形（すべてのビットが 1）である場合は注意が必要です。この場合、補数は 0 になってしまい、M は正の整数という条件を満たせません。そこで、N の最大の真の約数、すなわち「N を最小の素因数で割った値」が答えになります。

アルゴリズムの手順

• N が 2^k − 1 の形（すべてのビットが 1）かどうかを判定します。
• その場合：
  • 2 から √N までの各整数 i について、N が i で割り切れるならば N / i を返します（N 未満の最大の約数）。
  • 見つからなければ 1 を返します（N が素数の場合）。
• そうでない場合：
  • N の 0 のビットの位置に対応する 2 のべきの総和 val（＝k ビット内での補数）を求めます。
  • gcd(val XOR N, val AND N) を返します。

Python実装例

from math import gcd, sqrt

def maximum_gcd(n):
    # N が 2^k - 1（すべてのビットが 1）の場合
    if (n & (n + 1)) == 0:
        # N 未満の最大の約数（最小の素因数で割った値）を探す
        for i in range(2, int(sqrt(n)) + 1):
            if n % i == 0:
                return int(n / i)
        return 1  # 素数の場合
    else:
        # k ビット内でビットを反転した値（補数）を求める
        val = 0
        p = 1
        dupn = n
        while n:
            if (n & 1) == 0:
                val += p
            p *= 2
            n >>= 1
        return gcd(val ^ dupn, val & dupn)

n = 20
print(maximum_gcd(n))

入力

n = 20

出力

31

動作の解説（n = 20 の場合）

20 は 2 進数で 10100 です。0 のビットの位置（下位から 1、2、8 の位）に対応する値を足し合わせると、val = 1 + 2 + 8 = 11（2 進数で 01011）となります。この val が最適な M に相当します。

• val XOR n = 01011 XOR 10100 = 11111 = 31
• val AND n = 01011 AND 10100 = 00000 = 0

したがって、gcd(31, 0) = 31 となり、答えは 31 になります。

計算量

ビット反転のループは O(log N)、N が 2^k − 1 の形の場合の約数探索は O(√N) で行えるため、大きな N に対しても非常に効率的に動作します。