素数が関する計算量解析

素数が絡む計算量解析を紹介する。証明はせず、大雑把な評価を推定できるようになるのが目標。

1 素数定理
2 素数の逆数和
3 素因数の個数
4 原始根の探索アルゴリズム
5 約数の個数（大雑把な概算が外れる場合）
6 smooth-number
7 参考文献

素数を小さい方から順に $p_1,p_2,\ldots$と置く。

素数定理

素数定理：
$n$ 以下の素数の個数 $\pi(n)$ について、$$\begin{align}\pi(n)=&\Theta \left( \int_{x=2}^n \frac{1}{\log{x}} dx \right) \end{align}$$が成り立つ。

右辺を $\Theta(n/\log(n))$ とした形が計算量解析ではよく登場する（上から抑えるには、$x=\sqrt{n}$ で分けて台形近似する）。この定理は線形篩を用いた逆元の列挙など様々なアルゴリズムの計算量解析に出現する。
ここでは証明はせず、ざっくり漸近挙動を推定してみる。
$n$ が素数である確率は $n$ 以下の素数 $p_1,p_2,\ldots,p_k$ を用いて大体$$\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\ldots\left(1-\frac{1}{p_k}\right)$$と書ける。これは $p_i$ の倍数でない確率が $(1-1/p_i)$ であって、しかもその確率が独立であろうという推測に基づいている。等比級数の和の公式 $\frac{1}{1-x}=1 + x + x^2+\dots$ により
$$\left(\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\ldots\left(1-\frac{1}{p_k}\right)\right)^{-1}=\prod_{i=1}^k \left(1 + \frac{1}{p_i}+\frac{1}{p_i^2} + \dots\right)$$
である。右辺は総積を取ると $p_1,\ldots,p_k$ のみを素因数に持つ数の逆数和になっているから、少なくとも $n$ までの逆数和は全て登場する。$n$ までの逆数和で打ち切れば、 $\sum_{i=1}^n \frac{1}{n} = \Theta(\log n)$ より $n$ が素数となる確率はおよそ $O\left(\frac{1}{\log n}\right)$ 。$n$ 以下の素数の個数はこの確率を $2$ から $n$ まで積分すれば求まり、素数定理の式の上からの評価が得られた。総積の部分はメルテンスの第 3 定理 $\lim_{n\to\infty}\log n\prod_{p\le n}\left(1-\frac1p\right)=e^{-\gamma}$ として知られている。

素数の逆数和

素数の逆数和 $\sum_{p\leq n} 1/p$ はエラトステネスの篩（ふるい）の計算量解析に登場する。素数定理より $x$ が素数である確率がおよそ $1/\log(x)$ であったから、次のように推定できる（実際に正しい）：
$$
\begin{align}
\sum_{p\leq n} 1/p =& O\left(\int_{x=2}^n \frac{1}{x} \cdot \frac{1}{\log{x}} dx\right) \\
=& O(\log \log x)
\end{align}
$$必ずしも正しいとは限らないが、一般に $\sum_{p\leq n} f(p)=O\left(\int_{x=2}^n f(x) \cdot \frac{1}{\log{x}} dx \right)$ が成り立つだろうと期待できる。

素因数の個数

$n$ の素因数の個数 $\omega(n)$ は
$$\omega(n) = O\left(\frac{ \log n}{\log \log n}\right)$$
を満たす。

この評価は例えば Garner のアルゴリズムの計算量解析において現れる。推定も交えた計算でこの評価を捻り出してみる。
上から抑えたいので、$n=p_1p_2 \cdots p_{\omega(n)}$ と仮定してもよい。
素数定理により $\log(n)=\sum_{i=1}^{\omega(n)} \log(p_i) = \Theta(p_{\omega(n)})$ であろう。
つまり、$p_{\omega(n)}=\Theta(\log(n))$ であって、素数定理 $$\omega(n)=\Theta\left( \frac{p_{\omega(n)}}{\log(p_{\omega(n)})}\right)$$ に代入すると $\omega(n)=\Theta(\log(n)/\log\log(n))$ を得る。$n=p_1p_2\cdots p_{\omega(n)}$ を忘れると上からの評価になる。

原始根の探索アルゴリズム

ここまで紹介したテクニックを使ってmod p における原始根の探索アルゴリズムの計算量を推定しよう。このアルゴリズムは試行回数の期待値 $O((p-1)/\varphi(p-1))$ である。ただし $\varphi$ はオイラーのトーティエント関数。試行回数について次が成り立つと推定したい。

$$n/ \varphi(n)=O(\log\log(n))$$が成り立つ。

$n/\varphi(n)=\prod_{p\mid n} (1-1/p)^{-1}$ を上から評価したいから、$n=p_1p_2 \ldots p_{\omega(n)}$ として良い。
素数定理の項で推定したとおり、$\prod_{i=1}^{\omega(n)} (1-1/p_i)^{-1} = O(\log(\omega(n)))$ であるから、素因数の個数の項で求めた $\omega(n)$ の式を代入して $n/ \varphi(n)=O(\log\log(n))$ が推定値として得られる（実際に正しい）。

$n$ 以下の数のうち、$n^{1/u}$ 以下の素数を含まない数は $O(n/log(n))$ 個ある。これは、$n^{1/u}$ 以下の素数を因数に持つ確率がおよそ $1/log(n^{1/u})$ だからである（Buchstab function）。

約数の個数（大雑把な概算が外れる場合）

$N$ 以下の数についての約数の個数の和は $ \sum_{i=1}^N \lfloor N / i \rfloor = \Theta(N \log N)$ なので、$N$ の約数の個数のオーダーは $O(\log N)$ だろうという概算は正しくない（平均では正しい）。$O(N^{\varepsilon})$ は言える。

smooth-number

$x$ が $n^{1/u}$ 以下の素因数しか持たない確率はおおよそ $\frac{\log(n^{1/u})}{\log(x)}$ なので、$n$ 以下の数のうち、$n^{1/u}$ 以下の素因数しか持たない数は $\Theta(n)$ 個ある（正確には、Dickman functionよりおよそ $nu^{-u}$ 個なのでどこか定数倍を間違えているが…）。

参考文献

厳密な証明を書く実力がなくて無念。とはいえ、大雑把な推定で正しい値が得られるのは面白い。