1000以下の素数は250個以下であることを示せ、を包除原理でゴリ押す

こんにちは。

今日はすっかり有名になった題名の問題を解いていきたいと思います。

解答の方針

素数が250個以下＝合成数が750個以上なので、こちらを示しましょうか。

ある数nが素数であるかどうかを示すには√n以下の素数すべてで割り切れるかどうかを調べなければなりません（※）。

しかし、合成数であるかどうかは一つの素数で割り切れれば示せます。圧倒的に楽です。

現に、1000以下の数の半分は2の倍数なので（2は素数だよ）、一瞬で合成数が499個あることがわかりました。

なので、「じゃあ3の倍数とかでも調べれば一瞬じゃん！」と思ったかもしれません。

しかし、それでは6の倍数の数がダブってしまうんです。

例として10以下の自然数で見てみましょう。

2の倍数は5個(2,4,6,8,10)、3の倍数は3個(3,6,9)ですが、6がダブっていますね。

なので、このダブりをどうにか除外しなければいけません。そこで包除原理が登場します。

（※）nが素数かどうか判定するためには√n以下の素数で割り切れるかどうかを試せばよいです。例えば、91=7×13で試してみましょう。√91=8.…なので、2,3,5,7で割り切れるかどうかを試せばいいです。ではなぜ、それより大きい素数、11,13,17,19…などで試さなくてもいいのか、ですが、それは素因数分解するとき、必ずペアで数が分解されるからです（今回は7のペアは√91以上の13です）。なので√91以上の素数で素因数分解できた！となれば√91以下にそのペアがいないとおかしいわけです（掛け算だからね）。

包除原理とは？

数Aかそこらで習うやつです。見ればわかりますよ。

|A∪B|=|A|+|B|-|A∩B|

これは要素が2つの場合ですね。

例として、|A|は1000以下の2の倍数の要素の数、|B|は1000以下の3の倍数の要素の数としてみましょう。|A∩B|はAかつBなので6の倍数ですね。よって、

|A∪B|=|A|+|B|-|A∩B|=[1000/2]+[1000/3]-[1000/6]=500+333-166=667

（[n]はnの整数部分です。ガウス記号ってやつです。）

目標は750個なのでまだまだ足りませんね。ダブりが166個もあったとは…

要素を3つに増やしてみましょう。P(C)を導入します。

|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|

これを習った人は少ないかもしれませんね。（大丈夫ですよ）

|C|を1000以下の5の倍数の要素の数とすると、（計算を省いて）734個です。惜しい！あと16個なんですけどね。さてどうしましょうか…

ルート１）根気で合成数を16個探す

これくらいなら探しちゃいましょう。でも2,3,5で合成数はもう作っちゃったので7,11,13,17,19くらいで作りましょうか。7^2,7^3,11^2,13^2,17^2,19^2,7×11,7×13,7×17,7×19,11×13,11×17,11×19,13×17,13×19,17×19

合計16個です。これで証明終了です。

ルート2)要素が4つの場合の包除原理を使う

こんなの知りません。しかし、あるみたいですよ。要素がn個の場合で一般化されてるみたいです。

これだけ見てもわからないと思うので、言葉で説明します。n=2,3の場合と照らし合わせてみてください。

まず、個々の要素を足します。それからすべての集合から2つ選び、その共通の要素数を足し合わせたものを引きます。nC2ってことですよ。同じように3つのを足し合わせてそれを足します。+と-は交互です。それを続けていきます。では4つの場合でやってみましょうか。

まず、個々の要素数を足し合わせます。

|A|+|B|+|C|+|D|

次に2つを組み合わせます。ちゃんと4C2=6個の項があるかどうか確認してください。引き算なのを忘れずに

-|A∩B|-|A∩C|-|A∩D|-|B∩C|-|B∩D|-|C∩D|

次は3つです。4C3なので4項あります。今度は足し算ですよ。

+|A∩B∩C|+|A∩B∩D|+|B∩C∩D|+|A∩C∩D|

最後に4つ全部組み合わせましょう。引き算ですよ

-|A∩B∩C∩D|

これらを組み合わせると、

|A∪B∪C∪D|=|A|+|B|+|C|+|D|-|A∩B|-|A∩C|-|A∩D|-|B∩C|-|B∩D|-|C∩D|

+|A∩B∩C|+|A∩B∩D|+|B∩C∩D|+|A∩C∩D|-|A∩B∩C∩D|

これで、|D|を7の倍数の個数とかにしてしまえばできそうですね。

実際計算してみると、

[1000/2]+[1000/3]+[1000/5]+[1000/7]

-[1000/6]-[1000/10]-[1000/14]-[1000/15]-[1000/21]-[1000/35]

+[1000/30]+[1000/42]+[1000/105]+[1000/70]

-[1000/210]

=500+333+200+142 -166-100-71-66-47-28 +33+23+9+14-4

=772

2,3,5,7を抜いて、768個が合成数であることが示せたので証明終了です。

単純で面白い問題でしたね。