コラッツの予想(角谷の問題)

コラッツの予想(角谷の問題)

 ある自然数 n から始めて

  ① n が偶数なら 2 で割ります (n/2)
  ② n が奇数なら 3 をかけて 1 を加えます (3n + 1)

 このような操作を繰り返すとき、どんな n に対しても最終的には

1 → 4 → 2 → 1

というループに入る、という主張を コラッツの予想 (Collatz Problem) あるいは 角谷の問題 (Kakutani's problem) といいます。また、上の規則にしたがって並ぶ数列のことを コラッツ数列 とよびます。
 
 たとえば最初の数字を n = 10 としてコラッツ数列を並べてみると

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

となって、確かに最後には 1, 4, 2, 1 が繰り返されるようになりますね。今度は初期値を 6 としてみると、

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

 やはり 1, 4, 2, 1 のループに入ってしまいます。
 
 しかし、本当にどんな n についてもこの法則が成り立つのか、ということはまだ証明されていません。もしかすると、この法則を満たさない数が存在しているかもしれないと考えて、計算機を使って巨大数を探索させていますが、いまだに反例も見つかっていません。こういう一見して簡単そうに見える問題ほど、一般的な証明は難しいのです。
 

コラッツ数列を生成するマクロ

 コラッツ数列を並べる VBA のプログラム(マクロ)を作っておきました。
 興味のある人はモジュールにコピーして色々な数字を試してみてください。

' [VBA] コラッツ数列生成サブルーチン

Sub Collatz()

  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

 Collatz() を実行すると自然数の入力を促されます。途中で 1 が現れたら(あとは繰り返しなので)、表示をストップするようにしてあります。ループ処理の上限値は 1000 としてありますが、巨大数を扱う場合はこの部分をもっと大きな値に変えてください。


 

コメントをどうぞ

メールアドレスが公開されることはありません。