コラッツ予想

出典: 謎の百科事典もどき『エンペディア(Enpedia)』
ナビゲーションに移動 検索に移動

コラッツ予想(こらっつよそう,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千万円の懸賞金をかけている[1]

コラッツむし[編集]

島田正雄によって提案されたパラダイムであり、まったく一般的ではない。
コラッツ予想は「偶数だったら2で割る」「奇数だったら三倍して一を足す」という話なのだが、これを「無限に続くビット列」上で考えると、「偶数だったら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」を用いるとよい)の挙動を観察していると、なかなか興味深い。コラッツ予想の解決に寄与することを願っている。

脚注[編集]