東邦大学理学部情報科学科 2011 年度 卒業研究論文 Collatz 予想の変形について 提出日 2012 年 1 月 30 日 指導教員白柳潔 提出者 藤田純平

Transcription

1 東邦大学理学部情報科学科 2011 年度 卒業研究論文 Collatz 予想の変形について 提出日 2012 年 1 月 30 日 指導教員白柳潔 提出者 藤田純平

2 2011 年度東邦大学理学部情報科学科卒業研究 Collatz 予想の変形について 学生番号 氏名藤田純平 要旨 Collatz 予想とは 任意の自然数について それが偶数のときは半分にし 奇数のときは3 倍して1を加えるという操作を次々に繰り返していくと 必ず有限回で1に到達するであろうという予想である この予想は 80 年余り経った今でもなお証明されておらず 未解決のままである 本研究では Collatz 予想の変形として 上記 3 倍のところをπ 倍に置き換え 結果を浮動小数点近似 ( 切り下げ 四捨五入 切り上げ ) したものを考え 計算機実験を行った その結果 生成される数の列において 周期サイクルに関する規則性を発見し いくつかの予想を立てることができた さらに πの代わりに 自然対数の底である e に置き換えたものについても計算機実験を行った 白柳研究室

3 目次 第 1 章序論 第 2 章 Collatz 予想の変形についての実験 2.1 実験目的 2.2 実験方法 2.3 フローチャート 2.4 Maple14 によるプログラムと解説 2.5 実験結果 round πについて ceil πについて floor πについて round e について floor e について第 3 章考察 参考文献 別紙

4 第 1 章序論 Collatz 予想と言われてもわかりづらいので例を用いて説明すると次のようになる x = 5 のとき x = 29 のとき x = 31 のとき x = 5 のときは 4 回目で 1 に辿り着く x = 29 のときは 11 回目で 1 に辿り着く x = 31 のときは 67 回目で 1 に辿り着く このように代入する x の値によって 1 に辿り着くまでに要する回数は様々であるが すべての自然数で1に辿り着くであろうというのがこの予想である 2003 年 9 月までにこの予想が以下の整数に対して成り立つことおよび自明でないサイクルの長さは尐なくとも であることを導出した また 同年に a1 = からスタートするとき サイクルの最大は 回 まで到達できると見つけられた この予想はドイツの数学者 Lothar Otto Collatz 教授 ( ) によって提起 された (1932 年 7 月 1 日の教授のノートにて ) また この予想の類似として を でおきかえると 任意の列が {1,2} {5,14,7,20,10} {17,50,25,74,37,110,55,164,82,41,122,61,182,91,272,136,68,34} のどれかのサイクルで終わることがあるとした この予想は まで正しい 本研究ではこの予想の変形 ( について ) のサイクルについて着目し 様々

5 な数を用いて規則性を見出して Collatz 予想の解決の糸口を探るものとする この予想を一般化すると = このような形になる この列からは次の3 通りのいずれかになる (1) 必ず 1 に辿り着く (2) 途中からサイクル列に入る (3) 無限に発散してゆくここでいうサイクルとは 列の繰り返しのことである 具体例は挙げると x = 9,p = 2,q = 3,r = -1 の場合 となる このように 列の途中からでも { } が無限に続いていくを サイクルという 1 1 に辿り着く場合 1 に辿り着く列はどの列に対しても無限個存在している 具体的な例は序 論で述べたような列が挙げられる 2 途中からサイクル列に入る場合 サイクルに辿り着く列はどの列に対してもあるとは限らない しかし サイクルを確認できた列に対しては複数のサイクル列があると推測できるが その種類が有限種類のサイクル列かは不明である 但し {1 1} のサイクルは除くとする 3 発散する場合 発散する場合は実験結果や他の論文からの推測でしかないが p が 3 から遠ざ かるにつれて発散する列が多くなると推測される

6 本研究では 一般化においてのqに着目して 3に近いπや自然対数の底の e に置き換えることによって Collatz 予想に近い周期サイクルや軌跡について探求する 小数点以下の値を切り上げ 切り下げ 四捨五入の 3 パターンすることで小数点以下の値によっての変化も見る ただし ここでは Collatz 予想に近いものを調べるため p の値を2 r の値を1で統一する

7 第 2 章 Collatz 予想の変形についての実験 2.1 実験目的 Collatz 予想を変形させ 周期サイクルなどの規則性を発見する 2.2 実験方法 数式処理システム Maple 14 を用いて Collatz 予想の変形について観察する 2.3 フローチャート 数を決定 1 かどうか Yes No qx+1 をする No 偶数判定 Yes q/2 をする No サイクル判定 Yes 終了

8 2.4 Maple14 によるプログラムと解説 coll:= proc(n, m) local i:= n; local l := []; l:=[op(l),0]; while i 1 do if n=1 then print(1); else if type(i, even) then i := i/(2); print(i); elif type(i, odd) then i := ceil(evalf( Pi*i+1, m)); print(i); end if; end if; if member(i,l) = true then print(yes) ; i:= 1; end if; l := [op(l), i]; od; end proc;

9 入力 : (n,m) i := n l を箱にして 0 を一番目の要素とする 1. i が 1 でない限り以下の操作を繰り返す 2. n が 1 の場合 1を出力する 3. i が偶数の場合 i を半分にしてそれを新たな i としてその i を出力する 4. i が奇数の場合 i にπをかけて1を加える この時有効桁数はm 桁で出た値を超える最小の整数を新たな i としてその i を出力する 5. l の要素を参照してその中に i があった場合 i を 1 とする 6. l の要素に i を加える本実験ではプログラム内で色を変えた場所 ceil( この数を超える最小の整数 ) を floor( この数を超えない最大の整数 ) や round( 尐数第一位を四捨五入する ) に変える Pi(πのこと ) を自然対数の底 e に変える

10 2.5 実験結果 round πについて 最終的に1になる のサイクルになる のサイクルになる のサイクルになる のサイクルになる のサイクルになる を含むサイクルになる を含むサイクルになる から始まるサイクルになる 7~9 の場合においては サイクルの数が膨大なため付録に参照する round π についてはサイクルが多々を発見することができた 数が大きくなるにつれて違ったサイクルが発見でき サイクルの長さも膨大に なっていった

11 2.5.2 ceil πについて 最終的に1になるサイクル のサイクルになる のサイクルになる のサイクルになる を含むサイクルになる round ほどサイクルは見つからなかったがサイクルの種類に偏りができた そして ここでも を含むサイクルを見つけることができた floor πについて 最終的に1になるサイクル のサイクルになる のサイクルになる のサイクルになる 大きなループ列は見つけることができなかったが 1 になるサイクルを他の π の 計算に比べて多く見つけることができた しかし 大きなサイクルを見つける ことができなかった

12 2.5.4 round e について 最終的に1になるサイクル のサイクルになるサイクルが一つしか見つけることができなかった この値についてはただ一つしかサイクルがないかの検証が必要 また このサイクルについて数学的意味を考える必要がある floor e について 最終的に1になるサイクル のサイクルになる のサイクルになる πに比べてあまりサイクルは見つけられなかったが1になるサイクルは多く見つけることができた また 長いサイクルも発見することができなかった

13 第 3 章考察 本実験では一つ当たりの計算時間をかなり要したためあまり多くの結果を得ることができなかった しかし サイクルをいくつか発見することができたのは大きい round と ceilπにおいて同じ を含むサイクルを見つけることができた これにより この数字について数学的意味があると推察される ただ一つしかサイクルがでなかった round e についてサイクルの数学的意味などを検証する必要がある また 本実験では発散するものが出なかったが 他の論文などから3から遠ざかるほど発散するものが多くなると推測される round においては多くのサイクルが見つかったが 数が大きくなるとほかのサイクル列が見つかるかは不明で それぞれのサイクル列はもう尐し多くの数を調べなければサイクル列の個数はわからなさそうだ だが 2 種類の数値 ( 切り下げと四捨五入 ) において 大きなサイクルを見つけることができたので あまり大きなサイクル列を持たないものに関しては今後大きなサイクル列を持つ可能性があると推測される 本実験では5 種類の数においてしか調べることができなかった また 数も 50までとかなり狭い範囲でしか調べることができなかった 今後の課題としては種類を増やしたり 範囲をもっと大きなものにすることで新たなサイクルの発見をすることが挙げられる また その場合はパソコンを並列処理させて時間を短縮させる必要があると感じた

14 参考文献 Collatz 問題の一般化について大平麗子, 山下倫範数論 < 未解決問題 >の事典リチャード K ガイ著金光滋訳

15 付録 を含むサイクルになるもの , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,

16 2590, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,~ 中略 ~ , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,

17 , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,

18 , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,

19 , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , を含むサイクルになる 645,2027,6369,20010,10005,31433,98751,310236,155118,77559,243660,121830,60915,191371, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,

20 3340, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,6

21 , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,~ 中略 ~ , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,853341

22 06680, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,980256,490128,245064,122532,61266,30633,96237,302338,151169,474912, ,118728,59364,29682,14841,46625,146478,73239,230088,115044,57522,28761,90356,45178,2 2589,70966,35483,111474,55737,175104,87552,43776,21888,10944,5472,2736,1368,684,342,171,5 38,269,846,423,1330,665,2090,1045,3284,1642,821,2580,1290, から始まるサイクルになる 47,149,469,1474,737,2316,1158,579,1820,910,455,1430,715,2247,7060,3530,1765,5546,2773,8713, 27374,13687,43000,21500,10750,5375,16887,53053,166672,83336,41668,20834,10417,32727, ,51408,25704,12852,6426,3213,10095,31715,99637,313020,156510,78255,245846,122923, , ,606603, , , , , , , , , ,923261, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,

23 90, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,

24 , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,762060,381030,190515,598522,299261,940157, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,

25 50, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,13

26 , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ~ 中略 ~ , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,

27 , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,

28 , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , ,

29 , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 93555, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 64768, 32384, 16192, 8096, 4048, 2024, 1012, 506, 253, 796, 398, 199, 626, 313, 984, 492, 246, 123, 387, 1217, 3824, 1912, 956, 478, 239, 752, 376, 188, 94, 47