未解決問題「コラッツ予想」と確認用プログラミング（ＢＡＳＩＣ）～２０１１センター試験・数学ⅡＢ

たまに忘れた頃にプログラミング記事を書こうとすると、いつも最初の入口で引っかかる。コード入力して実行する、環境を作れないのだ。

今回だと、（少し前の？）高校数学で使われてた言語、ＢＡＳＩＣ（ベーシック）を使う環境がなかなか見つからない。今さら古過ぎるということか？　１つ前のＰＣにはインストールしてたけど、今のＰＣに新たにインストールするのも面倒。

そこで最初に試したのが、ｉＯＳアプリの Learn BASIC Programming。スイスイ使えていいと思ってたら、「ある数を超えない最大の整数」を表す INT 関数が使えないようで（？）、エラー表示が出る。解決策も発見できず。

次に試したのが、パソコンのブラウザで使えるはずのウェブ上のサービス、Quite BASIC。これはなぜか、コードの１行目の「INPUT N」が読めないとか言って来た。

これだけでもう、大量の時間とエネルギーを使い果たしたので、とりあえず自分でプログラムを書いて実行するのは断念。与えられたコードの画像を利用するだけにしよう。

（☆追記：　翌朝、ＰＣに十進ＢＡＳＩＣをインストールして成功。この記事の末尾にプログラムの画像を挿入した。）

　　　　　☆　　　　　☆　　　　　☆

今回の記事のキッカケは、ネットで見かけた数学の懸賞金問題。１９３７年に数学者コラッツが提示した「コラッツ予想」（Collatz conjecture）に、日本のベンチャー企業から１億２０００万円の懸賞金がかけられたとのこと。下の写真は英語版ウィキペディアより。

それは７月の話だが、昨日は別の「ブレイクスルー賞」で、日本人２人がそれぞれ賞金３００万ドル（３億３０００万円）を獲得したニュースが流れてた。数学部門では、京都大学の望月拓郎教授（ＡＢＣ予想関連の望月氏とは別人）。

望月拓郎氏の研究内容は、少しだけ調べてみた所だと、意味不明な言葉・概念が並んでいて、残念ながら全く理解不能。

それに対して、コラッツ予想は小学３年生くらいでも分かるし、計算実験で楽しめるはず。

　「どんな正の整数でも、偶数なら２で割る、奇数なら３倍して１を足す、という操作を繰り返せば、必ず１に到達するだろう。」

　　　　　☆　　　　　☆　　　　　☆

実際に試してみると、意外なほど長いプロセスになることもある。例えば、７なら、７→２２→１１→３４→１７→５２→２６→１３→４０→２０→１０→５→１６→８→４→２→１。操作数は１６回。

英語版ウィキペディアによると、２０２０年頃の段階では、１０の２０乗を超える所までコンピューター計算で確認されてるらしい。

ちょっと似た話なら、何度か聞いた気がする。例えば、６年前の人気ドラマ『デート』第９話では、「どんな数字も各位の２乗を足すと１か８９になる」というコネタが挿入されてた。

直感的には、コラッツ予想は簡単に示せそうな気もするが、提示から８４年も経つのに未解決。ただ、ネットのあちこちに、センター試験に出題されたという情報があったので、すぐ問題ファイルを手に入れて解いてみた。

それが数学ⅡＢの選択問題で、プログラミング関連。私が見た範囲では、どのサイトも、プログラミングの部分を飛ばして最初の導入だけ紹介してたので、ここでは本題のプログラミングも扱う。

　　　　　☆　　　　　☆　　　　　☆

それでは、２０１１年のセンター試験問題を見てみよう。「日本の学校」ＨＰよりダウンロードさせて頂いた。

まず、簡単な（１）を解いてみる。

　６→３→１０→５→１６→８→４→２→１

　∴　Ｆ（６）＝（６から始めて１が得られるまでの操作回数）＝８　・・・アの答

　１１→３４→１７→５２→２６→１３→４０→２０→１０→５→１６→８→４→２→１

　∴　Ｆ（１１）＝（１１から始めて１が得られるまでの操作回数）＝１４　・・・イの答

　　　　　☆　　　　　☆　　　　　☆

この先は、環境作りの失敗で時間も無くなったので、穴埋めや選択肢を飛ばして、直ちに正解のプログラムを見てみよう。

　　　　　☆　　　　　☆　　　　　☆

まず、最初の１００番の行で、調べる自然数Ｎをインプット。問題（１）なら、６とか１１。

次に１１０行で、Ｉという変数を用意して、最初はＮの値をそのまま代入。操作が進むと、Ｉは変化していく。

一方、１２０行で、Ｃという変数（回数のカウント用）も用意して、最初は０を代入。１回の操作ごとに、＋１で回数を増やしていく。

１３０行からが実質的な操作。まず、Ｉ＝１なら、直ちに２１０行まで飛んで、Ｆ（１）＝１と表示。

１４０行と１５０行は、もし「Ｉが偶数」なら２で割ったものをＩとする、という条件を、「ＩＮＴ（Ｉ／２）×２＝Ｉ」と書いてる。

これは、Ｉが奇数だと成り立たない。例えばＩ＝３の時、ＩＮＴ（３／２）×２＝１×２＝２になって、条件を満たさず、１８０行に進むことになる。

１６０行は、１回の操作ごとに、回数Ｃに１を加える操作。１７０行は、「もし」という条件の終了。

１８０行は、１でもないし偶数でもない奇数Ｉに対して、３倍して１を加える操作。

１９０行で、回数１を加えた後、２００行で１３０行までバックする。Ｉ＝１になったら終了。

２１０行で、結果の表示。Ｆ（Ｎ）＝Ｃ。ＮとＣはここまでに登場した変数の値で、他は単なるアルファベットの文字とカッコの記号。

２２０行で、すべて終了。

　　　　　☆　　　　　☆　　　　　☆

さらに、ある自然数Ｍ以下の自然数Ｎのうち、Ｆ（Ｎ）≦１０となるすべてのＮについて、Ｆ（Ｎ）の値を出力するプログラムへと書き換える。

最初と最後の辺りだけ少し変更して（下の青枠）、次のコードが正解。１０１行のFOR TO文で、Ｎ＝１からＭまでの実行を宣言。２１１行のNEXT Nで、次の数Ｎの操作へと進んで行く。PRINT（表示）は、Ｃ≦１０の時だけ（２１０行）。

これによって、次の８行が表示される（はず）。改行は省略。

　F(1)=0　F(2)=1　F(3)=7　F(4)=2　F(5)=5　F(6)=8　F(8)=3　F(10)=6

よって、２１０行の PRINT文が実行される回数は８　・・・サの答

後で実際にプログラミングしてみる予定。とりあえず今日のところはこの辺で。。☆彡

Ｐ．Ｓ．　翌朝、２つとも自分で書いて、実行。この問題の説明通りに表示された。

　　　　　　（計　２５１２字）