コラッツ予想（角谷の問題）

　興味深いコメントをいただいたので、記事を見直して大幅に加筆修正しておきました。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 に到達する数もあれば、長い手数を要する数もあります。このような直線グラフを見ても特に規則性がないように思えますが、散布図で描いてみると面白い図が現れます。

　VBA の Long 型に格納できる値の上限は 2147483647 なので、コラッツ数列の中にこの値を超える項が出現するとオーバーフローとなってしまいます。オーバーフローを発生させる最小の初期値を発見するコードを載せておきます。

'[VBA] 任意の初期値を受け取ってコラッツ数列の最大値を返す関数

Function Collatz_Max(k As Long)

    Dim n As Long
    Dim max_val As Long

    n = k

    max_val = n

    If n < 2 Then
        n = 2
    End If

    Do Until n < 2

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

        If n > max_val Then
            max_val = n
        End If

    Loop

    Collatz_Max = max_val

End Function

'[VBA] オーバーフローが発生する数列の最小初期値を発見するマクロ

Sub Find_Overflow()

    Dim i As Long, x As Long

    On Error GoTo ErrLabel

    For i = 5 To 300000
        Collatz_Max(i)
    Next i

ErrLabel:
    Debug.Print i

End Sub

　Find_Overflow() を実行すると 113383 が返ります。ですから、VBA で生成できるコラッツ数列の初期値は最大で 113382 ということになります。