AIとともにコラッツ予想について考えてみた

コラッツ予想とは

$$
T_{n+1}(x) =
\begin{cases}
3x + 1 (xが奇数) \\
x/2 (xが偶数)
\end{cases}
$$
があらゆる初期値で$x=1$にたどり着くかという数学の未解決問題です。
これは非常にプログラミングに相性がいいので計算機科学ではかなり計算されていますが未解決です。
これは1937年にCollatzが提案し、1950年代に計算機の発展とともに話題になっていったという経緯があります。
Stanislaw Ulam氏がLos Alamos研究所でこの問題を紹介し、コンピュータを使った実験が行われたことで爆発的に有名になりました。

増減の期待値(ドリフト)

1ステップごとにどれだけ増えるかの期待値のようなものとしてドリフトというものがあります。
コラッツは掛け算なので対数を取るとよくやる処置を入れて確率的の重みを考えると

$$
D_{step} = \frac{1}{2}log(3) + \frac{1}{2}log \left( \frac{1}{2} \right) \sim 0.2
$$
になります。対数を取っているので$e^{0.2} \sim 1.2$でわずかに増加です。
しかしながら奇数で$3n+1$の時は次は偶数になるのでその重みを後ろの項に掛けると
(より正確にはランダムだと仮定した確率モデルを使って計算しますが、これもヒューリスティック(経験則)です)

$$
D_{weight} = \frac{1}{2}log(3) + log \left( \frac{1}{2} \right) \sim -0.14
$$
とわずかに負になり$e^{-0.14} \sim 0.87$と減少していきます。ここから、1に落ちていくだろうという予測は成り立ちますが数学的な証明にはなりません。

爆発する初期値 : 27

これは1に戻る(停止時間)まで111ステップかかり、値は9232まで到達します。
こういう爆発する初期値が存在するので確率的に下降だとしても絶対1まで下がってくるかは自明ではないのです。

巡回パターン

1から始めると当然、$1 \rightarrow 4 \rightarrow 2 \rightarrow 1$の循環になります。
しかしこれ以外に巡回するパターンを見つければコラッツ予想は偽として決着します。
しかしながらこれはまだ見つかっていません。
因みに、もし巡回軌道があれば約1860億ステップらしいです、どうやったかもわかりませんがJournal of Integer Sequences, Vol. 26 (2023), Article 23.3.5に解説があります。

5n+1型の巡回パターン

$3n+1$を$5n+1$に変えると$13 \rightarrow 66 \rightarrow 33 \rightarrow 166 \rightarrow 83 \rightarrow 416 \rightarrow 208 \rightarrow 104 \rightarrow 52 \rightarrow 26 \rightarrow 13$という1を起点としない巡回パターン、非自明な巡回パターンなどと呼ばれるものが知られています。
その他にも$17→86→43→216→108→54→27→136→68→34→17$も知られています。

5n+1型の発散パターン

$5n+1$型の重みを付けたウェイトを考えると
$$
D_{weight} = \frac{1}{2}log(5) + log \left( \frac{1}{2} \right) \sim 0.11
$$
となり、発散する方向になります、実際に初期値7でも値が急速に巨大化し、Int64の範囲を超えます。
しかしこれが本当に無限大に続くかを数学的に証明できるかは別問題です。

3n+d型

ここで掛ける数を3に戻して後ろの数を3に変えてみる$3n+3$型にすると$6 \rightarrow 3 \rightarrow 12 \rightarrow 6$という巡回パターンを作ります。
更に面白いのが$1 \rightarrow 6$と1が1に戻るパターンはありません。
しかし$3n+5$にすると$1 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1$と1から1のパターンはありますが$5 \rightarrow 20 \rightarrow 10 \rightarrow 5$という巡回パターンがあります、というか数多くのパターンができます。

一般化

このようにコラッツ予想は掛ける数、足す数をパラメータ化して$qn+p$系を考えることでいろいろな姿を見せてくれます。
ただし、$qn+p$が奇数になっては発散するのは当たり前なので$(q, p)$のペアは偶数になるように選ばなければ意味がありません。
更に割る数、もしくは選択をかける数、今なら2もパラメーター化して

$$
T_{n+1}(x) =
\begin{cases}
px + q (n \mod k \neq 0) \\
x/k (n \mod k =0)
\end{cases}
$$
と3パラメーター化した研究もあります。
その場合、最初に出したドリフトの定義が難しくなります。
このような一般化Collatz系の中にはConwayによって計算論的に決定不能な系が存在することが示されています。

検証に使ったコード

検証に使ったコードは以下である。
自明なパターンについては1以外の巡回対策は入れてないので無限ループになる可能性がある。

using Printf

const q = 3
const p = 5
const k = 2

const max_value::Int = 10^2

const next = x -> x % k == 0 ? x÷k : q*x + p
const reverse = T -> (T-p) % q == 0 ? (T-p)÷q : k*T

const drift = (q, p, k)-> log(q/2^k)

function main()
    @printf "%dx%+d\n" q p
    @printf "x/%d\n" k
    @printf "drift : %f\n" drift(q, p, k)
    local base_cycle = Int[]
    local x = next(1)
    while x!=1
        push!(base_cycle, x)
        x = next(x)
    end
    push!(base_cycle, 1)
    println("Trivial Cycle : ", base_cycle)

    for i in 5:max_value
        local cycle = Int[]
        local is_trivial = true
        local x = i
        while x!=1
            push!(cycle, x)
            x = next(x)
#            println(x)
            if x in cycle
                push!(cycle, x)
                println("!!! Initial value : ", i, " Nontrivial Cycle ! ", cycle)
                is_trivial = false
                break
            end
            if x > 10^17
                push!(cycle, x)
                println("!!! n is overflow !!!")
                break
            end
        end
        if is_trivial
            println("Initial value : ", i, " Trivail Cycle : ", length(cycle), " step  max : ", maximum(cycle))
        end
    end
end

main()

最後に

この記事を書くにあたってAI(ChatGPTとClaude)に相談しました。
コードのほとんどは自分で書きました、ヒントはもらいましたが
そのうえで専門分野に近い上に境界領域なのでハルシネーションが起きたことも確認しました。
ただし研究の広げ方(広がっていった方向)などはすごく参考になりました。
コードについては多分、言いなりになって書かせると破綻すると思います、しかし次にやりたいこと等へのヒントとどう書けばいいかなどは的確だったと思います。
実験数学という計算機をフルに使う分野でもあるので遊んでみるのもいいと思います。