コマネチ大学 #33
たけしのコマネチ大学数学科#33 2007/01/18 深夜OA
今回のテーマは、
「素数」
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
素数とは、１とその数以外では割り切れない数字のことです。
世界的な素数研究プロジェクトもあり、その調査によると、
2006年9月の時点で発見された最大の素数は、980万8358桁。
全く想像もつきません。（戸部アナ）
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
>> ブログランキング始めてみました。暖かな応援を！！<<
>> バナークリック=>
よろしくお願いします <<
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
ここで竹内先生から、素数プロジェクトGIMPSによる最大の素数(980万8358桁)
についての解説があった。 その素数をプリントすると、
びっしり書かれたA4用紙が1400枚以上必要であると言う。
たけしの質問は、「メルセンヌ数かなんかで捜していくのか」というもの。
先生曰く、「その方法もあるのだけれども...」
たけし、「でもそれだと割れちゃう数字（素数でない数）も出てきちゃうんじゃない..」
先生、「そうですね、メルセンヌ数は素数でないものもある。」
数学談義が止まらないようなので、コマ大が割って止める。
竹内先生曰く
今こうしている間にも、世界中のコンピュータで計算をしている。
そして、懸賞金があるという。
1000万桁での素数を見つけると、約1000万円の懸賞金が出るらしい。（一同驚）
今や、素数はお尋ね者であり主役だという。
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
Q: 問題
両端にそれぞれ"１"と書かれたテープがあります。
数と数の間に両側の数の和を書き加えていく作業を一万回行うと、
一万本目のテープの上に"101"は何回出てくるでしょう。
上図（クリックすると大きくなります）参照してください。
まず、上のテープの数字はそのまま下のテープに書き写して、
その数字間に両端の数を足した数字を書き込む。
これをひたすら1万回していくのである。
はじめは何をするべきかがピンと来なかったのだが、タカさんの解説でようやく
理解できた。（タカさん、やるね）
一度書かれた数字は最後まで残っていくことも重要な要素だ。
ポイント：
１：早くパターンを見つけること。それが分れば後は早い。
２：素数に注目すること。"101"は素数ですよ。
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
Ａ： 各チームの解答
◆コマネチ大学生の解答
実際にテープを使ってやってみることに。
（ちょっと考えると、10枚辺りでテープの長さは、最初の1000倍以上になるので
これは出来るのか！とハラハラしながら見守った。）
2時間経過した11枚目のところで最初の"101"を発見！
さらに10時間作業は続けられ、14枚目でTimeUp！
ちなみにこのペースだと、2000時間以上、83日かかるそうだ。
苦労して出た答えは、14枚目で40個
◆マス北野の解答
左右対称なので、まず半分で考えていった。するとある法則に気が付く。
次々に出てくる数字を素数について数えてみると、
２は １コ 素数だけは、１を引いた個数が出てくる。
３は ２コ つまり、その素数の足し算の組合せの数でもある。
５は ４コ 例） 13は、 1+12であり、2+11でもあり、・・・・12+1 組合せは12コ
７は ６コ もうそれ以上の組合せは無いので、テープが何枚増えようが同じ。
11は10コ 101は素数だから、１を引いて、答えは"100"
13は12コ ここで、先生は1万回はヒッカケだとばらす。（コマ大、無念！）
◆東大生は時間切れで、まともな解答は得られなかった。
正解は、１００コ！
たけしさんのみ正解である。
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
先生の解説
コンピュータ（PC）で計算しても14段ですら結構時間がかかる。
先生が100段まで計算させて結果をスタジオで披露しようとしたが、
昨日からの計算がまだ終わっていなかった。(その時点でまだ計算しているかも)
それほど膨大な計算という事で、コマ大の頑張りを褒めていた。
◆簡単に解く方法
素数ｎは、 n = a + b で表わすことが出来る。（２以上）
この場合、a と b は"互いに素"である。
*互いに素とは、2つの正の整数の最大公約数が"1"しかない状態、
素数の場合は、上式の a と b の最大公約数が１しか存在しない。
n が素数でない場合は、上式は
n = a + b = c x q + d x q = ( c + d ) x q ( q は1以外の最大公約数) となり、
a と b は1以外の最大公約数qを持っていて、"互いに素"ではなくなる。
つまり、今回の問題では、
素数"101"の互いに素の組合せが、いくつあるかを数えればよい。
1 + 100
2 + 99
3 + 98 => という組合せがあるので、101 - 1 = 100 //
: 答えは １００コ
99 + 2 この方法で解いたマス北野は素晴らしい、と先生。
100 + 1
◆ユーグリッドの互除法を用いる解き方
ユーグリッドの互除法を説明。
これは、割り算で最大公約数を求める方法である。
（（コマネチ大学 #32 正月SP の問８
で出てきた方法。解答編ブログに説明あり））
例えば、１８と８の最大公約数を求める場合：
対象の数字同士を割り算する。
１８÷８＝２．．．２（余り）
割った数(８)を余り(２)で割る。
８÷２＝４．．．０（余り）
この割り切れたときの割った数 ２ が最大公約数
今回は、変形したユーグリッド互除法を用いる。
それは、引き算を使った互除法である。
１８と８の場合は、まず一番下に （ 18 , 8 ）と書いて、
大きい数（18）から小さい数（8）を引く。 18 - 8 = 10
( 2 , 2 ) Λ 次は上に出てきた答えの"10"と、さっきの小さい数(8)を書く。
( 2 , 4 ) ｜ そして今度は１０と８の場合になるので、
( 2 , 6 ) ｜ 大きい数（10）から小さい数（8）を引く。 10 - 8 = 2
( 2 , 8 ) ｜ 次は上に出てきた答えの"2"と、さっきの小さい数(8)を書く。
( 10, 8 ) ｜ ・・・・
( 18, 8 ) ｜ ・・・・
と続けて、両方の数字が同じになったら、その数が最大公約数。
（実は割り算と同じ事をしているに過ぎないが...）
３と７の場合は、まず一番下に （ 3 , 7 ）と書いて、
大きい数（7）から小さい数（3）を引く。 7 - 3 = 4
( 1 , 1 ) Λ 次は上に出てきた答えの"4"と、さっきの小さい数(3)を書く。
( 2 , 1 ) ｜ そして今度は４と３の場合になるので、
( 3 , 1 ) ｜ 大きい数（4）から小さい数（３）を引く。 4 - 3 = 1
( 3 , 4 ) ｜ 次は上に出てきた答えの"1"と、さっきの小さい数(3)を書く。
( 3, 7 ) ｜ ・・・・
と続けると、最後は(１，１)になって、最大公約数は１であるため、
３と７は"互いに素"である。//
◆ここで応用へのヒント
今は、下から計算していき最大公約数を求めたが、
（ 1 , 1 ） の組合せを一番上に書き、逆に下に足していくと、出てくる組合せは
どこでも互いに素であることにもなる。
３と７の組合せの場合も、上から
( 1 , 1 ) 、 ( 2 , 1 ) 、 ( 3 , 1 )、 ( 3 , 4 )、 ( 3, 7 )、と
すべて、互いに素の組合せである。これを踏まえて今回の問題へ応用をする
◆今回の問題への応用
問題でやっていることは、
引き算のユーグリッド互除法を上からやっているのと同じことである。
つまり、 ( 1 , 1 ) でスタートして、どんどん足していくと、
それは隣り合う数字が"互いに素"である数をどんどん作っている
"互いに素マシン"ということになる。
上図（クリックすると大きくなります）の（図１）では、
5枚目のテープには５が4コ出てくる。
（これは、"１０１"であれば、100コ出てくることになる。かなり下のほうで）
じゃあ、この"５"はどうやって作られてきたかと辿っていくと、
上図（図2）のように
赤の５は、 ( 1 , 4 ) 、 ( 1 , 3 ) 、 ( 1 , 2 )、 ( 1 , 1 )
青の５は、 ( 3 , 2 ) 、 ( 2 , 1 ) 、 ( 1 , 1 )
この並びは、さっきの引き算ユーグリッド互除法そのものである。
つまり"５"になる直前の組合せを数えることで、"５"がいくつ出てくるかがわかる
( 1 , 4 ) 、 ( 2 , 3 ) 、 ( 3 , 2 )、 ( 4 , 1 ) の４コですね。
また、この"互いに素マシン"は、
「ユーグリッドの互除法の一意性」が成り立っており、
重複の無い"互いに素"の数の組を作っている。
どこかに ( 1 , 4 )の組が出てきたら、他のところに ( 1 , 4 )の組は無いということ。
だから、"互いに素"の組合せを数えれば問題は解けた。
つまり、"101"の場合は、
( 1 , 100 ) 、 ( 2 , 99 ) 、 ( 3 , 98 ) ・・・・・ ( 100 , 1 ) で 答え：100コです。
たけしさんは、考え方も同じで、素晴らしい解答でした。
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
◆応用解説２（素数の魅力）
レオンハルト・オイラーの論文
「無限級数に関するいくつかの見解」（1736年）の定理８には
上図（クリックすると大きくなります）の式がある。
上の式は素数で構成されている掛け算の式
下の式は自然数で構成されている足し算の式
何が言いたいかというと、
自然数に対する足し算は、素数に対する掛け算とイコールである、
つまり、
自然数は素数から出来ていると言っても過言ではないということである。
さらに、「数学は素数から出来ている」という先生は、
「素数は基礎的であり、美しいし、広大である！」と語る。
「素数、それは素的な数学」と締めくくったところが洒落ていた。
◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
今週のフィールド賞：当然のマス北野
講師：竹内薫
（科学作家 東大理学部物理学科卒）
解答者：
マス北野
木村美紀（東京大学薬学部3年）
松江由紀子（東京大学農学部3年）
コマネチ大学生
2007/01/18OA