京大数学のお株を奪うような非常にシンプルかつ興味深い設問です。
Wikipediaに掲載されている情報によれば1000以下の素数は全部で168個存在するようですが、円周率の桁宜しく素数を丸暗記しているような猛者でもない限り全てを試験場で書き出す解法は現実的ではありません。
1000以下の自然数から「素数になり得る候補」をどのように絞り込んでゆくかが、本問を解く上での鍵となります。
解答
1000以下の正の整数全体の集合をU、Uの要素のうち2の倍数、3の倍数、5の倍数であるもの全体の集合をそれぞれA, B, Cと定義する。更に、ある集合Xに属する要素の総数をn(X)のと表現する。
2, 3, 5はどの2つも互いに素である為、A∧B, B∧C, C∧A, A∧B∧Cはそれぞれ1000以下の正の整数のうち6, 15, 10, 30の倍数であるもの全体の集合である。従ってこれら集合に属する要素の総数は以下の通りである。
n(A) = 500, n(B) = 333, n(C) = 200
n(A∧B) = 166, n(B∧C) = 66, n(C∧A) = 100, n(A∧B∧C) = 33
従って、A, B, Cの和集合(2, 3, 5の少なくとも1つ以上で割り切れる1000以下の正の整数)の総数は以下の通り計算できる。
n(A∨B∨C) = n(A)+n(B)+n(C)-n(A∧B)-(B∧C)-n(C∧A)+n(A∧B∧C)
= 734
更にUの要素のうち2でも3でも5でも割り切れないものの集合をDとすると、DはA∨B∨CのUに関する補集合である為以下の式が成立する。
n(D) = n(U) – n(A∨B∨C) = 1000 – 734 = 266
ここで2, 3, 5を除く1000以下の素数は全て集合Dに属する。従って集合Dに属する素数が247個以下であることを示せば良い。
ここで5より大きい6つの素数7, 11, 13, 17, 19, 23について、それぞれの2乗はいずれも合成数かつ集合Dの要素である。更に上記6つの素数から異なる2数を選んで得られる積は全部で6C2 = 15個存在するが、これらもまた合成数かつ集合Dの要素である。
従って集合Dには少なくとも6+15=21個の合成数が属しており、これにより集合Dに属する素数は最大でも266-21=245個である。よって2, 3, 5を含めても1000以下の素数は高々248個であるので、1000以下の素数が250個以下である事が証明された。
コメント
上記解答の背景となっているのが、「エラトステネスの篩」と呼ばれる有名な素数探索アルゴリズムです。
これは2以上N以下の自然数(1は素数でない為最初から除かれている)について、2の倍数、3の倍数、5の倍数….と小さな素数から順番にその倍数(自身を除く)を除外してゆき、素数が√Nに達するまで繰り返すという非常に単純な方法です。
本問はN=1000(√N ≒ 31.6…)なので、2から31まで素数について順に「篩」にかけることで1000以下の素数を全て求める事は出来ますが、流石にそこまでしている時間はありません。そこで解答では2, 3, 5という3つの「篩」を利用する事で、素数となる可能性のある自然数の絞り込みを行う事としました。
当初はこの時点で素数の候補が250以下になると期待していたのですが、3つの「篩」では証明を完了するには不十分であり、結局素数2, 3, 5を含めて269個の自然数が残ってしまいました。
そこで今回は残る素数の候補から19個以上の合成数を直接除外する方針を取ることしました。但し19個を直接書き出そうとするとかなり大変である為、上記解答のように工夫が必要となります。
シンプルで興味深い題材で歯ごたえはありますが、さりとて全く手が付かない訳ではない絶妙な難易度設定となっています。
備考
2, 3, 5, 7と4つ「篩」を利用すれば、1000以下の素数が250個以下となる事を直接証明する事が出来ます(2, 3, 5, 7のいずれでも割り切れない1000以下の自然数は全部で228個)。4つの要素に対する和集合の取り扱い方を知っていれば、計算量こそ多いですが試験時間内に解答する事は十分に可能です。
数学日和 