流れる空の中で数学を。

とある数学好きの「手作りすうがく」と「気ままな雑記」。

【素因数の個数】

Python オリジナルプチ研究数学数論素因数分解

Nの素因数分解

$N=p_1^{r_1} \cdots p_n^{r_n}$

と因数分解されたとき、素因数の個数

$r=r_1+\cdots+r_n$

を考える。これの最大値は、

$r\le \frac{\ln N}{\ln 2}$

となる。実際、 $N=10^5$ までの値をシミュレーションしてプロットすると、次の図のようになる。

f:id:FoxQ:20210902184615j:plain — r(N)の分布と $\ln N/ ln 2$

\ln N/ ln 2 — r(N)の分布と $\ln N/ ln 2$

平均化

自然数 $r_{mod}$ を考えて、

$r(N)=\frac{r(N)+\cdots+r(N+r_{mod})}{r_{mod}}$

として計算してみる。

$r_{mod}=N/100$ のとき、 $N=10^5$ まででは $\frac{\ln N}{\ln 4.7}$ で抑えられる。

f:id:FoxQ:20210902185223j:plain — 平均化したr(N)の分布と上からの評価

$N=10^{k-1}+1 \sim 10^k$ の区間で、 $r_{mod}=10^{k-1}$ として、プロットすると、

f:id:FoxQ:20210902190021j:plain — r(N)の区間ごとの平均化

このように平均化すれば、平均化された $r(N)$ は上から5で抑えられるように見える。