『Gijswijt's数列』について
Gijswijt's sequenceとは次の数列である。
巨大数界隈の人なら知っているかもしれません。
定義が若干わかりづらいです。
定義
とする。
とし、は以下の様な数とし、数列を帰納的に定義する。
までの数列を用いて文字列を考える。
そしてその文字列の末尾部分文字列が末尾で連続する最大の回数をとする。
(wordを用いて定義すると文字列を、と言う形とした時の最大のということである。)
例を上げて解説する。
の時考える文字列はのみ、つまり1であり、これの末尾として取れる文字列は1のみであるから1が"1"度のみ連続することとなる。したがってとなる。
の時考える文字列は11であり、末尾として取れる文字列は1と11の二種である。
1の時,2度連続(11にたいして"1""1")
11の時、1度連続(11にたいして"11")
したがってとなりとなる。
このあたりまではわかりやすい。
とんでの時を考える。
この時考える文字列は112112となる。末尾として取れる文字列は,2,12,112となる。
2の時,1度連続(112112に対して11211"2")
12の時,1度連続(112112に対して1121"12")
112の時,2度連続(112112に対して"112""112")
したがってとなりとなる。
巨大数との関係
が初めて登場するのはの時である。
が初めて登場するのはの時である。
が初めて登場するのは約の時である。
このようにある数字が初めて登場するときの数列のインデックスはとても大きくなることが分かると思う。
物の本によるとが初めて登場するときのインデックスは約となるらしい。
しかし大きいとはいえども指数で書けるレベルなので大きい数の中では小さいなあって思いました。