素因数の個数
概要
素因数の個数（number of prime factors）とは、正の整数 $n$ の素因数の数え方で、相異なる素因数の個数 $\omega(n)$ と、重複を込めた個数 $\Omega(n)$ がある（$\omega(12)=2$、$\Omega(12)=3$）。$\Omega$ は完全加法的、$\omega$ は互いに素な積についてだけ加法的で、約数の個数とは $2^{\omega(n)}\le d(n)\le2^{\Omega(n)}$ で結びつき、$s>1$ で $\sum2^{\omega(n)}n^{-s}=\zeta(s)^2/\zeta(2s)$ である。$\Omega(n)$ は最大で $\log n/\log2$、$\omega(n)$ は最大でも約 $\log n/\log\log n$ だが、典型的な $n$ ではどちらも $\log\log n$ 程度である。
素因数の個数（number of prime factors）には 2 通りの数え方がある。$12=2^2\cdot3$ の素因数を種類だけ数えると $2$ と $3$ の $2$ 個、指数の重複も込めて数えると $2,2,3$ の $3$ 個である。前者を $\omega(n)$、後者を $\Omega(n)$ と書く。どちらも素因数分解の一意性によって定まる数論的関数で、約数関数 $d(n)$、Möbius関数 $\mu(n)$、Liouville関数 $\lambda(n)=(-1)^{\Omega(n)}$ と結びついている。
$\omega(n)$ と $\Omega(n)$ は個々の $n$ では不規則に変わる。素数では $1$、$2^m$ では $\Omega=m$ だが $\omega=1$ である。この記事では、定義と積に対する性質（prop-npf-additive）、約数の個数との関係（thm-npf-divisors）、Dirichlet 級数（thm-npf-dirichlet）を示し、$\omega(n)$ のとりうる最大の大きさが $\log n/\log\log n$ 程度であること（thm-npf-max-order）を証明する。一方、典型的な $n$ での大きさは $\log\log n$ 程度とずっと小さい。その平均は 算術関数の平均位数 の定理「素因数の個数の平均」、ほとんどすべての $n$ での振る舞いは Hardy–Ramanujanの定理(素因数の個数)、ずれの分布は Erdős–Kacの定理 で扱う。
定義
以下、$p$ はつねに素数を表し、$\sum_{p\mid n}$ は $n$ を割り切る素数にわたる和である。素数 $p$ と正の整数 $n$ について、$p^e\mid n$ となる最大の整数 $e\ge0$ を $v_p(n)$ と書く。$\log$ は自然対数である。
正の整数 $n$ を $n=p_1^{e_1}p_2^{e_2}\cdots p_r^{e_r}$（$p_1,\dots,p_r$ は相異なる素数、$e_i\ge1$）と素因数分解するとき、
$$
\omega(n):=r,\qquad\Omega(n):=e_1+e_2+\cdots+e_r
$$
と定め、$\omega(1)=\Omega(1)=0$ とする。$\omega(n)$ を $n$ の 相異なる素因数の個数、$\Omega(n)$ を 重複を込めた素因数の個数 という。
素因数分解 の一意性（素因数分解の一意性 の定理「算術の基本定理」）により、$r$ と $e_i$ は $n$ だけで決まるので、$\omega$ と $\Omega$ は矛盾なく定まる。定義を和の形に書くと
$$
\omega(n)=\sum_{p\mid n}1,\qquad\Omega(n)=\sum_pv_p(n)=\#\{(p,k)\mid k\ge1,\ p^k\mid n\}
$$
である（最後の式は、$v_p(n)=e$ のとき $p^k\mid n$ となる $k\ge1$ が $1,\dots,e$ の $e$ 個であることによる）。
積に対する振る舞いを述べるために、次の言葉を使う。
数論的関数 $f$ が 加法的 であるとは、互いに素な正の整数 $m,n$ についていつも $f(mn)=f(m)+f(n)$ が成り立つことをいう。すべての正の整数 $m,n$ について成り立つとき 完全加法的 という。
加法的なら $f(1)=f(1\cdot1)=2f(1)$ から $f(1)=0$ である。$f$ が（完全）加法的なら、$0$ でない複素数 $z$ について関数 $n\mapsto z^{f(n)}$ は（完全）乗法的である（$f$ が整数値のとき）。たとえば $\lambda(n)=(-1)^{\Omega(n)}$ が完全乗法的であることは $\Omega$ の完全加法性から従う（Liouville関数 の命題「完全乗法性と Möbius 関数との関係」）。
例
| $n$ | 素因数分解 | $\omega(n)$ | $\Omega(n)$ | $d(n)$ |
|---|---|---|---|---|
| $1$ | — | $0$ | $0$ | $1$ |
| $8$ | $2^3$ | $1$ | $3$ | $4$ |
| $12$ | $2^2\cdot3$ | $2$ | $3$ | $6$ |
| $30$ | $2\cdot3\cdot5$ | $3$ | $3$ | $8$ |
| $36$ | $2^2\cdot3^2$ | $2$ | $4$ | $9$ |
| $360$ | $2^3\cdot3^2\cdot5$ | $3$ | $6$ | $24$ |
| $1024$ | $2^{10}$ | $1$ | $10$ | $11$ |
| $30030$ | $2\cdot3\cdot5\cdot7\cdot11\cdot13$ | $6$ | $6$ | $64$ |
$30$ や $30030$ のように平方因数をもたない数では $\omega=\Omega$ で、$d(n)=2^{\omega(n)}$ である。$2^{10}$ は $\Omega$ が大きく $\omega$ が最小になる例である。$10^6$ 以下で $\omega(n)$ の最大値は $7$ で、それをとる最小の数は $510510=2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17$ である（$\omega(n)=7$ となる $n\le10^6$ は、$570570=2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot19$ などを含めて $8$ 個ある）。
基本的な性質
- $\Omega$ は完全加法的である。
- $\omega$ は加法的だが、完全加法的ではない。より正確に、正の整数 $m,n$ について $\omega(mn)=\omega(m)+\omega(n)-\omega(\gcd(m,n))$ である。
1：素因数分解の一意性により、すべての素数 $p$ で $v_p(mn)=v_p(m)+v_p(n)$ である。$p$ について足すと $\Omega(mn)=\Omega(m)+\Omega(n)$ である。
2：$mn$ を割り切る素数の集合は、$m$ を割り切る素数の集合 $A$ と $n$ を割り切る素数の集合 $B$ の和集合である（素数 $p$ が $mn$ を割り切れば $m$ か $n$ を割り切るので。素因数分解の一意性 の定理「Euclidの補題」）。$A\cap B$ は $\gcd(m,n)$ を割り切る素数の集合なので、$\#(A\cup B)=\#A+\#B-\#(A\cap B)$ から式を得る。$\gcd(m,n)=1$ なら $\omega(1)=0$ なので $\omega$ は加法的である。$m=n=2$ では $\omega(4)=1\ne\omega(2)+\omega(2)=2$ なので、完全加法的ではない。$\square$
すべての正の整数 $n$ について
$$
\omega(n)\le\Omega(n)\le\frac{\log n}{\log2}
$$
である。左の等号は $n$ が平方因数をもたないとき、右の等号は $n$ が $2$ の冪のときに限って成り立つ。
$n=\prod_ip_i^{e_i}$ とする。$e_i\ge1$ なので $\omega(n)=r\le\sum_ie_i=\Omega(n)$ で、等号はすべての $e_i$ が $1$ のとき、すなわち $n$ が平方因数をもたないときに限る。また $p_i\ge2$ なので $n=\prod_ip_i^{e_i}\ge\prod_i2^{e_i}=2^{\Omega(n)}$ で、等号はすべての $p_i$ が $2$ のとき（$n=1$ を含む）に限る。$\square$
約数の個数との関係
正の整数 $n$ について次が成り立つ。
- $n$ の正の約数のうち平方因数をもたないものの個数は $2^{\omega(n)}$ である。すなわち $\sum_{c\mid n}\mu(c)^2=2^{\omega(n)}$ である。
- $2^{\omega(n)}\le d(n)\le2^{\Omega(n)}$ である。どちらの等号も、$n$ が平方因数をもたないときに限って成り立つ。
1：$n=\prod_{i=1}^rp_i^{e_i}$ とする。$n$ の約数 $c$ は $c=\prod_ip_i^{f_i}$（$0\le f_i\le e_i$）の形で、$c$ が平方因数をもたないことはすべての $f_i$ が $0$ か $1$ であることと同値である。よってそのような $c$ は $\{p_1,\dots,p_r\}$ の部分集合と 1 対 1 に対応し、$2^r$ 個ある。$\mu(c)^2$ は $c$ が平方因数をもたないとき $1$、もつとき $0$ である（Möbius関数 の定義「Möbius関数の定義」）ので、和の式も成り立つ。
2：約数関数 の命題「約数関数の基本性質」の 2 により $d(n)=\prod_{i=1}^r(e_i+1)$ である。整数 $e\ge1$ について $2\le e+1\le2^e$ であり（右は $2^e=(1+1)^e\ge1+e$）、左の等号は $e=1$ のとき、右の等号も $e=1$ のときに限る（$e\ge2$ なら $2^e\ge1+e+\binom e2>1+e$）。$i$ について掛けると $2^r\le d(n)\le2^{e_1+\cdots+e_r}$ で、どちらの等号もすべての $e_i$ が $1$ のときに限る。$\square$
2 の不等式から、$\log d(n)$ は $\omega(n)\log2$ と $\Omega(n)\log2$ の間にある。$\omega(n)$ と $\Omega(n)$ の正規位数が $\log\log n$ であること（Hardy–Ramanujanの定理(素因数の個数)）と合わせると、任意の $\varepsilon>0$ について、ほとんどすべての $n$ で $2^{(1-\varepsilon)\log\log n}< d(n)< 2^{(1+\varepsilon)\log\log n}$ となる（HW60 Theorem 432、§22.13、p. 359）。
Dirichlet 級数
すべての正の整数 $n$ は、平方因数をもたない正の整数 $a$ と正の整数 $b$ によって $n=ab^2$ とただ 1 通りに書ける。
存在：$v_p(n)$ が奇数である素数 $p$ の積を $a$、$\prod_pp^{\lfloor v_p(n)/2\rfloor}$ を $b$ とすれば、各素数で $v_p(ab^2)=v_p(a)+2v_p(b)=v_p(n)$ なので $n=ab^2$ である。一意性：$n=ab^2$、$a$ が平方因数をもたないなら、各素数で $v_p(a)\in\{0,1\}$ と $v_p(n)=v_p(a)+2v_p(b)$ から、$v_p(a)$ は $v_p(n)$ の偶奇で決まり、$v_p(b)=(v_p(n)-v_p(a))/2$ も決まる。素因数分解の一意性により $a,b$ は決まる。$\square$
$\zeta(s)=\sum_{n\ge1}n^{-s}$ を Riemannゼータ関数 とする。実数 $s>1$ について
$$
\sum_{n=1}^\infty\frac{\mu(n)^2}{n^s}=\frac{\zeta(s)}{\zeta(2s)},\qquad\sum_{n=1}^\infty\frac{2^{\omega(n)}}{n^s}=\frac{\zeta(s)^2}{\zeta(2s)}
$$
である。左辺の級数は絶対収束する。
数論的関数 $f,g$ の Dirichlet 積を $(f*g)(n):=\sum_{c\mid n}f(c)g(n/c)$、恒等的に $1$ の関数を $\mathbf 1$ と書く（数論的関数 の定義「数論的関数と Dirichlet 積」）。$n$ が平方数のとき $1$、そうでないとき $0$ をとる関数を $q$ とする。
$(\mu^2*q)(n)$ は、$n$ の約数 $c$ で、$c$ が平方因数をもたず $n/c$ が平方数であるものの個数である。lem-npf-squarefree-square によりそのような $c$ はちょうど 1 つなので、$\mu^2*q=\mathbf 1$ である。また thm-npf-divisors の 1 は $\mu^2*\mathbf 1=2^{\omega}$ を意味する。
$s>1$ では $0\le\mu(n)^2\le1$、$0\le q(n)\le1$ なので、$\mu^2$、$q$、$\mathbf 1$ の Dirichlet 級数はどれも $\sum n^{-s}$ で上から押さえられて絶対収束する（Riemannゼータ関数 の定理「級数の収束」）。$q$ の級数は $\sum_{b\ge1}(b^2)^{-s}=\zeta(2s)$ である。数論的関数 の定理「絶対収束する Dirichlet 級数の積」を $\mu^2*q=\mathbf 1$ に使うと
$$
\Bigl(\sum_{n\ge1}\frac{\mu(n)^2}{n^s}\Bigr)\zeta(2s)=\zeta(s)
$$
であり、$\zeta(2s)\ge1>0$ で割って最初の式を得る。同じ定理を $\mu^2*\mathbf 1=2^{\omega}$ に使うと、$2^{\omega}$ の級数も絶対収束して $\zeta(s)\cdot\zeta(s)/\zeta(2s)$ に等しい。$\square$
この 2 つの式は HW60 Theorems 301–302（§17.8、p. 255）にある。
個々の値の大きさ
$\Omega(n)$ の最大の大きさは prop-npf-trivial-bounds で決まっている。$\Omega(n)\le\log n/\log2$ で、$n=2^m$ で等号になる。$\omega(n)$ はずっと小さい。$\omega(n)=k$ となる最小の $n$ は最初の $k$ 個の素数の積 $N_k:=p_1p_2\cdots p_k$（$p_1=2,p_2=3,\dots$）なので、$\omega$ の最大の大きさは $N_k$ の大きさで決まる。
- 任意の $\varepsilon>0$ について $n_0$ があって、すべての $n\ge n_0$ で
$$ \omega(n)\le(1+\varepsilon)\frac{\log n}{\log\log n} $$
である。 - $N_k$ を最初の $k$ 個の素数の積とすると、$k\to\infty$ のとき
$$ \frac{\omega(N_k)\log\log N_k}{\log N_k}\to1 $$
である。
とくに $\displaystyle\limsup_{n\to\infty}\frac{\omega(n)\log\log n}{\log n}=1$ である。
1． $g(t):=t(\log t-1)$ とおく。$g'(t)=\log t\ge0$（$t\ge1$）なので $g$ は $[1,\infty)$ で増加する。
$k:=\omega(n)\ge1$ とする。$n$ は相異なる $k$ 個の素数で割り切れ、$i$ 番目に小さい素数は $i+1$ 以上なので、$n\ge p_1\cdots p_k\ge2\cdot3\cdots(k+1)\ge k!$ である。$e^k=\sum_{j\ge0}k^j/j!\ge k^k/k!$ より $k!\ge(k/e)^k$ なので、$L:=\log n$ とおくと
$$
L\ge\log k!\ge k\log k-k=g(k)
$$
である。
$\varepsilon>0$ を固定し、$L\ge e$ とする（$\log L\ge1$）。$t_0:=(1+\varepsilon)L/\log L$ とおくと、$t_0\ge L/\log L\ge1$ で、
$$
g(t_0)=(1+\varepsilon)\frac{L}{\log L}\bigl(\log(1+\varepsilon)+\log L-\log\log L-1\bigr)\ge(1+\varepsilon)L\Bigl(1-\frac{\log\log L+1}{\log L}\Bigr)
$$
である。$(\log\log L+1)/\log L\to0$（$L\to\infty$）なので、$L_0$ があって $L\ge L_0$ なら右辺の括弧は $1/(1+\varepsilon)$ より大きく、$g(t_0)>L$ である。このとき $k\ge t_0$ とすると、$g$ の増加性から $g(k)\ge g(t_0)>L\ge g(k)$ となって矛盾する。よって $n\ge n_0:=e^{\max\{e,L_0\}}$ なら $\omega(n)< t_0$ である（$\omega(n)=0$ のときは明らか）。
2． $y:=p_k$ とおき、$\theta(y):=\sum_{p\le y}\log p$、$\pi(y)$ を $y$ 以下の素数の個数とする。$\log N_k=\theta(y)$、$\omega(N_k)=k=\pi(y)$ である。各 $\log p$ は $\log y$ 以下なので $\pi(y)\ge\theta(y)/\log y$ である。
$\theta(y)$ を下から押さえる。$\sqrt y< p\le y$ の素数は $\log p>\frac12\log y$ を満たし、$\sqrt y$ 以下の素数は $\sqrt y$ 個以下である。素数定理 の定理「Chebyshevの評価」の 2 の下からの評価 $\pi(y)\ge\frac{\log2}4\cdot\frac y{\log y}$（$y\ge2$）を使うと
$$
\theta(y)\ge\frac12\log y\,\bigl(\pi(y)-\sqrt y\bigr)\ge\frac{\log2}8\,y-\frac12\sqrt y\log y
$$
である。$\sqrt y\log y/y\to0$ なので、十分大きい $y$ で $\theta(y)\ge c\,y$（$c:=\frac{\log2}{16}$）である。$k$ が大きければ $\theta(y)>e$ でもあり、
$$
\frac{\omega(N_k)\log\log N_k}{\log N_k}=\frac{\pi(y)\log\theta(y)}{\theta(y)}\ge\frac{\log\theta(y)}{\log y}\ge\frac{\log y+\log c}{\log y}=1+\frac{\log c}{\log y}
$$
である。$k\to\infty$ で $y\to\infty$ なので、下極限は $1$ 以上である。一方 1 により、任意の $\varepsilon>0$ について上極限は $1+\varepsilon$ 以下である。よって極限は $1$ である。
最後の主張：1 から上極限は $1$ 以下で、2 の数列 $N_k$ に沿って $1$ に近づくので、上極限は $1$ である。$\square$
2 の収束は遅い。$k=10,100,300$（$p_k=29,541,1987$）での比 $\omega(N_k)\log\log N_k/\log N_k$ は $1.380$、$1.231$、$1.183$ で、上から $1$ に近づく。この主張は HW60 §22.10（pp. 354–355）にある（同書は素数定理の形の評価を使っている）。
典型的な大きさと分布
最大の大きさ $\log n/\log\log n$ に比べ、典型的な $n$ の $\omega(n)$ はずっと小さい。$10^6$ 以下の正の整数を $\omega(n)$ の値で分けると次のとおりである（$\log\log10^6=2.626\ldots$）。
| $\omega(n)$ | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ |
|---|---|---|---|---|---|---|---|---|
| $n\le10^6$ の個数 | $1$ | $78734$ | $288726$ | $379720$ | $208034$ | $42492$ | $2285$ | $8$ |
$\omega(n)=1$ の $n$ は素数の冪で、$\omega(n)=7$ の $n$ は $8$ 個しかない。このような分布については次の結果がある。
- 平均：$\sum_{n\le x}\omega(n)=x\log\log x+O(x)$、$\sum_{n\le x}\Omega(n)=x\log\log x+O(x)$（算術関数の平均位数 の定理「素因数の個数の平均」）。
- ほとんどすべての $n$ での大きさ：$\omega(n)$ と $\Omega(n)$ の正規位数は $\log\log n$ である。さらに、$\infty$ に発散する任意の関数 $\psi$ について、ほとんどすべての $n\ge3$ で $\lvert\omega(n)-\log\log n\rvert\le\psi(n)\sqrt{\log\log n}$ である（Hardy–Ramanujanの定理(素因数の個数)）。
- ずれの分布：すべての実数 $t$ について、$\omega(n)-\log\log x\le t\sqrt{\log\log x}$ を満たす $n\le x$ の割合は、$x\to\infty$ のとき標準正規分布の分布関数の値 $\Phi(t)$ に近づく。$\omega$ を $\Omega$ に替えても同じである（Erdős–Kacの定理）。
条件を外した反例
| 替える条件 | 例 | 成り立たなくなること |
|---|---|---|
| $\omega$ の加法性で、$m,n$ が互いに素という条件を外す | $m=n=2$ | $\omega(mn)=\omega(m)+\omega(n)$ |
| $d(n)=2^{\omega(n)}$ で、平方因数をもたないという条件を外す | $n=4$ | $d(4)=3$ だが $2^{\omega(4)}=2$ |
| $\Omega$ を $\omega$ に替えて、上界 $\log n/\log2$ の等号を考える | $n=2^m$（$m\ge2$） | $\omega(2^m)=1< m$ |
| thm-npf-max-order の 1 で、$n\ge n_0$ という条件を外す | $\varepsilon=0.3$、$n=N_{10}$ | $\omega(n)\log\log n/\log n=1.380\ldots>1.3$ |
1 行目：prop-npf-additive の 2 の証明のとおり $\omega(4)=1\ne2$ である。2 行目：$4$ の約数は $1,2,4$ の $3$ 個である（thm-npf-divisors の 2 の等号の条件が外れている）。3 行目：$\Omega(2^m)=m=\log2^m/\log2$ で $\Omega$ の上界は等号だが、$\omega$ は $1$ のままである。4 行目：$N_{10}=6469693230$ で、$\log N_{10}=22.59\ldots$、$\omega(N_{10})=10$ である。したがって $\varepsilon=0.3$ に対する $n_0$ は $N_{10}$ より大きくとらなければならない。thm-npf-max-order の 1 は十分大きい $n$ だけについての主張である。
補足
- Möbius 関数と Liouville 関数：$\mu(n)$ は、$n$ が平方因数をもたないとき $(-1)^{\omega(n)}$、もつとき $0$ である。$\lambda(n)=(-1)^{\Omega(n)}$ である（Möbius関数、Liouville関数）。2 つは平方因数をもたない $n$ で一致する。
- 完全数：奇数の完全数があるとすれば、$\omega$ と $\Omega$ がある程度以上大きいことが知られている（完全数 の定理「奇数の完全数の素因数の個数」）。
関連項目
- 前提: 素因数分解, 素因数分解の一意性, 数論的関数
- 関連する関数: 約数関数, Möbius関数, Liouville関数, Riemannゼータ関数
- 分布: 算術関数の平均位数, Hardy–Ramanujanの定理(素因数の個数), Erdős–Kacの定理
- 道具: 素数定理, 冪乗因数をもたない整数
- 応用: 完全数
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
