コラッツ予想のステップ数
コラッツ予想のステップ数を予測する式についての記事です
最初に厳密にステップ数を予測する式の紹介をして、次にその式を近似して変形した結果、下記の論文で紹介されてる近似式とほぼ同じになったよって感じです。
↓ ついでに、この質問の式の方が視覚的には近く見えたのでこれも比較します。
コラッツ予想の概要
この記事にたどり着いた時点で「そんなん知っとるわい！ぼけなす！
」って思われそうですが、一応コラッツ予想について簡単に説明します。
任意の正の整数 n が与えられたとき、その n に対して下記の操作を繰り返します。
n が偶数なら ... n / 2
n が奇数なら ... 3 * n + 1
コラッツ予想とは、この操作を繰り返すとどんな整数でも 1 になるって予想です。
中学生でも十分に理解できる予想ですね。例えば n = 3 の時は次のように値が変化していきます。
3 \to 10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1
なるほど！って感じですね。この記事の主題であるステップ数とは、ある整数が 1 に到達するまでに施された操作の回数です。
上の例では 3 から始まり、 10, 5, 16, 8, 4, 2, 1 と 7 回の操作が行われているので、整数 3 のステップ数は 7 になりますね。
コラッツ関数と n 回合成写像
定義域、値域がともに奇数である次の関数 c をコラッツ関数と名付けます。
c(x)=\frac{3x+1}{2^{v_2(3x+1)}}
ここで v2 は引数が持つ 2 の冪を返す2進付値とします。（詳しく知りたい人はこちら）
例えば c(3) は次のようになります。
c(3)=\frac{3 \times 3 + 1}{2^{v_2 (3 \times 3 + 1)}}=\frac{10}{2^1}=5
分母で常に分子が持つ 2 の冪を割っているので、単純に奇数部分が残るってわけですね。コラッツ予想に現れる数値の変化の内、「偶数なら割る」って操作を省略した感じです。
コラッツ関数 c は n 回合成した写像 c^n をシンプルに表現できるという利点を持ちます。それが次の式です。
c^n (x)=\frac{A_n (x)}{2^{v_2 (A_n (x))}}
A_n = 3^{n} \left( x + \sum_{k=0}^{n-1} 3^{-1-k} \cdot 2^{v_2 (A_k (x))} \right) , A_0 (x) = x
シンプル(?)ですね。今後はコラッツ関数で c^n(x) = 1 を満たす最小の n をステップ数と呼ぶことにします。偶数で割るステップは数えません。
この式でいろいろ遊べるのですが、今回はその中でもステップ数に着目しました。
ステップ数の導出
さっきの式は十分に大きい n でも成り立ちます。ステップ数を超えても成り立つわけですね。てことで、奇数 x のステップ数を s としてさっきの式をもっかい考えます。
奇数 x がステップ数 s に到達すると、c^s (x) = 1 が成り立ちます。そう定義したから当たり前ですね。
さらに合成を行って、s < n の領域でも c^n (x) = 1 です。これを利用すると次の式を得ることができます。
2^{c + 2n} = 3^{n} \left( x + \sum_{k=0}^{s-1} 3^{-1-k} \cdot 2^{v_2 (A_k (x))} + \sum_{k=s}^{n-1} 3^{-1-k} \cdot 2^{c + 2k} \right)
論文でもないので詳細は省略しますが、ステップ数以降の関数の合成では常に 2k ずつ 2 の冪が増えることを利用して、ステップ数以前と以後で和を分割しています。
式を整理すると x についての式を得ることができます。
x = 2^c \left( \frac{4}{3} \right)^s - \sum_{k=0}^{s-1} 3^{-1-k} \cdot 2^{v_2 (A_k (x))}
これを s について解くと、ある奇数 x のステップ数を完全に求めることができます。
近似！
といってもさすがに大変で、ある奇数 x がステップ数に到達するまでに 2 で割らる回数をどうにか定式化する必要があります。
現在絶賛研究中ですが、わからなくても近似式を求めるくらいはできるのでやっちゃいます。
1 <= k <= [s/2] の区間では k + c、[s/2] + 1 <= k <= s - 1 の区間では 3k + c - s となると近似します。[s/2] は s/2 以下の最大の整数です。
この近似の理由はデータから得た経験的なものだと思ってください。正確な背景はちゃんとできてからにします。
この近似の下で式を整理すると次を得ます。
2^{-c} x = \frac{4}{5} \left(\frac{4}{3} \right)^s + \frac{6}{5} \left(\frac{2}{3} \right)^{\frac{s}{2}} - 1
両辺の対数を取ると非常に速い速度で次のように近似することができます。
\log \left( \frac{4}{5} \left(\frac{4}{3} \right)^s + \frac{6}{5} \left(\frac{2}{3} \right)^{\frac{s}{2}} - 1 \right) \approx \log \frac{4}{3} s + \log \frac{4}{5}
これを s について解いて、次のステップ数に関する近似式を得ます。
s \approx \frac{1}{\log \frac{4}{3}} \left( \log x -c\log 2 -\log\frac{4}{5} \right)
未知パラメータ c は奇数 x の選び方に依存しますが v2(A1(x)) = v2(3x + 1) が今回の近似においては成り立ちます。
v2(3x + 1) は多くの x を選んで平均を取ればほぼ 2 となりますが、x が大きくなるにしたがって 2 の冪の間隔が大きくなるため、その平均は若干 2 よりも大きな数値となります。
というわけで！これがステップ数の近似式です！
s \approx \frac{1}{\log \frac{4}{3}} \left( \log x -v_2(3x+1)\log 2 -\log\frac{4}{5} \right) \approx \frac{1}{\log \frac{4}{3}} \left( \log x - \log\frac{16}{5} \right)
既存の研究と比較
既存の研究で出ていた近似式は次の通りです。
S = 24.0116 \log_{10} N - 12.809
今回この記事で求めたステップ数は偶数で割るステップを省略しています。平均してちょうど 3 倍だけステップ数に差が出るので、自分が求めた式に 3 を乗じて比較します。
3s \approx \frac{3}{\log \frac{4}{3}} \left( \log x - \log\frac{16}{5} \right) \approx 24.0128 \log x - 12.1276
いい感じですね！
ただしこれは外れ値みたいなステップ数の奇数も併せての平均なので、見た目的にはあんまりよろしくない係数になってます。
実際には冒頭で紹介したもう一個の近似式の方がよく見えます。
S\approx10.45\ln(n)-3
従来研究の式と、c = v2(3x+1) とした自分の式でグラフを描画すると下記のようになります。
v2(x) は無理やり下記の式で表現しました。実際にはここまで振動的にはならないですが傾向はこんな感じです。
v_p(x) = \sum_{n=1}^{\infty} \frac{1}{2p^n} \left[ \frac{\sin\left( 2\pi x - \frac{\pi x}{p^n} \right)}{\sin\left( \frac{\pi x}{p^n} \right)} + 1 \right] , p = 2
ついでに。実際の「偶数を割る操作を省略したステップ数」と今回の近似式を比べると次のようになります。
拡大してみると、必死で実際のステップ数を追おうとしてるかわいい姿が見れます。