1000以下の素数は250個以下を暗算してみた

4986

1000以下の素数は250個以下を暗算してみた

一橋大学の入試問題

　普段は入試問題とか問題文を読むだけでちんぷんかんぷんな私ですが、ごくまれに学のない私にも解読可能なコトバで書かれたやさしい問題をお見かけします。

　「円周率は $3.05$ より大きいことを示せ」(2003年東京大学)

　「$\tan1^\circ$は有理数か」(2006年京都大学)

などなど。このくらいカンタンに書いてくださると「読める！読めるぞー！」って気分が味わえて「挑戦してみよかな」ってモチベにつながるわけですが、難解な数式とか専門用語とか並ぶともう意味わかんない＞＜

　で、今年のソレはコレ。

「$1000$ 以下の素数は $250$ 個以下であることを示せ」(一橋大学)

twitter の TL で拝見しまして、さっそく考えてみたところ

$(33-4)\times8+6=238\leqq250$

　いや、もっとラクして

$\Large (33-3)\times8+6=246\leqq250$

という直感が降りてきました。$\cdots$これだけでロジックが分かっちゃった方、かなり凄腕のエスパーです(；´∀｀)

ほとんどの方はエスパーではないと思われますので、本題に入る前に軽くウォーミングアップからしていきましょう。
$ $

まずはウォーミングアップ

「素数は整数全体の半分以下」と言われたら、さすがにこれは自明ですよね。そもそも人類(整数)の半分は偶数で、確実に合成数なのですから。$\cdots$今なにか意味不明な日本語が混じったようですが、お気になさらず(笑)

では、半分以下ではなく、$\frac14$ 以下と言われたらどうでしょう？

試しに $3$ の倍数も除外してみます。人類の $\frac13$ は $3$ の倍数なので、さきほどの素数候補 $\frac12$ のうちの $\frac13$ は $3$ の倍数です。つまり素数候補は $\frac12\times\frac23=\frac13$。もう少し削って $\frac14$ 以下にしたいところ。

$5$ の倍数も除外してみます。$\frac13\times\frac45=\frac4{15}$。分子を $4$ 倍すると分母を超えちゃうので、まだ $\frac14$ より大きいようです。

奮発して $7$ の倍数もいっちゃいましょう。$\frac4{15}\times\frac67=\frac8{35}$。分子を $4$ 倍しても分母を超えませんでしたので、ここで試合終了！

今回の入試問題的にはこの時点でほぼ $1000\times\frac8{35}\leqq250$ が示されちゃいました。細かいこといえば、端数処理どうなってるのとか一緒にまとめて除外されちゃったかわいそうな子達（$2,~3,~5,~7$）の面倒もみてあげないと、とか色々考えないといけませんが、この記事の本題ではないので誤差の範囲ということで雑に流します()

　$\cdots$さて、ウォーミングアップはこのあたりにして、そろそろ本編いきますね(*´∀｀*)
$ $

ひらめいた解法

合成数にその約数の整数倍を加えた数は確実に合成数で、言い換えれば素数候補はそれ以外の範囲にあるといえます。例えば $30~(=2\cdotp3\cdotp5)$ と互いに素な整数は
$$\quad\begin{cases} 30n\pm1\\ 30n\pm7\\ 30n\pm11\\ 30n\pm13 \end{cases}\quad\{n\in\mathbb{Z}\}$$
という $8$ パターンのうちのいずれかに該当します。ということは、$17~(=30\cdotp1-13)$ 以上 $1003~(=30\cdotp33+13)$ 以下の範囲の素数も必ずこれらのパターンに該当しているわけです。

$13$ 以下の素数は $2,~3,~5,~7,~11,~13$ の $6$ 個ですので、現時点で $1003$ 以下の素数候補数は $33\times8+6=270$ です。あと $20$ ほど削りたいですね。$2,~3,~5$ の倍数は既に除外されてますので、$7$ の倍数もテキトーに消すとしましょう。

$30\bmod7\equiv2$、つまり、$30$ を $7$ で割ったあまりは $2$ ですので、先程の $8$ パターンの $n$ を $7m+\alpha$ $\{m\in\mathbb{Z}\}$ として $7$ で割り切れるパターンを列挙してみると

$\begin{cases} 30(7m\pm3)\pm~~1\equiv(0\pm3\times2)\pm1\equiv0\\ 30(7m\pm0)\pm~~7\equiv(0\pm0\times2)\pm0\equiv0\\ 30(7m\mp2)\pm11\equiv(0\mp2\times2)\mp3\equiv0\\ 30(7m\mp3)\pm13\equiv(0\mp3\times2)\mp1\equiv0\\ \end{cases}\pmod{7}\quad$

となります。つまり $17$以上の数を $30\times7=210$ 個ずつブロックに区切って先程の素数候補のみに絞り込むと各ブロックに $7$ の倍数が必ず $8$ つ含まれていると言えるわけですね。

$1003$ までの数なら $4$ ブロック以上は確実にありますから試しに $4\times8$ だけ除外してみましょう。

$\large(33-4)\times8-4+6=238\quad(\leqq250)$

$1003$ 以下の素数は高々 $238$ 個以下であることが示されました。横着して $3$ 通りだけ削れば

$$\quad(33-3)\times8+6=246\quad(\leqq250)$$

で暗算余裕ですね。

以上により、$1000$ 以下の素数は $250$ 個以下です。
$ $

一般論

この考え方を整理すると、

エラトステネスの篩を $2,3,5$ までかけると
$30n+13$ 以下の数では $8n+6$ 個が素数候補として残る
$\tiny(2\times3\times5=30,~30\text{と互いに素な数は}8\text{個},~\text{13以下の素数は}6\text{個})$
エラトステネスの篩を $2,3,5,7$ までかけると
$210n+13$ 以下の数では $48n+6$ 個が素数候補として残る
$\tiny(2\times3\times5\times7=210,~(7n-n)\times8=48n)$