東邦大学理学部情報科学科 2018 年度 卒業研究論文 コラッツの予想における 最大数と操作回数について 提出日 2019 年 1 月 30 日 ( 水 ) 指導教員白柳潔 提出者 金山和樹 1

1

東邦大学 理学部 情報科学科

2018 年度

卒業研究論文

コラッツの予想における

最大数と操作回数について

提出日 2019 年 1 月 30 日(水)

指導教員 白柳 潔

提出者 5515029 金山 和樹

2

2018 年度 東邦大学理学部情報科学科 卒業研究

コラッツの予想における最大数と操作回数について

学籍番号 5515029

氏名 金山 和樹

要旨

コラッツの予想とは、任意の0 でない自然数 n をとり、「n が偶数の場合 n を 2 で割り、 n が奇数の場合は n を 3 倍して 1 を加える」という操作を繰り返していくと、必ず有限回 の操作で1 に到達するであろうという予想である。別名をコラッツの問題、3n+1 問題とい う。1937 年にドイツの数学者コラッツが提示したこの問題は、未だ真かどうかは証明され ていない。よって数学の未解決問題とされている。 本研究では、コラッツの予想において初期値n が最終的に 1 に到達するまでの操作回数 や、初期値n が 1 に到達するまでの過程でどれだけ大きな数になるか、またその 2 つの関 係性等について、計算機実験を行い、考察した。

3

目次

第

1章 序論

1－1 序論

1－2 これまでの研究

1－3 本研究内容

第

2章 コラッツの予想の Maple プログラム

第

3章 操作回数、最大数の調査

3－1 n=1～1000

3－2 n=1001～10000

3－3 n=10001～30000

第

4章 今後の課題

4

第

1 章 序論

1－1 序論

コラッツの予想とは、任意の０でない自然数ｎ(本研究では初期値と呼ぶことにする)をと り、「ｎが偶数の場合ｎを２で割り、n が奇数の場合ｎに３をかけて１を足す」という操作 を繰り返していくと、必ず有限回で１に到達するであろうという予想である。 この予想は1937年にドイツの数学者コラッツが提示したことからコラッツの予想と呼ば れている。未だこの問題が真であるかどうかは証明されていないため、この問題は数学の 未解決問題とされている。コンピュータを用いた計算により、初期値ｎ＝3 × 260_までは反 例がないことが確認されている。[1] (例) ・初期値ｎ＝6 の場合 ｎ＝6 (偶数) →6÷2＝3 (奇数) →3×3＋1＝10 (偶数) →10÷2＝5 (奇数) →5×3＋1＝16 →16÷2＝8 →8÷2＝4 →4÷2＝2 →2÷2＝1 (成立) ・n＝11 の場合 11→34→17→52→26→13→40→20→10→5→16→8→4→2→1 (成立)

5

1－2 これまでの研究

コラッツの予想を解決する糸口を見つけるため、本研究室では過去4 年以上に渡りコラ ッツの予想をテーマとした研究が行われている。 例えば藤田[2]は、n が奇数の場合の操作である 3 倍の「3」をπや e(自然対数の底)に置 き換えたものについて計算機実験を行った。峯岸[3]は、本来 n が奇数の場合 3 倍するとこ ろを3,5,7,9 倍し、1 加えるところ 1,3,5,7,9,11 を加えた。その中で収束する値、ループす る値、発散する値に規則性を探した。

1－3 本研究内容

まず、初期値n が 1 に到達するまでに必要とする操作の回数と、1 に到達するまでの間 に出現する中で最も大きな数を、本研究ではそれぞれ操作回数、最大数と呼ぶことにする。 (例) ・n＝6 の場合 6→3→10→5→16→8→4→2→1 と変化していくため、操作回数8, 最大数 16。 ・n＝11 の場合 11→34→17→52→26→13→40→20→10→5→16→8→4→2→1 と変化していくため、操作回数14,最大数 52。 本研究では、これら操作回数や最大数に着目することでコラッツの予想の解決の糸口を 探す。また、初期値n、操作回数、最大数の値に何らかの法則や規則性がないか実験を行う。

6

第

2 章 コラッツの予想の Maple プログラム

本研究では、コラッツの予想のMaple プログラムとして以下を用いる。

7 ① の出力結果(例) ・n＝6 の場合 ・n＝11 の場合 ・n＝100 の場合 このように、n が 1 に到達するまでの過程、操作回数、最大数が出力される。

8

9 ② の出力結果(例)

・初期値n＝1～1000(スペースの都合上、記載するのは n＝10 まで)

このように、上からn＝1 の時の操作回数(0)、最大数(1)、n＝2 の時の操作回数(1)、最大数 (2)、n＝3 の時の操作回数(7)、最大数(16)…と出力される。

10 51 24 232 52 11 52 53 11 160 54 112 9232 55 112 9232 56 19 56 57 32 196 58 19 88 59 32 304 60 19 160 61 19 184 62 107 9232 63 107 9232 64 6 64 65 27 196 66 27 100 67 27 304 68 14 68 69 14 208 70 14 160 71 102 9232 72 22 72 73 115 9232 74 22 112 75 14 340 76 22 88 77 22 232 78 35 304 79 35 808 80 9 80 81 22 244 82 110 9232 83 110 9232 84 9 84 85 9 256 86 30 196 87 30 592 88 17 88 89 30 304 90 17 136 91 92 9232 92 17 160 93 17 280 94 105 9232 95 105 9232 96 12 96 97 118 9232 98 25 148 99 25 448 100 25 100

第

3 章 操作回数、最大数の調査

3－1 n=1～1000

前述したプログラムを用いて、まずは初期値n＝1～1000 における操作回数、最大数を調査 する。 調査結果をもとに、以下のような表を作成した。 また操作回数や最大数の、範囲内での最大値、最頻値も求め、考察を行う。 (スペースの都合上表は省略する。 赤色に塗った値に関しては後 述。) 初期値n 操作回数 最大数 1 0 1 2 1 2 3 7 16 4 2 4 5 5 16 6 8 16 7 16 52 8 3 8 9 19 52 10 6 16 11 14 52 12 9 16 13 9 40 14 17 52 15 17 160 16 4 16 17 12 52 18 20 52 19 20 88 20 7 20 21 7 64 22 15 52 23 15 160 24 10 24 25 23 88 26 10 40 27 111 9232 28 18 52 29 18 88 30 18 160 31 106 9232 32 5 32 33 26 100 34 13 52 35 13 160 36 21 52 37 21 112 38 21 88 39 34 304 40 8 40 41 109 9232 42 8 64 43 29 196 44 16 52 45 16 136 46 16 160 47 104 9232 48 11 48 49 24 148 50 24 88

11

実験結果

ｎ＝1～1000 操作回数 最大値：178(n=871) 最頻値：28 (計 30 回出現) 最大数 最大値：250504(n=703,937) 最頻値：9232 (計 354 回出現) n＝1～1000 の範囲では、上記のような結果となった。

考察

まず着目すべきは、9232 という最大数の出現頻度である。 9232 という最大数は、n＝27 で初めて出現した。周辺のほとんどの初期値 n が 2 桁の最大 数を記録している中、初めて出現した4 桁の最大数である(前ページの表参照)。 以下は、n＝27 が最大数 9232 を経て 1 に到達する過程である。 操作回数77 回で最大数 9232 が出現し、その後 34 回の操作を経て 1 に到達している。

12 9232 の n＝1～1000 における出現回数は 354 回で、平均すると 3 回に 1 回以上のペースで 出現したことになる。次いで出現回数の多い最大数4372 の出現回数は 28 回であるため、 最大数9232 の出現頻度はこの範囲内で群を抜いていると言える。 次ページのグラフは、n＝1～1000 における各最大数の出現回数を比較したものである。 このグラフからも、9232 という最大数の出現回数の多さが見て取れる。 (グラフの見やすさの都合上、縦軸(データの出現回数)の表記は 30 までとしている。)

14 操作回数の最頻値28 は出現回数 30 回であり、最大数ほどの偏った結果にはならなかった。 しかし、操作回数に関しては、隣り合うn や周辺の n において操作回数が一致するものが 非常に多く見られた。以下はその一例である。 123 や 30 といった操作回数が多く見られるが、特に n＝514～518、521、523、530、531 に関しては、9232 という最大数まで一致している。 以下は、操作回数123 と最大数 9232 の一致したこれら 9 つの初期値 n が、123 回の操作を 経て1 に到達するまでの過程である。9232 以降は、初期値 n の値に関わらず 34 回の操作 回数を経て1 に到達するため(p11 参照)、ここでは初期値 n が 89 回の操作の中で、どのよ うな過程を経て9232 に到達するかに着目する。 初期値n 操作回数 最大数 514 123 9232 515 123 9232 516 123 9232 517 123 9232 518 123 9232 519 61 3508 520 30 520 521 123 9232 522 30 784 523 123 9232 524 30 592 525 30 1576 526 79 9232 527 79 9232 528 30 528 529 30 1588 530 123 9232 531 123 9232

15 n＝514 操作回数89 回で最大数 9232 が出現。 n＝515 操作回数5 回で 580 が出現し、それ以降は n＝514 と同じ過程を辿って 9232 に到達してい る。

16 n＝516

操作回数18 回で 94 が出現し、それ以降の過程は n=514 と一致。

n＝517

17 n＝518

操作回数6 回で 292 が出現し、それ以降の過程は n=516 と一致。

n＝521

18 n＝523

操作回数12 回で 166 が出現し、それ以降の過程は n=516 と一致。

n＝530

19 n＝531

20

3－2 n=1001～10000

次に、範囲を拡大して同様に実験を行う。 操作回数、最大数の最大値と最頻値は1000 刻みで計測する。

実験結果

n＝1001～2000 操作回数 最大値：181(n=1161) 最頻値：34(40 回出現) 最大数 最大値：1276936(n=1819,1915) 最頻値：9232(323 回出現) n＝2001～3000 操作回数 最大値：216(n=2919) 最頻値：32(53 回出現) 最大数 最大値：1276936(n=2047,2155,2425,2553,2729,2873) 最頻値：9232(248 回出現) n＝3001～4000 操作回数 最大値：237(n=3711) 最頻値：43(64 回出現) 最大数 最大値：1276936(n=3071,3233,3638,3639,3830,3831) 最頻値：9232(160 回出現)

21 n＝4001～5000 操作回数 最大値：214(n=4379) 最頻値：46(76 回出現) 最大数 最大値：8153620(n=4591) 最頻値：9232(140 回出現) n＝5001～6000 操作回数 最大値：235(n=5567) 最頻値：54(98 回出現) 最大数 最大値：6810136(n=5673) 最頻値：9232(108 回出現) n＝6001～7000 操作回数 最大値：261(n=6171) 最頻値：62(98 回出現) 最大数 最大値：8153620(n=6121,6887) 最頻値：9232(92 回出現)

22 n＝7001～8000 操作回数 最大値：251(n=7963) 最頻値：52(95 回出現) 最大数 最大値：2316760(n=7935) 最頻値：9232(68 回出現) n＝8001～9000 操作回数 最大値：246(n=8959) 最頻値：65(101 回出現) 最大数 最大値：8153620(n=8161) 最頻値：9232(70 回出現) n＝9001～10000 操作回数 最大値：259(n=9257) 最頻値：60(127 回出現) 最大数 最大値：27114424(n=9663) 最頻値：250504(16 回出現)

23

考察

n=1001～10000 の範囲では上記のような結果となった。 まずは最大数の最頻値に着目する。 n＝1～1000 の範囲の最大数のうち多くを占めていた 9232 という値は、n が大きくなるに つれて出現回数は減少していく傾向にあったものの、n=8001～9000 の範囲まで最頻値であ り続けた。n=9001～10000 の範囲では最頻値は 9232 でなくなっているが、n=9233 以降 9232 は最大数になりえない事を考えると、自然な事だと考えられる。 結局、9232 は n=1～9232 の範囲で計 1579 回、約 17％の割合で出現した。 n＝9001～10000 の範囲の最大数の最頻値である 250504 は、n=703 において初めて出現し (p11 参照)、n=10000 までに計 142 回出現している。 n=1～10000 の範囲で 9232 に次いで出現回数の多い 39364 は、n=447 において初めて出現 し、n=10000 までに計 197 回出現している。 現時点では9232 と比較すると出現回数の少ないこれらの最大数が、n=9233 以降どの程度 の頻度で出現することになるのか着目しながら、n の範囲をさらに拡大し研究を進めていく。 次に操作回数の最頻値に着目する。 最大数における9232 のように、何か 1 つの値が出現し続けることはなかったが、最頻値の 出現回数そのものは少しずつ増加していった。 n=1～1000 における操作回数の最頻値は 28 で、出現回数は 30 回だが、n=9001～10000 においては60 という操作回数が 127 回出現している。 最大数の最大値はn=9663 における 27114424(この範囲において唯一の 8 桁)、操作回数の 最大値はn=6171 における 261 となった。

24

3－3 n=10001～30000

n の範囲をさらに 10000～30000 まで拡大し、実験を続ける。

実験結果

n＝10001～11000 操作回数 最大値：267(n=10971) 最頻値：55(140 回出現) 最大数 最大値：8153620(n=10331,10881) 最頻値：39364(17 回出現) n＝11001～12000 操作回数 最大値：249(n=11945) 最頻値：143(113 回出現) 最大数 最大値：8153620(n=11623) 最頻値：250504(17 回出現) n＝12001～13000 操作回数 最大値：262(n=12342,12343,12399,12583) 最頻値：63(156 回出現) 最大数 最大値：9198520(n=12447) 最頻値：39364(20 回出現)

25 n＝13001～14000 操作回数 最大値：275(n=13255) 最頻値：138(131 回出現) 最大数 最大値：9635920(n=13551) 最頻値：250504(21 回出現) n＝14001～15000 操作回数 最大値：270(n=14695) 最頻値：71(147 回出現) 最大数 最大値：27114424(n=14495) 最頻値：250504(18 回出現) n＝15001～16000 操作回数 最大値：270(n=15039) 最頻値：53(153 回出現) 最大数 最大値：9635920(n=15039) 最頻値：250504(16 回出現)

26 n＝16001～17000 操作回数 最大値：265(n=16457,16777) 最頻値：66(169 回出現) 最大数 最大値：9565936(n=16383) 最頻値：250504(16 回出現) n＝17001～18000 操作回数 最大値：278(n=17647,17673) 最頻値：141(160 回出現) 最大数 最大値：27114424(n=17179) 最頻値：250504(17 回出現) n＝18001～19000 操作回数 最大値：260(n=18514,18515,18599,18875) 最頻値：61(189 回出現) 最大数 最大値：9198520(n=18671) 最頻値：250504(14 回出現)

27 n＝19001～20000 操作回数 最大値：273(n=19593,19883) 最頻値：74(177 回出現) 最大数 最大値：27114424(n=19326,19327) 最頻値：250504(16 回出現) n＝20001～21000 操作回数 最大値：255(n=20830,20831,20895) 最頻値：87(146 回出現) 最大数 最大値：50143264(n=20895) 最頻値：250504(14 回出現) n＝21001～22000 操作回数 最大値：268(n=21942,21943) 最頻値：56(158 回出現) 最大数 最大値：27114424(n=21743) 最頻値：250504(22 回出現)

28 n＝22001～23000 操作回数 最大値：268(n=22043,22369,22559) 最頻値：69(161 回出現) 最大数 最大値：27114424(n=22905) 最頻値：250504(12 回出現) n＝23001～24000 操作回数 最大値：281(n=23529) 最頻値：144(191 回出現) 最大数 最大値：11003416(n=23529) 最頻値：250504(18 回出現) n＝24001～25000 操作回数 最大値：263(n=24684,24685,24686,24798,24799) 最頻値：157(142 回出現) 最大数 最大値：9635920(n=24091) 最頻値：250504(15 回出現)

29 n＝25001～26000 操作回数 最大値：263(n=25166,25167) 最頻値：64(154 回出現) 最大数 最大値：27114424(n=25769) 最頻値：39364(13 回出現) n＝26001～27000 操作回数 最大値：307(n=26623) 最頻値：139(185 回出現) 最大数 最大値：106358020(n=26623) 最頻値：250504(22 回出現) n＝27001～28000 操作回数 最大値：258(n=27135,27772,27773,27774,27807,27899) 最頻値：152(157 回出現) 最大数 最大値：17824048(n=27135) 最頻値：250504(12 回出現)

30 n＝28001～29000 操作回数 最大値：258(n=28313) 最頻値：59(180 回出現) 最大数 最大値：62710036(n=28287) 最頻値：250504(19 回出現) n＝29001～30000 操作回数 最大値：271(n=29257,29390,29391,29825) 最頻値：72(212 回出現) 最大数 最大値：14747488(n=29935) 最頻値：95956(15 回出現)

31

考察

n=10001～30000 においては、上記のような結果となった。 n=9001～10000 において最大数の最頻値であった 250504 は、n=10001～30000 の範囲に おいて多く出現したが、9232 ほどの出現回数には至らなかった。n=10001～30000 の範囲 では計315 回の出現で、これは n=10001～30000 の最大数のうち 1.5％と、9232 には到底 及ばない値であった。39364、95956 といった最大数に出現回数を抜かれている範囲も確認 できた。 操作回数の最頻値は、n=1～10000 の範囲においてその出現回数が増加傾向にあることが確 認されたが、n=10001～30000 の範囲においても同様の傾向が確認できた。 n=10001～11000 における最頻値 55 の出現回数は 140 回だが、n=29000～30000 において は最頻値72 が 212 回出現している。 ここから考えられる可能性は、 ① 初期値 n が大きくなると、それに比例し、操作回数の最頻値の出現回数は増加して いく傾向にある。 ② 最大数の最頻値の出現回数と、操作回数の最頻値の出現回数は反比例する傾向にあ る。 ③ n=1～30000 の範囲において操作回数の最頻値の出現回数が増加しているのは全く の偶然であり、より範囲を拡大すればそのような傾向は確認できなくなる。 である。

32 n=1～30000 の範囲での最大数の最大値は、初期値 n=26623 における 106358020 となった。 この範囲において唯一の9 桁の最大数である。一時的にここまで膨れ上がった初期値 n=26623 は、以下のような過程で 1 に到達している。 操作回数63 回で最大数 106358020 に到達し、その後 244 回の操作を経て 1 に到達してい る。 なお、この計307 回という操作回数は、n=1～30000 において最大である。

33

第

4 章 今後の課題

今後は初期値n の範囲を拡大しつつ、特に以下の点に着目して研究を進める必要があると 私は考える。 ① 今後最大数において、9232 と同程度の出現回数の値は出現するのか。また、なぜ 9232 という最大数があれほどの出現頻度だったのか。 ② なぜ初期値 n が近い値は操作回数も同一になりやすいのか。 ③ 操作回数の最頻値の出現回数は、今後も増え続けるのか。

謝辞

本研究を進めるにあたり、ご指導いただいた研究室指導教員の白柳教授、研究室の皆様に 感謝いたします。

【参考文献】

[1]「Computational verification of the 3x+1 conjecture」 (T.Oliveira e Silva) http://sweet.ua.pt/tos/3x_plus_1.html

[2]「collatz 予想の変形について」(東邦大学情報科学科 2011 年度卒業生 藤田 純平) [3]「コラッツ予想の変形について」(東邦大学情報科学科 2013 年度卒業生 峯岸 広大)