未解決問題で暇つぶし - 偽計数学妨害罪

こんにちは、108Hassiumです。

少し前、とある数学の未解決問題に関する論文がTwitterで話題になりました。

そう、

コラッツ予想です。

ja.wikipedia.org

2019年の12月に、解決に向けた大きな進展があった(完全解決ではないらしい)ようです。

えっ？

「ABC予想じゃないのか」って？

あれについては他の人によってもう説明し尽くされたと思うので、今更私が語れることは無いです。

というわけで、コラッツ予想の話をします。

コラッツ予想って何？

まず、好きな自然数を1つ思い浮かべてください。

その数がもし偶数だったら2で割って、奇数だったら3倍して1を足してください。

計算できましたか？

そしたら次はその数に対して同じ操作をします。偶数だったら2で割って、奇数だったら3倍して1を足してください。

これをずっと繰り返してください。

途中で1になりませんでしたか？

これがコラッツ予想です。

正確に言うと、こうです。

コラッツ予想：自然数に対して「偶数だったら2で割って、奇数だったら3倍して1を足す」という操作を繰り返すと、どんな自然数から始めても必ず1になるだろう。

例として7から計算を始めると、7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1となり、ちゃんと1になります。

先ほど言った通りコラッツ予想は未解決の超難問ですが、問題の内容自体は非常に単純です。

実際、私がこの問題に初めて触れたのは小学生のときで、教室の本棚に教員が置いたパズル本に載っていました。

この~~小学校レベルの~~問題について、数学者のポール・エルデシュは次のように述べました。

「数学はまだこの種の問題に対する用意ができていない」

かの有名なフェルマー予想の「それを書くにはこの余白は狭すぎる」みたいで格好いいですね。

数値実験

コラッツ予想の面白いところは、数値計算が簡単かつ楽しいことです。

数値がどう増減するかはほとんど予測不能なので、暇つぶしに最適です。

というわけで、30以下の数について計算してみましょう。

※偶数から始めても奇数になるまで2で割り続けるだけなので、初期値は奇数に限定します。

3,10,5,16,8,4,2,1

5,16,8,4,1

7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1

11,34,17,52,26,13,40,20,10,5,16,8,4,2,1

13,40,20,10,5,16,8,4,2,1

15,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1

17,52,26,13,40,20,10,5,16,8,4,2,1

19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1

21,64,32,16,8,4,2,1

23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1

25,76,38,19,58,29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1

27,82,41,124,62,31,94,47,142,71,214,107,322,161,484,242,121,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1

29,88,44,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1

御覧の通り、27だけ異様に長くなります。

1になるまでの計算回数は111回、途中で出現する数の最大値は9232です。

これを見て、ふとこんな疑問が浮かびました。

疑問1：コラッツ数列の長さってどんな感じで増えるの？

疑問2：コラッツ数列の最大値ってどんな感じで増えるの？

※コラッツ数列：「偶数だったら(略)」の操作を繰り返してできる数を順番に並べた列のこと

一つ一つ手計算して挙動を観察してもいいんですが、さっさと続きを読みたい人もいらっしゃると思うので文明の利器【PC】の力を借りたいと思います。

初期値が9999以下のコラッツ数列の長さを計算するコードです。

これを実行して出力されたデータをExcelでグラフ化すると、こうなります。

乱高下していますが、規則的な模様っぽいものも見えます。

増加の様子を見るため、次は最大値だけを見てみます。(ついでに範囲を24999まで広げます)

どうやら初期値の増加に対して長さの増加は非常に遅く、27のときの長さはかなり特殊だったようです。

ただし、これはあくまでも有限の範囲を見ただけなので、この後とんでもない値が出る可能性も十分あり得ます。

続いて、列中の最大値を見てみます。

なんかめちゃくちゃデカい値がありますね。

どのくらいデカいのかわからないので、初期値で割ってみます。

割ってもまだデカいですね。

どうやら初期値が9663のとき、初期値の約2806倍まで増加するようです。

ここまでの結果をまとめます。

疑問1→コラッツ数列の長さの増加はかなり緩やかである(ように見える)

疑問2→コラッツ数列の最大値はめちゃくちゃデカくなることがある

派生問題

コラッツ予想には、「3n+1予想」(または3n+1問題)という別名があります。

奇数だった時の「3倍して1を足す」にちなんだ名称ですが、この部分を変えることでコラッツ予想の亜種を考えることができます。

例えば、「偶数だったら2で割り、奇数だったら3倍して3を足す」という変形ルールを考えます。

このルールに従って計算すると、以下のような数列が得られます。

1,6,3

3,12,6,3

5,18,9,30,15,48,24,12,6,3

7,24,12,6,3

9,30,15,48,24,12,6,3

11,36,18,9,30,15,48,24,12,6,3

13,42,21,66,33,102,51,156,78,39,120,60,30,15,48,24,12,6,3

15,48,24,12,6,3

17,54,27,84,42,21,66,33,102,51,156,78,39,120,60,30,15,48,24,12,6,3

19,60,30,15,48,24,12,6,3,12,6,3

21,66,33,102,51,156,78,39,120,60,30,15,48,24,12,6,3

23,72,36,18,9,30,15,48,24,12,6,3,12,6,3

25,78,39,120,60,30,15,48,24,12,6,3

27,84,42,21,66,33,102,51,156,78,39,120,60,30,15,48,24,12,6,3

29,90,45,138,69,210,105,318,159,480,240,120,60,30,15,48,24,12,6,3

どの数も1ではなく3に収束するように見えます。

ちなみに3n+1のときの27のような変な挙動もちゃんと(?)あります。

53,162,81,246,123,372,186,93,282,141,426,213,642,321,966,483,1452,726,363,1092,546,273,822,411,1236,618,309,930,465,1398,699,2100,1050,525,1578,789,2370,1185,3558,1779,5340,2670,1335,4008,2004,1002,501,1506,753,2262,1131,3396,1698,849,2550,1275,3828,1914,957,2874,1437,4314,2157,6474,3237,9714,4857,14574,7287,21864,10932,5466,2733,8202,4101,12306,6153,18462,9231,27696,13848,6924,3462,1731,5196,2598,1299,3900,1950,975,2928,1464,732,366,183,552,276,138,69,210,105,318,159,480,240,120,60,30,15,48,24,12,6,3

3n+3ルールの場合の挙動は3n+1と比べてあまり差はありませんが、3n+5にすると大きな変化が生まれます。

1,8,4,2,1

5,20,10,5

19,62,31,98,49,152,76,38,19

23,74,37,116,58,29,92,46,23

187,566,283,854,427,1286,643,1934,967,2906,1453,4364,2182,1091,3278,1639,4922,2461,7388,3694,1847,5546,2773,8324,4162,2081,6248,3124,1562,781,2348,1174,587,1766,883,2654,1327,3986,1993,5984,2992,1496,748,374,187

347,1046,523,1574,787,2366,1183,3554,1777,5336,2668,1334,667,2006,1003,3014,1507,4526,2263,6794,3397,10196,5098,2549,7652,3826,1913,5744,2872,1436,718,359,1082,541,1628,814,407,1226,613,1844,922,461,1388,694,347

なんとループの種類が増えます。

というわけで、こんな疑問が湧きます。

疑問3：奇数のときのルールを変えたらループの種類はどう変わるの？

私は高校生の時、コラッツ予想の派生問題の数値実験にはまった時期がありました。

同級生たちがスマホゲーム(校則違反)に没頭している横で、合法的に電卓をポチポチしていました。

電卓で1項ずつ計算するしかなかった高校時代とは違い、今の私にはPCがあります。(実際、3n+5ルールでの187と347から始まるループは高校時代の自分には見つけられませんでした)

というわけで、自動計算によるループ探しを行います。

まず「1~999を初期値とする数列を500項計算して表示するプログラム」を書き、

目視でループの種類を判別し、採集します。

ちなみにこのプログラムを実行すると画面内に大量の数字がブワァァ～っと表示されるんですが、

いかにも「プログラミングしてます」って感じで格好いいですね。

…と思ったんですが、どう考えても効率悪すぎですね。

というわけで、改良しました。

これを実行すると、

3n+kルールで初期値が1~999のときに出現するループパターンが全部出力されます。

上の画像はk=5のときで、よく見ると先程の6種類のループと同じであることが分かると思います。

というわけで、これを使ってループを探しまくります。

3n+1
- 1,4,2,1
3n+3
- 6,3,12,6
3n+5
- 1,8,4,2,1
- 38,19,62,31,98,49,152,76,38
- 5,20,10,5
- 23,74,37,116,58,29,92,46,23
- 374,187,566,283,854,427,1286,643,1934,967,2906,1453,4364,2182,1091,3278,1639,4922,2461,7388,3694,1847,5546,2773,8324,4162,2081,6248,3124,1562,781,2348,1174,587,1766,883,2654,1327,3986,1993,5984,2992,1496,748,374
- 1334,667,2006,1003,3014,1507,4526,2263,6794,3397,10196,5098,2549,7652,3826,1913,5744,2872,1436,718,359,1082,541,1628,814,407,1226,613,1844,922,461,1388,694,347,1046,523,1574,787,2366,1183,3554,1777,5336,2668,1334
3n+7
- 10,5,22,11,40,20,10
- 7,28,14,7
3n+9
- 18,9,36,18
3n+11
- 1,14,7,32,16,8,4,2,1
- 26,13,50,25,86,43,140,70,35,116,58,29,98,49,158,79,248,124,62,31,104,52,26
- 11,44,22,11
3n+13
- 1,16,8,4,2,1
- 13,52,26,13
- 358,179,550,275,838,419,1270,635,1918,959,2890,1445,4348,2174,1087,3274,1637,4924,2462,1231,3706,1853,5572,2786,1393,4192,2096,1048,524,262,131,406,203,622,311,946,473,1432,716,358
- 844,422,211,646,323,982,491,1486,743,2242,1121,3376,1688,844
- 682,341,1036,518,259,790,395,1198,599,1810,905,2728,1364,682
- 454,227,694,347,1054,527,1594,797,2404,1202,601,1816,908,454
- 574,287,874,437,1324,662,331,1006,503,1522,761,2296,1148,574
- 502,251,766,383,1162,581,1756,878,439,1330,665,2008,1004,502
- 283,862,431,1306,653,1972,986,493,1492,746,373,1132,566,283
- 319,970,485,1468,734,367,1114,557,1684,842,421,1276,638,319
3n+15
- 114,57,186,93,294,147,456,228,114
- 3,24,12,6,3
- 30,15,60,30
- 138,69,222,111,348,174,87,276,138
- 1122,561,1698,849,2562,1281,3858,1929,5802,2901,8718,4359,13092,6546,3273,9834,4917,14766,7383,22164,11082,5541,16638,8319,24972,12486,6243,18744,9372,4686,2343,7044,3522,1761,5298,2649,7962,3981,11958,5979,17952,8976,4488,2244,1122
- 4002,2001,6018,3009,9042,4521,13578,6789,20382,10191,30588,15294,7647,22956,11478,5739,17232,8616,4308,2154,1077,3246,1623,4884,2442,1221,3678,1839,5532,2766,1383,4164,2082,1041,3138,1569,4722,2361,7098,3549,10662,5331,16008,8004,4002
3n+17
- 1,20,10,5,32,16,8,4,2,1
- 50,25,92,46,23,86,43,146,73,236,118,59,194,97,308,154,77,248,124,62,31,110,55,182,91,290,145,452,226,113,356,178,89,284,142,71,230,115,362,181,560,280,140,70,35,122,61,200,100,50
- 17,68,34,17
3n+19
- 112,56,28,14,7,40,20,10,5,34,17,70,35,124,62,31,112
- 19,76,38,19
3n+21
- 30,15,66,33,120,60,30
- 42,21,84,42
3n+23
- 110,55,188,94,47,164,82,41,146,73,242,121,386,193,602,301,926,463,1412,706,353,1082,541,1646,823,2492,1246,623,1892,946,473,1442,721,2186,1093,3302,1651,4976,2488,1244,622,311,956,478,239,740,370,185,578,289,890,445,1358,679,2060,1030,515,1568,784,392,196,98,49,170,85,278,139,440,220,110
- 5,38,19,80,40,20,10,5
- 7,44,22,11,56,28,14,7
- 23,92,46,23
3n+25
- 28,14,7,46,23,94,47,166,83,274,137,436,218,109,352,176,88,44,22,11,58,29,112,56,28
- 34,17,76,38,19,82,41,148,74,37,136,68,34
- 5,40,20,10,5
- 190,95,310,155,490,245,760,380,190
- 25,100,50,25
- 115,370,185,580,290,145,460,230,115
- 1870,935,2830,1415,4270,2135,6430,3215,9670,4835,14530,7265,21820,10910,5455,16390,8195,24610,12305,36940,18470,9235,27730,13865,41620,20810,10405,31240,15620,7810,3905,11740,5870,2935,8830,4415,13270,6635,19930,9965,29920,14960,7480,3740,1870
- 6670,3335,10030,5015,15070,7535,22630,11315,33970,16985,50980,25490,12745,38260,19130,9565,28720,14360,7180,3590,1795,5410,2705,8140,4070,2035,6130,3065,9220,4610,2305,6940,3470,1735,5230,2615,7870,3935,11830,5915,17770,8885,26680,13340,6670
3n+27
- 54,27,108,54
3n+29
- 1,32,16,8,4,2,1
- 44,22,11,62,31,122,61,212,106,53,188,94,47,170,85,284,142,71,242,121,392,196,98,49,176,88,44
- 29,116,58,29

まずわかることとして、どの場合でも「k,4k,2k,k」というループがあります。

まぁこれは実際に計算したらそうなるというだけで特に面白くもないです。

あと、ループが1種類しか見つからなかったのはk=1,3,9,27ですが、これらは全て3の冪乗です。

試しにk=81,243,729も計算してみましたが、やはりループは1種類しか見つかりませんでした。

疑問4：kが3の冪乗のときのループってk,4k,2k,kだけなの？

また、k=21のときのループをよく見てみると、

30,15,66,33,120,60,30=3×(10,5,22,11,40,20,10)
42,21,84,42=3×(14,7,28,14)

k=7のときのループを3倍しただけの列になっていることが分かります。

もしやと思ってk=63を計算してみると、

90,45,198,99,360,180,90=9×(10,5,22,11,40,20,10)
126,63,252,126=9×(14,7,28,14)

やはりk=7のときの9倍になっていました。

このことから、疑問4を以下のように拡張することができます。

疑問4(新)： $3n+3^mk$ ルールでのループって3n+kルールのときのやつを $3^m$ 倍したやつだけなの？

さて、ここまでの話は3n+1の1の部分を変えた場合の話でしたが、3の部分を変えるとどうなるのかも気になります。

というわけで、まずは5n+1ルールで数列を計算してみましょう。

1,6,3,16,8,4,2,1

3,16,8,4,2,1,6,3

5,26,13,66,33,166,83,416,208,104,52,26

7,36,18,9,46,23,116,58,29,146,73,366,183,916,458,229,1146,573,2866,1433,7166,3583,17916,8958,4479,22396,11198,5599,27996,13998,6999,34996,17498,8749,43746,21873,109366,54683,273416,136708,68354,34177,170886,85443,427216,213608,106804,53402,26701,133506,66753,333766,166883,834416,417208,208604,104302,52151,260756,130378,65189,325946,162973,814866,407433,2037166,1018583,5092916,2546458,1273229,6366146,3183073,15915366,7957683,39788416,19894208,9947104,4973552,2486776,1243388,621694,310847,1554236,777118,388559,1942796,971398,485699,2428496,1214248,607124,303562,151781,758906,379453,1897266,948633,4743166,2371583,11857916,5928958,2964479,14822396,7411198,3705599,18527996,9263998,4631999,23159996,11579998,5789999,28949996,14474998,7237499,36187496,18093748,9046874,4523437,22617186,11308593,56542966,28271483,141357416,70678708,35339354,17669677,88348386,44174193,220870966,110435483,552177416,276088708,138044354,69022177,345110886,172555443,862777216,431388608,215694304,107847152,53923576,26961788,13480894,6740447,33702236,16851118,8425559,42127796,21063898,10531949,52659746,26329873,131649366,65824683,329123416,164561708,82280854,41140427,205702136,102851068,51425534,25712767,128563836,64281918,32140959,160704796,80352398,40176199,200880996,100440498,50220249,251101246,125550623,627753116,313876558,156938279,784691396,392345698,196172849,980864246,490432123,2452160616,1226080308,613040154,306520077,1532600386,766300193,3831500966,1915750483,9578752416,4789376208,2394688104,1197344052,598672026,299336013,1496680066,748340033,3741700166,1870850083,9354250416...

何だか様子がおかしいです。

値がどんどん大きくなり、ループする気配がありません。

そういえば、3n+kルールのループ探しでは何の根拠もなく「どんな数から始めてもループに入る」と仮定していましたが、よく考えてみると当たり前のことではないようです。