人生reject

思いついたことをなんとなく書く

『Gijswijt's数列』について

Gijswijt's sequenceとは次の数列である。
1, 1, 2, 1, 1, 2, 2, 2, 3, 1, 1, 2, 1, 1, 2, 2, 2, 3, 2, 1, \cdots
巨大数界隈の人なら知っているかもしれません。
定義が若干わかりづらいです。

定義

a_{1}=1とする。
a_{n+1}=kとし、kは以下の様な数とし、数列を帰納的に定義する。
nまでの数列を用いて文字列a_{1}\cdots a_{n}を考える。
そしてその文字列の末尾部分文字列が末尾で連続する最大の回数をkとする。
(wordを用いて定義すると文字列a_{1}\cdots a_{n}を、XY^{k}と言う形とした時の最大のkということである。)



例を上げて解説する。
a_{2}の時考える文字列はa_{1}のみ、つまり1であり、これの末尾として取れる文字列は1のみであるから1が"1"度のみ連続することとなる。したがってa_{2}=1となる。

a_{3}の時考える文字列は11であり、末尾として取れる文字列は1と11の二種である。
1の時,2度連続(11にたいして"1""1")
11の時、1度連続(11にたいして"11")
したがってk=2となりa_{3}=2となる。

このあたりまではわかりやすい。

とんでn=7の時を考える。
この時考える文字列は112112となる。末尾として取れる文字列は,2,12,112となる。
2の時,1度連続(112112に対して11211"2")
12の時,1度連続(112112に対して1121"12")
112の時,2度連続(112112に対して"112""112")
したがってk=2となりa_{7}=2となる。

巨大数との関係

3が初めて登場するのはn=9の時である。
4が初めて登場するのはn=220の時である。
5が初めて登場するのは約n=10^{10^{23}}の時である。
このようにある数字が初めて登場するときの数列のインデックスはとても大きくなることが分かると思う。
物の本によるとnが初めて登場するときのインデックスは約2^{2^{3^{\cdots^{n-1}}}}となるらしい。
しかし大きいとはいえども指数で書けるレベルなので大きい数の中では小さいなあって思いました。