素数に関連した確率の問題

はじめに

今日見たtweetにこんなのが。

これに対して、ちょっと計算してみて、でも前提を勘違いしていることに気が付いたのでこうtweetしたわけですが。

でも、結局$\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}$ではないかなあ? ということでした。

終わりに

といってもオチは特にないんですが…。さてこの計算、どうなんでしょうね?