コラッツ予想

コラッツ予想(こらっつよそう,Collatz conjecture)は未解決の数学上の難問のひとつである。「コラッツ問題」ともいう。「3n + 1問題」、「3n + 1 予想」ともいう。日本では「いわゆる『角谷予想』」として知られている。

概要

1937年にドイツの数学者ローター・コラッツ(Lothar Collatz）が提出した。

1. 任意の正の数nから開始する。
2. n が偶数の場合は、n を 2 で割る
3. n が奇数の場合は、3倍して1を加える。
4. これを繰り返すと、最終的に必ず1になる。(1になったら終了する)

を「コラッツ変換」という。コラッツ予想は「任意の自然数に対してコラッツ変換を繰り返すと、必ず終了する」という主張である。
コラッツ予想を解くことは難しく、数学者ポール・エルデーシュは「数学はまだこの種の問題に対する用意ができていない」と述べている。コンピューターによる計算により、21桁までは予想が成り立つことが分かっている。しかしすべてので自然数において成立するのか、または反証が存在するのかは分かっていない。
つーても日本人にとって意味のある自然数はゼニカネであり、一円単位が問題になるのはせいぜい億単位なので、実用的にはどうでもいいっちゃあどうでもいい話なのだが、「整数論は、こんな小学生にも解るような問題も解けないのか？(pgr」と言われるのが悔しいため、しつこく究明しようと努力している研究者は多い。

具体例

• 2→1
• 3→10→5→16→8→4→2→1
• 4→2→1
• 5→16→8→4→2→1
• 6→3→10→5→16→8→4→2→1
• 7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1
• 8→4→2→1
• 9→28→14→7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1
• 10→5→16→8→4→2→1
• 11→34→17→52→26→13→40→20→10→5→16→8→4→2→1

のように、数によって1に辿り着くまでに必要な手数に差はあるが、必ず1に辿り着く。初期値が偶数のほうが奇数より手数が小さい傾向にある。偶数の場合は小さくなり、奇数の場合は大きくなるので、当然である。

初期値を「10000」のように大きな数にしても、10000→5000→2500→1250→625→1876→938→469→1408→704→352→176→88→44→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1のように、1に辿り着ける。「17543」のように、大きな数でしかも中途半端な奇数でも、17543→52630→26315→78946→39473→118420→59210→29605→88816→44408→22204→11102→5551→16654→8327→24982→12491→37474→18737→56212→28106→14053→42160→21080→10540→5270→2635→7906→3953→11860→5930→2965→8896→4448→2224→1112→556→278→139→418→209→628→314→157→472→236→118→59→178→89→268→134→67→202→101→304→152→76→38→19→58→29→88→44→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→1とかなりの手数がかかるが、1になる。

試験問題

2011年度の大学入試センター試験の「数学IIB」で出題されたことがある。6と11は、何回の操作で1になるか、という設問であった。

賞金

未解決問題「コラッツ予想」の証明に、日本のベンチャー企業は1億2千万円の懸賞金をかけている。

コラッツむし

島田正雄によって提案されたパラダイムであり、まったく一般的ではない。
コラッツ予想は「偶数だったら２で割る」「奇数だったら三倍して一を足す」という話なのだが、これを「無限に続くビット列」上で考えると、「偶数だったら２で割る」という条件が除去できる。単にシフト操作するだけの話だからだ。
すなわち、「無限に続くビット列」を表すレジスタAとBがあったとして、Aレジスタに任意の自然数を配置した場合、「最下位の on ビットと最上位の on ビットまでの領域」が定義できる。この領域を「コラッツむし（Collatz Worm）」と呼ぶ。
これを、

• A レジスタから B レジスタにコピーする。
• B レジスタの内容を上位（向かって右とする）に1ビットぶんシフトする。
• 空いたところに on ビットを詰める。
• AとBの内容を算術加算して、Aレジスタに書きもどす。

という操作を繰り返すと、最終的に 1 ビットのコラッツむしになるという予想は、コラッツ予想と等価である。
最下位のビットは必ず「1 + 1」になるので、コラッツむしの尻尾は、「無限に続くビット列」空間において少なくとも 1 以上は右に進んでゆき、コラッツむしの頭部も必ず 1 以上は右に進んでゆく。
したがって、コラッツ予想は「コラッツむしの尻尾は必ず頭に追いついて 1 ビットになる」という言明と等価になる。要するに
「32→16→8→4→2→1」
といった2の冪乗数の遷移は、「無限に続くビット列」上で考えると、ただの 1 ビットのコラッツむしでしかない。
パソコン上でコラッツむし（初期値としては「2の冪乗数 - 1」を用いるとよい）の挙動を観察していると、なかなか興味深い。コラッツ予想の解決に寄与することを願っている。