概要[]
2020年9月25日現在GoucherのT関数はベクレミシェフの虫と十分に大きな入力においてほぼ同じ(FGHにおいて \(f_{\varepsilon_{0}}(n)\) 程度)の増加速度になると言われている。しかし本当はそうではなくて「GoucherのT関数の増加速度は大体 \(f_{\omega^{\omega^{\omega^{\omega^{\omega^{\omega^{\omega^{\omega^{\omega^{\omega}}}}}}}}}}(n)\) 程度で、ベクレミシェフの虫と比べてGoucherのT関数はすごく弱いんじゃないか」という主張をし、そのうえで \(f_{\varepsilon_{0}}(n)\) になりそうな定義を再定義する。
T関数の小さくて大きな問題点[]
ベクレミシェフの虫はGoucherのT関数とほぼ同じ展開をしているが、重要な違いがある。GoucherのT関数では10進数の各位が活躍している。この「10進数の各位」に当たる部分は、ベクレミシェフの虫では任意の非負整数のリストの各要素と対応してる。だからGoucherのT関数は「ベクレミシェフの虫でリストを定義するときに各要素に入れることができる整数を0～9の10種類に制限したもの」だともいえる。
たとえばGoucherのT関数に \(10^{100}\) を入れるとあーってなる。そしてその後、ふつうのべクレミシェフの虫だとどうなるのか(リストの1要素に \(10^{100}\) を入れるとどうなるのか)、制限されたべクレミシェフの虫ではどうなっちゃうのか(リストの各要素に \(10^{100}\) の十進表記の各桁を左から位の大きい順で入れていく)も確認してみて！
もしGoucherのT関数がベクレミシェフの虫と十分に大きな入力にたいしてほぼ同じ増加速度といえるなら、その理由がよく分からない。なぜかというと、これまで「各要素に入れることができる数字の範囲がそのままFGHで近似したときの \(\omega\) の累乗の高さに関わってくる」と思っていたから。もしこの想像が正しいなら、GoucherのT関数の増加速度は大体 \(f_{\omega^{\omega^{\omega^{\omega^{\omega^{\omega^{\omega^{\omega^{\omega^{\omega}}}}}}}}}}(n)\) 程度
になると予想してしまいたくなる。つまり、「ベクレミシェフの虫と比べてGoucherのT関数はすごく弱いんじゃないか」という主張ができる。ここではこの予想が正しいとして \(f_{\varepsilon_{0}}(n)\) になるようにGoucherのT関数を自分なりに再定義して、それを"GoucherのT関数(Gaoji版)"と名付ける。
考え方[]
n進法は、各桁に使用できる記号の数を表している。ベクレミシェフの虫では、初期条件として与えたリストの各要素のうち最も大きな値より大きな値は展開の中で絶対に現れない。これは \((初期条件で与えたリストの各要素の最大値の数)+1\) だけ記号を用意しておけばいいことを表す。つまりnを入力するときにはn+1進法以上で定義することが必要なのだが、初期条件で与えた進法は関数を反復させるときに変えてはいけないという条件が生まれる。これを守らないと各桁の値が全部1になったり、各桁の値が全部変わってしまったり、計算が終わらなかったりすることがある。
定義[]
- \(n,L,R\) は非負整数、 \(m\) は \(m\gt 1\) の整数
- \(len_{m}(n)\) は \(n\) の \(m\) 進表記の桁数を返す関数
- \(n=L\times m^{len_{m}(R)}+R\) となる非負整数 \(L,R\) が一意に存在する。ただし
- \(L\) の \(m\) 進表記の一の位は、\(n\) の \(m\) 進表記の一の位より小さい
- \(R\) の \(m\) 進表記の全ての位は、 \(n\) の \(m\) 進表記の一の位以上の大きさ
このとき非負整数を入力して非負整数を返す関数 \(hg_{m}(n)\) を定義する。
\begin{eqnarray} hg_{m}(n) = \begin{cases} \frac{n}{m} & ( len(n)\gt 1\:かつ\:n\:のm進表記の一の位が0 ) \\ n & ( n=0\:または\:n=1 ) \\ L\times m^{(n+1)\times len_{m}(R-1)}+\sum_{k=0}^{n} ((R-1)\times m^{k\times len_{m}(R-1)}) & ( n\gt 1\:かつ\:n\:のm進表記の一の位が0でない ) \end{cases} \end{eqnarray}
非負整数を入力して非負整数を返す関数 \(TG(n)\) を定義する。 \(hg_{n+1}^{\circ i}(n)\leqq1\) となる最小の \(i\) について \[TG(n)=i\] とし、これをGoucherのT関数(Gaoji版)とする。
大きさ[]
FGHで \(f_{\varepsilon_{0}}(n)\) 程度である。また \(n\gt1\) において、追記によって修正されたGoucherのT関数 \(T(n)\) に対し、 \(TG(n)\gt T(n)\) だと思っていたが、不安になってきたからここに拡張版を書いた。
n=1(2進数)
hg_{n+1}^i(n)
i=0 1
TG(1)=0
n=2(3進数)
hg_{n+1}^i(n)
i=0 2
i=1 11
i=2 10101010
i=3 1010101
i=4 1010100...0(820個の0)
i=824 101010
i=825 10101
i=826 10100...0(91個の0)
i=917 1010
i=918 101
i=919 100000000000
i=930 1 TG(2)=930
n=3(4進数)
hg_{n+1}^i(n)
i=0 3
i=1 222
i=2 221...221(42個の221)
i=3 221...221220・・・221...221220(4^(42*3)より多い数の221...221220)
i=4 221...221220・・・221...22122
追記[]
巨大数研究Wikiに書かれてあったGoucherのT関数の定義が出典元の定義と異なっていて、修正が入った。修正後の定義はべクレミシェフの虫と本当の意味でほとんど同じな定義になっている。つまり各桁としていたところを非負整数の列に定義しなおしている。