「今年最難」と噂の問題6へ
ネットでの評価をざっと見た感じでは、本年度の東大入試問題においては問題6が「一番難しかった」との評価のようである。問題1もそれなりに難しかったと思うのだが、あれが「ウォーミングアップ」程度だとすると、やはり東大に合格する学生たちはそれなりに頑張っているのだな、と思う。とはいえ、数学を満点で合格する人と、半分以下の出来で合格する人との差は結構あるだろう。
ちなみに、問題6の前半(1)はかなり簡単である。設問(1)は、ある意味で具体例の計算である。したがって、(1)のやり方を一般化すれば(2)も簡単に解けそうな気がする。ただ、一般化する時はそれなりの注意深さが必要で、面倒臭い例外処理というのもある(場合分?)から、油断は禁物である。
もし問題6が「最難」だとすると、今年の入試問題は「簡単な部類」ということになって、どの学生も高得点しないと厳しく、競争は激しいだろう。こういうときは、ケアレスミスみたいな減点が影響するので、真の意味での知性は入試で測れないような気がする。今回の入試に失敗した諸君も、白紙で手も足も出なかったというのであればダメだが、解き方はわかっていたが、ところどころで計算ミスしてしまった、という場合には、わざわざ東大まで通う必要はない。自信を持って別の大学で、存分にその知性の高さ(注意深さの高さではない)を発揮したらよいと思う。
問題の概略
「素数は因数分解できない正の整数である。ただし1だけは除く」というのが、素数の大雑把な定義である。問題6のテーマは、数学用語の定義や数学の概念をきちんと日頃から気にする姿勢をもっているかというものであろう。これは意外に大事であって、たとえば、解析の場合、代数関数、初等関数、多項式関数など様々な用語を使って関数を分類する。それぞれの意味がわかっていないと問題を正しく解くことができない(正直、私もこれらの関数の定義について奥底まで理解したとは到底言えないので、恥じるべきであるとは感じている)。
今回の問題文には、素数の定義がわざわざ書かれているので、それが大きなヒントになっている。 考察するのは多項式 \begin{equation} f(x)=x^3 + 10x^2 +20x \end{equation} なのであるが、実数$x$を整数$n$に「投影」した際に、その「影」$f(n)$が素数になる場合があるかどうか考えよ、という問題になっている。実数空間内で$f(x)$は明らかに因数分解できる形をすでに持ち合わせていて、 \begin{equation} f(x) = x (x^2 + 10x +20) \end{equation} である。したがって、$x\rightarrow n$としたときに$f(n)$が素数になれるとすれば、「2つの場合」しかあり得ない。それは$n=1$か、$n^2+10n+20=1$の場合である(後でみるが、実はあともう2つ、考えるべきケースがあるのだが、それを見落としてしまうかもしれないというのが、この問題の「落とし穴」である)。因数が1であれば、それは素数の例外規定に適用されるので、上の形式であっても許されるのである。
実際計算してみると、$n=1$は問題に適合するケースであり、答えの一つとなる。一方$n^2+10n+20=1$の場合は不適合となる($n$が整数にとれない)。ここで解答をやめると、おそらく「不合格」となるであろう。
「落とし穴」と私が呼ぶ、残り2つのケースは、$n<0, n^2+10n+20<0$の場合である。「素数」といったら正数しかないが、「整数」ならば負数もあり得る。2つの因子の両方が負であれば、その積は正となるので、依然として問題として考察すべきケースになりうるのである。したがって、残り2つのケースというのは、$n=-1$の場合と、$n^2+10n+20=-1$の場合である。しかし、注意すべきは相棒の因子も負にならないといけない、という条件である。
$n=-1$の場合、$n^2+10n+20 \rightarrow 11 >0$なので条件に合致しない。一方で、$n^2+10n+20=-1$の場合は、$(n+3)(n+7)=0$となるので$n=-3,-7$である。これは条件に合致する。したがって、$n=-3,-7$も答えに属する。
以上より、$n=-7, -3,1$の3つが解答の全体である。ここまでかなり簡単である。多分10分、うまくいけば5分程度で解ける。
複天一流の流儀で解く
しかし、我々は複天一流である。上のような解き方では予備校の解説とあまり違わないし、学ぶべきことが少なすぎて、勉強にならない(東大合格には近づくかもしれないが、仮に合格しても4月からの学業生活で困難を極めるであろう)。そこで、今回も計算機を使って、この問題に取り組んでみることにする。
正解は3つだけである。しかも絶対値にして10よりも小さな整数だけ。「人間のすばらしさは、必要最低限の思考で、最大の効果をあげることができることだ」と予備校の先生なら叫ぶかもしれない。しかし、現代はAIの時代である。将棋AIが人間を凌駕し始めたのは、人間では考えが及ばないような一手を、コンピュータがしらみつぶしに調べるようになったあたりからである。人間の観点からは「無駄な一手」に見えても、実は有効な一手になっている場合が存在し、それをAIは「見つける」ことができるのである。AIは「無駄」ということは考えないので、つまらないことでも、すばらしいことでも、平等にすべてを計算するので、馬鹿であり、かつ同時に利口なのである。
今回の設問(1)も、とにかく片っ端から整数を順番に入れて行って、問題の条件にあるものが出てくるまで探し続ければよいのである。一見間抜けに見えるこのアルゴリズムは、意外な点において重要さを見せてくれるかもしれない。とにかくやってみよう。
素数のデータベース
この問題を数値的に解くに当たり、まずは素数のデータベースをつくらねばならない。
ネット上には、これまでに誰かが計算してくれたデータが上がっているはずで、それを読み込めばよい。とはいえ、一応自分でもある程度の整数生成はやった方が勉強になるであろう。古典的に有名な素数探索アルゴリズムはエラトステネスの篩(ふるい)と呼ばれる。まずはこれを使って、素数を1万個程度、自分で探してみよう。
とはいえ、このアルゴリズムが正しく機能するかどうかのチェックには、古人が既に見つけてくれた素数のデータベースを利用することにする。権威の軍門に下るのか!、という叱責の声が聞こえてきそうであるが、間違えてしまってはどうしようもない。特にプログラミングというのはバグがつきものである(古代ローマ人は、Erarre humanum estと言った!)。この際、権威に媚びつつも、ただデータベースを読むだけに終わらず、プログラミングの技能向上のために自分自身でもコーディングしてみたいと思う。
どうやら、もっとも有名なデータベースはテネシー大学のThe PrimePagesのようである(他にもあるとは思うが、まず最初に見つかったのがこれなのである)。素数の専門家は「最大の素数」探しに躍起になっているので、2から始まる最初1万個程度の素数にはあまり興味がないようである。データベースをつかって、「初等的な素数」を探そうと思ったが、意外に苦労した。やっと見つけたのがこちらである。
ということで、まず目標とするのは、このデータベースにある「小さな素数、最初の1万個」を再現することである。データベースからダウンロードしたデータの一部を以下に掲載する。
The First 10,000 Primes (the 10,000th is 104,729) For more information on primes see https://t5k.org/ 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 1009 1013 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069 1087 1091 1093 1097 1103 1109 1117 1123 1129 1151 1153 1163 1171 1181 1187 1193 1201 1213 1217 1223 1229 1231 1237 1249 1259 1277 1279 1283 1289 1291 1297 1301 1303 1307 1319 1321 1327 1361 1367 1373 1381 1399 1409 1423 1427 1429 1433 1439 1447 1451 1453 1459 1471 1481 1483 1487 1489 1493 1499 1511 1523 1531 1543 1549 1553 1559 1567 1571 1579 1583 1597 1601 1607 1609 1613 1619 1621 1627 1637 1657 1663 1667 1669 1693 1697 1699 1709 1721 1723 1733 .... 103889 103903 103913 103919 103951 103963 103967 103969 103979 103981 103991 103993 103997 104003 104009 104021 104033 104047 104053 104059 104087 104089 104107 104113 104119 104123 104147 104149 104161 104173 104179 104183 104207 104231 104233 104239 104243 104281 104287 104297 104309 104311 104323 104327 104347 104369 104381 104383 104393 104399 104417 104459 104471 104473 104479 104491 104513 104527 104537 104543 104549 104551 104561 104579 104593 104597 104623 104639 104651 104659 104677 104681 104683 104693 104701 104707 104711 104717 104723 104729 end.
最初の1万個の素数を見つけるには、11万までの整数を調べなくてはならないということだ。とはいえ、偶数が考察から除外されることはすぐにわかる(エラトステネスの篩の一部でもある)。ということで、我々のプログラムは、11万の半分の5万5千個の整数を調べ、そこに素数がいくつ入っているのか確かめることになるであろう。
最初のコード
このデータベースはtxt形式のファイルとしてダウンロードできる。まずは、このデータベースを読み込む部分をプログラムで書いてみよう。整数の区切りは「空白」であるから、pythonのsplit()関数がもってこいであろう。
ファイルの最初4行は説明文なので、これを飛ばして次の行からデータとして読み込みを始め、最後の"end."が読み込まれたときに、プログラムを終了させよう。1行に10個のデータが書いてある構造を利用すると、次のような感じのプログラムで狙いの機能を実現することができた。
#!/opt/homebrew/bin/python3 while True: prime_data = input().split() if len(prime_data) == 10: for i in range(10): print(prime_data[i]+" ",end="") print() if len(prime_data) == 1 and prime_data[0] == "end.": break
実行はパイプを用いて、次のようにする。
python3 prime_read.py < 10000.txt
ちなみに、上のプログラムは"prime_read.py"とした。
しかしながら、この読み方だと、1行処理が終わった途端にメモリからデータ内容が破棄されてしまい、保持されない。 やはり、データは、パイプではなく、ファイルを開いて読み込み、プログラムがアクセスできるメモリに一度マウントすべきであろう。そのやり方は現在調査中である。