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

一橋大学の入試問題

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

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

　「$\tan 1^{\circ }$は有理数か」(2006年 京都大学)

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

　で、今年のソレはコレ。

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

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

$(33-4)\times 8+6=238\leqq 250$

　いや、もっとラクして

$(33-3)\times 8+6=246\leqq 250$

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

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

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

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

では、半分以下ではなく、$\frac{1}{4}$ 以下と言われたらどうでしょう？

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

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

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

今回の入試問題的にはこの時点でほぼ $1000\times \frac{8}{35}\leqq 250$ が示されちゃいました。細かいこといえば、端数処理どうなってるのとか一緒にまとめて除外されちゃったかわいそうな子達 （$2,3,5,7$）の面倒もみてあげないととかありますが、本題ではないので誤差の範囲ということでテキトーに流します（雑


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

ひらめいた解法

合成数にその約数の整数倍を加えた数は確実に合成数で、言い換えれば素数候補はそれ以外の範囲にあるといえます。例えば $30(=2\cdot 3\cdot 5)$ と互いに素な整数は
$$\{\begin{array}{l}30n\pm 1\\ 30n\pm 7\\ 30n\pm 11\\ 30n\pm 13\end{array}\{n\in \mathbb{Z}\}$$
という $8$ パターンのうちのいずれかに該当します。ということは、$17(=30\cdot 1-13)$ 以上 $1003(=30\cdot 33+13)$ 以下の範囲の素数も必ずこれらのパターンに該当しているわけです。

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

$30mod7\equiv 2$、つまり、$30$ を $7$ で割ったあまりは $2$ ですので、先程の $8$ パターンを $\{m\in \mathbb{Z}\}$ として $n$ を $7m+\alpha$ で書き改めると

$\{\begin{array}{l}30(7m\pm 3)\pm 1\equiv (0\pm 3\times 2)\pm 1\equiv 0\\ 30(7m\pm 0)\pm 7\equiv (0\pm 0\times 2)\pm 0\equiv 0\\ 30(7m\mp 2)\pm 11\equiv (0\mp 2\times 2)\mp 3\equiv 0\\ 30(7m\pm 3)\mp 13\equiv (0\pm 3\times 2)\pm 1\equiv 0\end{array}(\mathrm{mod}7)$

つまりこれらの式は $7$ で割ったあまりが全部 $0$ になるように調整したもので、ざっくり $1\leqq m\leqq 4$ の $4$ 通りだけ考えても、$7$ の倍数はかなり除外されることがわかります。ということで $4$ 通り削って

$(33-4)\times 8+6=238(\leqq 250)$

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

$$(33-3)\times 8+6=246(\leqq 250)$$

で暗算余裕ですね。

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