Pythonで与えられた数値がワグスタッフ素数かどうかを判定する方法

ワグスタッフ素数とは？

ある数値 n が与えられたとき、その数がワグスタッフ素数（Wagstaff prime）であるかどうかを判定することを考えます。ワグスタッフ素数とは、次の形式で表される素数のことです。

(2^q + 1) / 3

ここで q は奇素数（2 以外の素数）でなければなりません。

具体例での確認

たとえば、入力が n = 683 の場合、出力は True になります。これは、683 を次のように表せるためです。

683 = (2¹¹ + 1) / 3 = 2049 / 3

この場合 q = 11 であり、11 は奇素数なので、683 はワグスタッフ素数であることがわかります。

判定の手順

この問題を解くには、以下の手順に従います。

• num が素数であり、かつ (num × 3 − 1) が 2 の累乗である場合 → True を返す
• 上記以外の場合 → False を返す

ポイントは、(num × 3 − 1) が 2 の累乗（つまり 2^q）になれば、num は自動的に (2^q + 1) / 3 の形を満たすという点です。あとは num 自身が素数であることを確認すればよいわけです。

サンプルコード

def isPrime(num):
    if num > 1:
        for i in range(2, num):
            if num % i == 0:
                return False
        return True
    return False

def power_of_two(num):
    return num and not(num & (num - 1))

def solve(num):
    if isPrime(num) and power_of_two(num * 3 - 1):
        return True
    return False

n = 683
print(solve(n))

入力

683

出力

True

コードの解説

isPrime 関数： 2 から num−1 まで順番に割り切れるかどうかを調べる、シンプルな試し割り法による素数判定を行います。

power_of_two 関数： ビット演算を使ったテクニックで、2 の累乗かどうかを判定します。「num & (num − 1)」が 0 になるのは num が 2 の累乗の場合だけです。これにより効率的にチェックできます。

solve 関数： 「num が素数」かつ「num × 3 − 1 が 2 の累乗」という 2 つの条件を確認し、両方が成立すればワグスタッフ素数として True を返します。