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

 興味深いコメントをいただいたので、記事を見直して大幅に加筆修正しておきました。VBA のコードも改良してあります。

コラッツ予想とコラッツ数列

 ある自然数 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 As Long, Optional ws = False)

  If n < 2 Then
    n = 2
  End If

  Do Until n < 2
    
    Debug.Print n;
        
    If ws = True Then
      ActiveCell = n
      ActiveCell.Offset(0, 1).Activate
    End If

    If n Mod 2 = 0 Then
      n = n / 2
    Else
      n = 3 * n + 1
    End If

  Loop
    
  Debug.Print 1;
    
  If ws = True Then
    ActiveCell = 1
  End If

End Sub

 引数 n には 2 以上の整数を渡すようにしてください (2 未満の数値を受け取っても自動的に n = 2 となります)。ws はオプション引数で、True に設定すると数列をワークシートのアクティブセル (現在選択されているセル) から右側に順次転記します (デフォルトでは False です)。一例として、n = 10 のコラッツ数列を並べてみます。

Sub Test_Collatz()
  Call Collatz(10, True)
End Sub
10  5  16  8  4  2  1

 コラッツ数列が 1 になるまでのステップ数を返すマクロも作っておきました。

'[VBA] コラッツ数列ステップ計算関数

Function Collatz_Step(n As Long) As Long

  Dim stp As Long

  If n < 2 Then
    n = 2
  End If

  Do Until n < 2

    stp = stp + 1

    If n Mod 2 = 0 Then
      n = n / 2
    Else
      n = 3 * n + 1
    End If

  Loop

  Collatz_Step = stp

End Function

 たとえば、ワークシートの適当なセルに

=Collatz_Step(10)

と入力すると「6」が返ります。この関数を使って、横軸にに正整数 n、縦軸に n が 1 に到達するまでのステップ数をプロットしてみると、以下のような結果が得られました。

コラッツ数列ステップ数プロット

 比較的短いステップで 1 に到達する数もあれば、長い手数を要する数もあります。このような直線グラフを見ても特に規則性がないように思えますが、散布図で描いてみると面白い図が現れます。

collatz sequence scatter plot

コメント

  1. 和田文博 より:

    コラッツの予想が面白かったので、上記VBAを2~1000まで実行して
    元数と手数の関係をグラフ化してみたら、不思議な図形になりました

    3D円グラフ -> 宇宙の成り立ち
    散布図 → バーンスレイのシダの親戚みたいな

    ご参考までです

    • Blog Cat より:

      面白いですね!
      貴重な情報、ありがとうございます!
      さっそく、私も Excel でグラフを描いてみました。
      Excelで描いたcollatz予想の散布図
      コラッツ予想には、何か秘密が隠されているのかもしれませんね。

      • 和田文博 より:

        コメントありがとうございます。
        このグラフの規則性だけでは説明できない不思議なドットの存在が興味深いです。

        このサイトを楽しく拝見させていただいています。
        最近VBAで考えているのが、EXCELの膨大な行数を時間経過にした、”世代”です。
        何か不思議な世界があるかもしれません。

タイトルとURLをコピーしました