コラッツ予想に関する予想について
はじめに
どうもこんにちは．皆さんは，過去に投稿した記事 コラッツ予想に関する予想の提案 という記事をご覧になられたことがあるでしょうか．この記事では，
$$ c(n)= \begin{cases}\frac n2&\mathrm{if}\ 2|n\\3n+1&\mathrm{otherwise} \end{cases} $$
として$c^{(f(n))}(n)$の漸近的な挙動について，二つの予想をしていました．
\begin{align}
c^{(n)}(n)&\le7288\\
c^{(\floor{\sqrt n})}(n)&\le3830704
\end{align}
が予想されている．ただし等号については，上の式は$n=63,$下の式は$n=8510$で起こる．
つまり，$n$に対してCollatz変換を$n$回，あるいは$\sqrt n$回繰り返すことを考えると，Collatz変換で大きくなる速度よりも小さくなる速度のほうが大きい，ということになります．それに対して，次のこともわかっています．
自然数$n$に対する関数
$$
c^{(\floor{\ln n})}(n)
$$
は，有界ではない．
つまり，仮に$c^{(f(n))}(n)$が有界になるとすれば，そのような$f$は代数関数オーダーであろうということになります．逆に有界でないときの条件はどのようになるのでしょうか．仮に有界だとして，その上限はどのような挙動をするのでしょうか．これについて考えていきたいと思います．
数値計算
というわけで数値計算を行っていきます．実際に関数を考えたときに有界であるときの上限を与えるのは困難(というか，与えることができてしまったらその時点でCollatz予想が解決してしまいます)なので，証明することはできないと思います．まず，次のような定義をします．
実数$k$に対して
\begin{align}
a_n=c^{(\floor{n^{1/k}})}(n)
\end{align}
で定まる数列$a_n$を考える．この数列の上限と上限を与えるような整数$n$がただ一つであるとき，その数$n$とその上限を$u_1(k),u_2(k)$で表し，組$(u_1(k), u_2(k))$を$\bm u(k)$で表す．
つまり現状の予想では，
\begin{align} \u(1)&=(63, 7288),\\ \u(2)&=(8510, 3830704). \end{align}
ということになります．直感的には$k$が大きくなると$\u(k)$の各要素は大きくなっていくので，どこかで$\u$の何らかの要素が定義できない(発散する)という気がしますし，逆に増大し続けるけれど値がちゃんと定まるという感じもします．前者については厳密に論証することは不可能ではなさそうですが，これもやはり難しそうな気はします．ここまで定式化しておけば数値計算していけそうです．$k<0$のとき，$0< n^{1/k}<1$なので，$0$回合成(恒等写像)になってしまって面白くないので，$k>0$のときを考えます．数値計算によって，次の結果を得ました．($0.1$ごとに区切っているだけ)
| $k$ | $u_1(k)$ | $u_2(k)$ |
|---|---|---|
| $0.5$ | $1$ | $1$ |
| $0.6$ | $3$ | $2$ |
| $0.7$ | $3$ | $8$ |
| $0.8$ | $31$ | $4616$ |
| $0.9$ | $41$ | $3238$ |
| $1$ | $63$ | $7288$ |
| $1.1$ | $94$ | $3644$ |
| $1.2$ | $231$ | $9232$ |
| $1.3$ | $353$ | $9232$ |
| $1.4$ | $703$ | $37624$ |
| $1.5$ | $703$ | $55667$ |
| $1.6$ | $1249$ | $167002$ |
| $1.7$ | $2631$ | $250504$ |
| $1.8$ | $4255$ | $1212064$ |
| $1.9$ | $5673$ | $3830704$ |
| $2$ | $8510$ | $3830704$ |
| $2.1$ | $45127$ | $26404378$ |
| $2.2$ | $60975$ | $150343370$ |
| $2.3$ | $270271$ | $4386828320$ |
| $2.4$ | $360361$ | $4868756126$ |
| $2.5$ | $608111$ | $16432051930$ |
| $2.6$ | $1042431$ | $84503790916$ |
| $2.7$ | $4809759$ | $22559788912$ |
| $2.8$ | $2643183$ | $169297616428$ |
| $2.9$ | $19638399$ | $13445132519231$ |
| $3$ | $39276798$ | $306296925203752$ |
$u_1(k)$についての計算は$k=3$のときは$a_{100000000}$までの計算で，$k<3$については$a_{50000000}$までの計算です．利用したソースコードとしては前回のをほとんどそのまま利用していて，次のようになっています．(つまりこの表はプログラムから得られた結果の一部分でしかないです)
import math
def c(n, steps):
num = n
for _ in range(steps):
if n == 1:
break
if n % 2 == 0:
n //= 2
else:
n = 3 * n + 1
num = n
return num
def main(st, ste, ed, ede, ex):
try:
max = 0
for i in range(st * pow(10,ste), ed * pow(10,ede)+1):
ulam = c(i, math.floor(pow(i, 1/(ex))))
if ulam > max:
max = ulam
print([i,max])
print("end")
基本的な部分は前回書いた記事と同じで，合成回数の部分だけいじった感じですね．
予想&考察など
先に挙げた数値計算による予想から，次の予想を立てました．
$k\gtrsim0.9$であるとき，ある定数$A, B$があって
\begin{align}
k\sim B+A\ln\ln u_i(k)\quad(i=1, 2)
\end{align}
となるであろう．
参考にしたグラフが
こちら
です．$u_i$に対する$,B$の値を$A_i, B_i$のように書くことにして，その値の近似値としては，
\begin{align}
A_1&\approx1.38042\\
B_1&\approx-1.07106\\
A_2&\approx1.42515\\
B_2&\approx-1.95844
\end{align}
くらいになりそうです．これだけ見てもへぇ～という感じですが，何かこれがいい感じの定数に収束したりするんでしょうか．
個人的には$k$をより大きくした時により精密な評価を与えたい(考えている区間が小さすぎるので一次近似くらいしかできない)ので，$k>4$の時の挙動も知りたいのですが，計算量に大きく寄与する$u_1$が二重指数関数程度で増大するので少し厳しそうです...効率的なアルゴリズムがあればいいのですが...
例えば，当初期待していた性質として，$k< l$であるならば$u_i(k)\le u_i(l)$という性質がありました．これが正しいなら大きくなったところで$u_i(l)$を計算するために必要な計算量を$u_i(k)$の分削減できるので多少なりとも楽になるのですが，残念ながらそうもいきませんでした．見てみるといくつか値が逆転しているところがありますね．大小関係が逆転するという現象が，有限回しか発生しないような例外的な現象なのか，それとも何度も起こるありふれた現象なのかもよくわかりません．このことについて予想するためにはより大規模な計算を行う必要があると思います．
ただし，$k$の幅のみ小さくしたとしても，一度床関数を合成しているので$k$の違いが小さすぎると差が出なくなるので$k$の値を大きくする方向にも計算をしていく必要があると思います．これをするには計算量の壁が大きすぎるので，個人的にはプログラム自体の改良が必要だと思っていて競技プログラミングをやっているような人に協力を仰ぎたい，というのも個人的にはあります．
もう一つ個人的に気になるのが，現在計算した近傍で二重指数関数程度で増大しているように見えますが，これが一体どうしてなのだろうかというのがあります．これに関しては個人的によくわからなかったので，直感的な説明が与えられるといいですね．