Pythonでnの真の約数が偶数の完全平方数になる確率を求めるプログラム

整数 n が与えられたとき、その真の約数（n 自身を除く約数）の中から無作為に 1 つ選んだ際、それが「偶数の完全平方数」である確率を求める問題を考えます。

たとえば入力が n = 36 の場合、出力は 1/8 になります。これは、36 の真の約数が {1, 2, 3, 4, 6, 9, 12, 18} の 8 個あり、そのうち偶数かつ完全平方数に該当するのは 4 のみだからです。

解法のアプローチ

この問題は、次の手順に従って解くことができます。

• n を 4 で割った余りが 0 でない場合は 0 を返します（2 の指数が不足しているため、条件を満たす約数が存在しない）。
• それ以外の場合は、以下を実行します。
  • nc := n、ptr := 2 とし、空のリスト l を用意します。
  • ptr が nc の平方根以下である間、次を繰り返します。
    • a := 0 とします。
    • nc が ptr で割り切れる間、a を 1 増やし、nc を nc ÷ ptr の商（切り捨て）で更新します。
    • a > 0 の場合、a をリスト l に追加します。
    • ptr を 1 増やします。
  • nc > 1 の場合、1 をリスト l に追加します。
  • k := l[0]、d := k + 1、no := k ÷ 2 の切り捨てとします。
  • l の 2 番目以降の各要素 i について、d := d × (i + 1)、no := no × (i ÷ 2 の切り捨て + 1) とします。
  • d := d − 1 とします。
  • n 自身が完全平方数である場合、no := no − 1 とします。
  • d と no の最大公約数 g を求め、d := d ÷ g、no := no ÷ g として約分します。
  • no が 0 の場合は 0 を返し、そうでなければ分数 no/d を返します。

アルゴリズムのポイント

ある約数が偶数の完全平方数になるためには、素因数分解した際のすべての指数が偶数であり、かつ 2 の指数が 2 以上である必要があります。したがって、n = 2^k × … と素因数分解できるとき、2 の指数としては {2, 4, …, k} の ⌊k/2⌋ 通り、その他の素因数 pⁱ については {0, 2, …, i} の ⌊i/2⌋ + 1 通りが選べます。これらを掛け合わせることで、条件を満たす約数の個数が求まります。なお、n 自身が完全平方数の場合は「真の約数」の定義上 n を除外する必要があるため、1 を差し引きます。分母は全約数の個数から 1 を引いた値、つまり真の約数の総数です。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

from math import gcd

def solve(n):
    if n % 4 != 0:
        return 0
    else:
        nc = n
        ptr = 2
        l = []
        while ptr <= nc ** 0.5:
            a = 0
            while nc % ptr == 0:
                a += 1
                nc = nc / ptr
            if a > 0:
                l += [a]
            ptr += 1
        if nc > 1:
            l += [1]
        k = l[0]
        d = k + 1
        no = int(k / 2)
        for i in l[1:]:
            d = d * (i + 1)
            no *= int(i / 2) + 1
        d = d - 1
        if int(n ** 0.5) ** 2 == n:
            no -= 1
        g = gcd(d, no)
        d = d // g
        no = no // g
        if no == 0:
            return 0
        else:
            return str(no) + '/' + str(d)

n = 36
print(solve(n))

入力

n = 36

出力

1/8