Period-doubling文字列

初期文字 \(a\) , \(b\) による \(n\) 番目のPeriod-doubling文字列

・Pd(n) = dummy

注：\(n\) を大きい数にするとおかしくなります．(入力制限で \(n<20\) としています)

定義

\(n(n \geq 0)\) 文字目の Period-doubling文字列 (Period-doubling Word) \(Pd[n]\) を以下のような定義で生成する．

\(Pd[n] =v_2(n+1)mod2\)

ここで

\(v_2(n+1) = a\) \(（aは2^a \mid (n+1)，2^{a+1} \mid \hspace{-.67em}/ \ (n+1)　を満たす）\)

定義に従って生成されるPeriod-doubling文字列は以下のようになる．

\(Pd = 0100010101000100...\)

また，\(n(n \geq 0)\) 番目のPeriod-doubling文字列 \(Pd_n\) は， \(Pd_{n-1}\) に対して次の規則に従った変換を行うことにより生成することもできる．
ただし， \(Pd_0 = 0\) とする．

Allouche, Jean-Paul, and Jeffrey Shallit. Automatic sequences: theory, applications, generalizations. Cambridge university press, 2003.