皆さん、こんにちは。
もうすぐゴールデンウィークですね。コロナも一段落して羽を伸ばそうという方も多いかと思います。一方で、相変わらず家でのんびりしたいという人もいるでしょう。
今回は、そんな連休中に読めるような軽めの記事を上げます。小学生でも内容を簡単に理解できる未解決問題「コラッツ予想」についてです。
1. コラッツ予想の概要
まず、好きな数字（自然数）を準備して、それに対して、
1. その数字が偶数なら、その数字を半分にする。
2. その数字が奇数なら、その数字を3倍して1足す。
というルールで次の数字を作り、以下同じルールを繰り返して次々に数字を作っていくことを考えてみましょう。
例えば、最初の数字が3だとします。
3は奇数なので、次の数字は3×3+1 =10になります。すると、10は偶数なので、次の数字は半分にした5になります。5は奇数なので次の数字は3×5+1=16, 16は偶数なので次は半分の8, 8は偶数なので次は半分の4, 4は偶数なので次は半分の2、2は偶数なので次は半分の1, 1は奇数なので次は3×1+1=4、・・・・となり、
3→10→5→16→8→4→2→1→4→2→1→・・・・
最終的には4→2→1のループに突入することが分かります。ループする現象は今後議論しにくいので、特に「最終的に1になる」という結論が重要です（つまりループに入るところで打ち切ってしまいます）。
他の数字でもやってみましょう。
最初が6の場合は、
6→3→・・・となって上の3の場合に帰着します。
最初が7の場合は、
7→22→11→34→17→52→26→13→40→20→10→・・・となって結局3の場合と同じルートをたどります。
最初が9の場合は、
9→28→14→7→・・・・となって7の場合に帰着します。
最初が15の場合は、
15→46→23→70→35→106→53→160→80→40→・・・となって結局7の場合と同じルートをたどります。
少なくとも上記の例で、1~17については、最終的に1になることが分かりましたね。
この話を広げて、
「最初の数がどんな自然数でも、上のルールの操作で最終的に1なる」
という仮説こそが、コラッツ予想です。
この仮説は本当なのか？こんな簡単なルールなのにも関わらず、実はタイトルにある通りまだ証明されていません。
現在コンピュータでの計算で、初期値が2の68乗（21桁の整数）までの整数についてはコラッツ予想が正しいことが確かめられいます。が、初期値は無限大まですべての値をとれるので、21桁ごときじゃ全然足りず、証明にならないのです。
このままコンピュータの計算が進んでいっても結局いたちごっこなので、何か大きな包括的なブレイクスルーになるようなアプローチがないと、証明ができません。
この問題の難しさの一端をお見せしましょう。最初の値が27の場合です。
この場合の計算結果は、下のようになります。
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
このように27という単純さからは想像もつかないほどの計算量となり、1になるまでに111回の計算を必要とします。
数字の羅列で増減が分かりにくいので、グラフにしてみました。
このように可視化すると、数字の上下が激しいことが分かり、最大では9232なんていう5桁に迫らんばかりのバカでかい数字に跳ね上がるのです。
※コラッツ数列は下のようなプログラムで計算できます。
（言語はPythonで、初期値が27の場合）
初期値が27の場合は111回の計算が必要でしたが、初期値がnのときの計算回数はどうなるのか？
この計算回数をCollatz(n)というnの関数として、プログラムを使って値を計算してみます。
下が、計算回数を計算するプログラムです（例によって言語はPython）。
nが1から1000までで計算しグラフにしてみるとこんな感じになります。
点で打つとある程度秩序だって見えますが、それでも式にする（規則性を見出す）ことは難しそうです。
折れ線グラフにすると、もはやホワイトノイズと言っていいレベルです。
2. なぜ証明が難しいのか？ ～筆者なりの見立て～
この予想の証明が難しい理由として、筆者は大きく2つの理由があるのではと考えています。
2-1. 分岐の多さ
証明のアプローチとして、「1から逆算していって、全部の整数が出てくればOK」というものが考えられます。実際1からであれば16までは一通りに逆算できます。ところが、そこから先を考えると、
枝分かれの仕方が先に行けば行くほど不規則になっていくため、本当にすべての整数を網羅できているのか調べるのが大変になってきます。
具体的には、枝分かれするタイミングは「3×奇数+1」の形の偶数になる時なのですが、いつその形の偶数が来るかが読みにくいというわけです。合同式とか使えばある程度読めるかもしれませんが・・・
2-2. 足し算が入ることで素因数分解が壊れてしまう
上にも絡みますが、根本的な要因として「足し算が入ると素因数分解が壊れてしまう」というものがあります。どういうことか、例を挙げてみます。
今回のコラッツ予想は、2で割り切れる回数が多ければ多いほど値が小さくなっていきやすいわけですが、ひとたび奇数が登場した瞬間に一気に数が巨大化します。
例えば997は素数ですが、これにコラッツの操作をしてできる数は2992で、この数は2で4回割り切れ187になります。これをさらに操作すると562となりこれは2で一回しか割り切れません。その結果281にさらに操作をすると844でこれは2で2回まで割り切れ211になる・・・
といった具合に、奇数に操作するたびにできる偶数が「2で何回割り切れるか」が全く予測不能なのです。3をかけるだけでは素因数2の個数は変わりませんが、1を足した瞬間に、その直前の素因数分解の情報がすべて壊れてしまうのです。なにせ差が1同士の整数は互いに素ですからね。
そのため、どの程度で1まで計算し終わるかが初期値からは全く予測不能になってしまうわけです。これが証明を阻む最大の要因だと思います。
3.最後に
興味があれば、色々な初期値で計算を試してみてください。もしかしたら、最終的に1にならない「反例」が見つかるかもしれませんよ。それを見つけただけでも大発見であり、数学界に名を残せます。
