ある自然数 n から始めて
① n が偶数なら 2 で割ります (n/2)
② n が奇数なら 3 をかけて 1 を加えます (3n + 1)
このような操作を繰り返すとき、どんな n に対しても最終的には
というループに入る、という主張を コラッツの予想 (Collatz Problem) あるいは 角谷の問題 (Kakutani's problem) といいます。また、上の規則にしたがって並ぶ数列のことを コラッツ数列 とよびます。
コラッツ数列を並べてみましょう
たとえば最初の数字を n = 10 としてコラッツ数列を並べてみると
となって、確かに最後には 1, 4, 2, 1 が繰り返されるようになりますね。今度は初期値を 6 としてみると、
やはり 1, 4, 2, 1 のループに入ってしまいます。
コラッツの予想は証明されていません
しかし、本当にどんな n についてもこの法則が成り立つのか、ということはまだ証明されていません。もしかすると、この法則を満たさない数が存在しているかもしれないと考えて、計算機を使って巨大数を探索させていますが、いまだに反例も見つかっていません。こういう一見して簡単そうに見える問題ほど、一般的な証明は難しいのです。
コラッツ数列を生成するマクロ
コラッツ数列を並べる VBA のプログラム(マクロ)を作っておきました。
興味のある人はモジュールにコピーして色々な数字を試してみてください。
n = InputBox("自然数を入力してください")
Debug.Print n;
If n = 1 Then
Exit Sub
End If
For k = 1 To 1000
If n Mod 2 = 0 Then
n = n / 2
Debug.Print n;
Else
n = 3 * n + 1
Debug.Print n;
End If
If n = 1 Then
Exit For
End If
Next k
End Sub
マクロを実行すると自然数の入力を促されます。途中で 1 が現れたら(あとは繰り返しなので)、表示をストップするようにしてあります。ループ処理の上限値は 1000 としてありますが、巨大数を扱う場合はこの部分をもっと大きな値に変えてください。