今回もかけ声はαριθμοι κυβερυουν συμπανのコマネチ大学数学科。顧問は中村先生。
今回はプログラマーにとってもうれしい問題。
問題:1から1000までの番号とスイッチがついた電球があります。まず、1の倍数の電球のスイッチを押し、次に2の倍数のスイッチを押し....これを1000回行った後、点灯している電球の数はいくつあるでしょう?ただし、最初の状態では電球は消灯状態です。
この問題は「1から1000までの数において、1とそれ自身を含む因数の数が奇数のものはいくつあるでしょう?」という問題に還元される。
エレガントな解答に行く前に、コマ大生たちの足跡をjavascriptでたぐってみよう。
どんな数が現れただろう?そう。平方数なのである。よって問題は「1から1000までの間に、平方数はいくつあるか?」に還元されて、あとは1000の平方根を取って少数以下を切り捨てれば、答えの31が出るという仕掛け。マス北野と女子東大生チーム、見事正解。
ところで、第12講では、「約数の和が奇数になるのは、常に平方数である」ということをきちんと証明していない(直感的な説明は中村先生がしていたが)。なぜそうなのかは、↑の「素数入門」にも載っている以下の定理を使うことが出来る。
pp.195
正整数nの標準素因数分解を、
n = paqbrc...
とすると、
[因数の数]σ0(n) = (a + 1)(b + 1)(c + 1)...
σ0(n) が奇数ということは、 (a + 1)(b + 1)(c + 1)...の全ての項が奇数ということなので、a,b,c....は全て偶数。よってpaqbrc...は平方数となる。
そんなわけで、因数の不思議についてもっと知りたい人は是非本書を入手のこと。以前も紹介したが、手頃な問題ということで、ここで改めて紹介する次第。
Dan the Auditor
nの約数kのそれぞれについて、n/k（これもnの約数）とペアを組ませます。もし、どの約数も自分以外の数とペアになっているならば、約数の個数はペアの数の2倍（つまり偶数）のはずですが、今はそうではありません。よって、ある約数kは自分自身とペアになっている（妙な表現ですが…）はずで、n/k=k、つまりn=k^2でnは平方数となります。