Pythonで等差数列（AP）の中から素数Pの倍数となる最初の項を効率的に求める方法

初項 A と公差 D を持つ等差数列（AP）と、素数 P が与えられたとき、その等差数列の中で初めて素数 P の倍数になる項の位置（何番目の項か）を求める問題を考えてみましょう。

問題の例

たとえば、A = 3、D = 4、P = 5 という入力の場合、答えは 3 になります。これは、この等差数列の第4項（インデックス3）が素数 5 の倍数であるためです。

• 第1項 = 3
• 第2項 = 3 + 4 = 7
• 第3項 = 3 + 2×4 = 11
• 第4項 = 3 + 3×4 = 15（5 の倍数）

解法のアプローチ

k 番目の項は A + k×D で表されます。これが P の倍数になる条件は、次の合同式で表せます。

A + k×D ≡ 0 (mod P)

これを変形すると、k ≡ −A × D⁻¹ (mod P) となります。ここで必要になるのが D のモジュラ逆元です。P が素数であるため、フェルマーの小定理を利用すると、逆元は D^(P−2) mod P として高速に計算できます。

アルゴリズムの手順

• 繰り返し二乗法で冪乗を高速に計算する関数 get_pow(x, y, p) を定義する
  • ans := 1 で初期化
  • x := x mod p
  • y > 0 の間、以下を繰り返す
    • y の最下位ビットが 1 なら ans := (ans × x) mod p
    • y := y / 2（右シフト）
    • x := (x × x) mod p
  • ans を返す
• メイン処理では以下を実行する
  • A := A mod P、D := D mod P
  • A が 0 の場合 → 初項自体が P の倍数なので 0 を返す
  • D が 0 の場合 → 数列の値が変わらないため解は存在せず -1 を返す
  • それ以外の場合 → X := get_pow(D, P − 2, P) で逆元を求め、(X × (P − A)) mod P を返す

実装コード

それでは、実際のPython実装を見てみましょう。

def get_pow(x, y, p) :
    ans = 1
    x = x % p
    while y > 0 :
        if y & 1 :
            ans = (ans * x) % p
        y = y >> 1
        x = (x * x) % p
    return ans

def get_nearest(A, D, P) :
    A %= P
    D %= P
    if A == 0 :
        return 0
    elif D == 0 :
        return -1
    else :
        X = get_pow(D, P - 2, P)
        return (X * (P - A)) % P

A = 3
D = 4
P = 5
print(get_nearest(A, D, P))

入力

A = 3, D = 4, P = 5

出力

3

計算量について

この手法の優れた点は、数列の各項を順番に確認する必要がないことです。get_pow による繰り返し二乗法の計算量は O(log P) であり、全体として非常に効率的に動作します。仮に素朴な方法で各項を順にチェックすると、最悪の場合 O(P) 回の反復が必要になりますが、本手法では対数時間で答えが得られます。