シュー・モールス文字列

初期文字 \(a\) と \(b\) による \(n\) 番目のシュー・モールス文字列
n =
a =
b =
・TM(n) = dummy
注 ： \(n\) に大きい値を入れすぎるとおかしくなります．(入力制限で \(n<16\) としています)

定義

以下の漸化式によって定義される \(TM_n\) を \(n\) 番目の シュー・モールス文字列 (Thue-Morse string) という．

  • \(TM_0 =\) 0
  • \(TM_{n} = TM_{n-1} + TM'_{n-1}\)

ただし、 \(TM'_{n}\) は \(TM_{n}\) をビット反転させたものである．(例: \(TM_{n}=10010\) ならば \(TM'_{n}=01101\) )

\(TM_{n}\) は \(TM_{n-1}\) に次の規則に従った変換を行うことにより生成することもできる．ただし、\(TM_0\) = 0 とする．

  • 0 \(\to\) 01
  • 1 \(\to\) 10

また，この手続きを無限に繰り返してできる無限文字列を 無限シュー・モールス文字列 という．

  • \(TM_{\infty} =\) 01101001100101101001011001101001100101100110100101101...

例

例えば，最初の6個のシュー・モールス文字列は次の通り．

  • \(TM_0 =\) 0
  • \(TM_1 =\) 01
  • \(TM_2 =\) 0110
  • \(TM_3 =\) 01101001
  • \(TM_4 =\) 0110100110010110
  • \(TM_5 =\) 01101001100101101001011001101001

その長さの系列は1,2,4,8,16,32,...であり， \(n\) 番目のシュー・モールス文字列の長さは \(2^n\) である．

性質

  • \(n\) 番目のシュー・モールス文字列に含まれる回文の最大数以下のようになる
  • \(n\) が偶数ならば \(|TM(n)|\)
  • \(n\) が奇数ならば \(|TM(n-1)|\)
  • 無限シュー・モールス文字列の長さ \(2^n\) の接頭辞は \(TM_{n}\) と一致する
  • 無限シュー・モールス文字列の \(N\) 番目の文字 \(TM_{\infty}[N]\) に関して以下が成り立つ
  • \(TM_{\infty}[0] = 0\),
  • \(TM_{n}[2i] = TM_{n}[i]\) \((0 \leq i \leq 2^n)\)
  • \(TM_{n}[2i+1] = 1 - TM_{n}[i]\) \((0 \leq i \leq 2^n)\)

アルゴリズム

\(n\) 番目のシュー・モールス文字列を返す

無限シュー・モールス文字列の \(n\) 番目の文字を返す