素数に関連した確率の問題
はじめに
今日見たtweetにこんなのが。
1~Nから整数を1つ無作為に選んで x とするとき、 x の最大の素因数が √x 以上である確率 P(N) は、N→∞でぐふっ(絶命
— 齊藤 (tails) (@saito_ta) 2018年2月1日
これに対して、ちょっと計算してみて、でも前提を勘違いしていることに気が付いたのでこうtweetしたわけですが。
あー、√x 以上か…。√N 以上ならざっくり ln2 っぽい気がするけど…
— angel as ㌵㌤の猫 (@angel_p_57) 2018年2月1日
でも、結局$\ln{2}$で良いんじゃなかろうか? と思って記事にしてみました。
尤も、あんまり厳密な議論じゃないのですが、ざっくりと。
違う前提での計算
問題の整理
まず、「最大の素因数が$\sqrt{N}$以上である確率」と勘違いしていたわけですが、これは条件を満たす$N$以下の自然数の個数を$N$で割るだけですから、最終的に個数の問題に帰着できます。 そして、「最大の素因数が$\sqrt{N}$以上」これは単に「$\sqrt{N}$以上の素数の倍数」で、$N$以下の自然数の中に、$\sqrt{N}$以上の素因数を2種類持つ数はありませんから、個別に数えて足し込めば済みます。
つまり、個数を$S(N)$とすると、$S(N)=\sum_{q:prime,q\ge\sqrt{N}}\lfloor \frac{N}{q}\rfloor$
計算を進めるためのアプローチ
ここで、素数$q$を$\lfloor\frac{N}{q}\rfloor$の値で分類してみます。
例えばこの値が1なら、該当する素数は$\lfloor\frac{N}{2}\rfloor+1$以上$N$以下の素数、値が2なら、該当する素数は$\lfloor\frac{N}{3}\rfloor+1$以上$\lfloor\frac{N}{2}\rfloor$ 以下の素数といった具合に。
そのため、この分類値の上限を$m$とするとき、 $$ \begin{eqnarray} S(N)&=&\sum_{k=1}^{m} k(\pi(\lfloor\frac{N}{k}\rfloor)-\pi(\lfloor\frac{N}{k+1}\rfloor)) \\ &=&\{~\sum_{k=1}^{m} \pi(\lfloor\frac{N}{k}\rfloor)~\}- m\pi(\lfloor\frac{N}{m+1}\rfloor) \end{eqnarray} $$
※式の最後$m\pi(\lfloor\frac{N}{m+1}\rfloor)$、分数部分の分母を間違えて$m$としていたので訂正しました。以下の計算もそれに合わせて訂正しています。
なお、$\pi(x)$は、$x$以下の素数の個数を表すものとします。 これは、$\pi(x)\sim \frac{x}{lnx}$ と近似できるらしいので、$\pi(\lfloor\frac{N}{k}\rfloor)\sim\frac{N}{kln{(N/k)}}$ としておきます。
で、$x=log_N{k}=\frac{ln{k}}{ln{N}},~dx=\frac{dk}{kln{N}}$ として、総和を積分計算に変換すると、
$$ \begin{eqnarray} S(N)&\sim&\int_{0}^{log_{N}{m}} \frac{N}{kln{(N/k)}}\cdot kln{N}\cdot dx-\frac{m}{m+1}\cdot\frac{N}{ln{(N/(m+1))}} \\ &=&\int_{0}^{log_{N}{m}} \frac{Nln{N}}{ln{N}-ln{k}}\cdot dx-\frac{m}{m+1}\cdot\frac{N}{ln{(N/(m+1))}} \\ &=&\int_{0}^{log_{N}{m}} \frac{Nln{N}}{ln{N}-xln{N}}\cdot dx-\frac{m}{m+1}\cdot\frac{N}{ln{(N/(m+1))}} \\ &=&N\{~\int_{0}^{log_{N}{m}} \frac{dx}{1-x}-\frac{m}{m+1}\cdot\frac{1}{ln{(N/(m+1))}}~\} \\ \end{eqnarray} $$
で、$m\simeq\sqrt{N}$とすると、$log_{N}{m}\simeq\frac{1}{2}$で、結局積分の所だけが残るので、 $S(N)\sim N\int_0^{1/2}\frac{dx}{1-x}$、積分の値を計算してあげて$\frac{S(N)}{N}\simeq ln{2}$
…ということで、tweetした$ln{2}$が得られました。
ちなみに、$ln{2}\simeq 0.693147\cdots$ ですが、コードを組んで概算した結果とまあまあ合ってそうな気がします。
$ ruby -rprime -e 'p Prime.each(n=ARGV[0].to_i).drop_while{|q|q*q<n}.reduce(0){|s,q|s+n/q}.to_f/n' 1000000000 0.671100019
前提を戻して
さて、では正しい前提に戻して考えてみます。
…しかし、実を言うと勘違いしていた「最大の素因数が$\sqrt{N}$以上」これは、正しい前提の中に含まれます。なので、差分だけを考えれば良いはずです。 それは、「ある素数$q\lt \sqrt{N}$に対して、$q\times 1,~q\times 2,~\cdots,~q\times q$ のいずれかで表現できる数」これは、$q$毎に$q$個ずつあるはずです。
ということは、差分を$D(N)$とすると、
$$ D(N)=\sum_{q:prime,~q\lt \sqrt{N}} q $$
という訳です。
つまりは素数の合計なのですが…。良く分からないので、「素数になる確率」を重みづけした総和と考えてみます。この確率は、上で出てきた$\pi(x)$を微分したものになるはずです。なので、
$$ D(N)\sim \int_1^\sqrt{N} x\pi'(x)dx $$
ここで、部分積分$\int x\pi'(x)dx=x\pi(x)-\int\pi(x)dx$を考えると、この$D(N)$は高々$\sqrt{N}\pi(\sqrt{N})\sim\frac{N}{ln{\sqrt{N}}}$ で抑えられるはずです。 ということは、$N\rightarrow \infty$ で $\frac{D(N)}{N}\rightarrow 0$
結局、差分の影響は消えてしまうので、答えは同じく$ln{2}$ではないかなあ? ということでした。
終わりに
といってもオチは特にないんですが…。さてこの計算、どうなんでしょうね?