.. -*- coding: utf-8; -*-

==========================================
シュー・モールス文字列
==========================================


| 初期文字 :math:`a` と :math:`b` による :math:`n` 番目のシュー・モールス文字列


.. raw:: html
         
   　　　<script type="text/javascript"  src="../../_static/ThueMorse.js">
         </script>

          <form onsubmit="return false;" autocomplete="off">
          <div> n = <input id="n" type="int" size="64" value="0"/></div>
		  <div>
		  a = <input id="a" type="text" size="64" value="0"/>
		  </div>
		  <div>
		  b = <input id="b" type="text" size="64" value="1"/>
          </div>
          </form>
		  <div style="word-wrap:break-word;"> ・TM(n) = <TM>dummy</TM> </div>

| **注** ： :math:`n` に大きい値を入れすぎるとおかしくなります．(入力制限で :math:`n<16` としています)

定義
=========================================

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

- :math:`TM_0 =` 0
- :math:`TM_{n} = TM_{n-1} + TM'_{n-1}`

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

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

- 0 :math:`\to` 01
- 1 :math:`\to` 10

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


- :math:`TM_{\infty} =` 01101001100101101001011001101001100101100110100101101...


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

- :math:`TM_0 =` 0
- :math:`TM_1 =` 01
- :math:`TM_2 =` 0110
- :math:`TM_3 =` 01101001
- :math:`TM_4 =` 0110100110010110
- :math:`TM_5 =` 01101001100101101001011001101001

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





性質
========================
- :math:`n` 番目のシュー・モールス文字列に含まれる回文の最大数以下のようになる
- :math:`n` が偶数ならば :math:`|TM(n)|` 
- :math:`n` が奇数ならば :math:`|TM(n-1)|` 


- 無限シュー・モールス文字列の長さ :math:`2^n` の接頭辞は :math:`TM_{n}` と一致する　

- 無限シュー・モールス文字列の :math:`N` 番目の文字 :math:`TM_{\infty}[N]` に関して以下が成り立つ
- :math:`TM_{\infty}[0] = 0`,
- :math:`TM_{n}[2i] = TM_{n}[i]` :math:`(0 \leq i \leq 2^n)`
- :math:`TM_{n}[2i+1] = 1 - TM_{n}[i]` :math:`(0 \leq i \leq 2^n)`



.. .. todo:: 出典探し（あれば）

アルゴリズム
=========================================

:math:`n` 番目のシュー・モールス文字列を返す
-----------------------------------------------

- 定義にしたがって作ったもの（ :download:`/Scripts/Python/thue_morse1.py`）

.. literalinclude:: /Scripts/Python/thue_morse1.py
    :pyobject: tm
	
- 0 :math:`\to` 01,1 :math:`\to` 10の規則に従って生成するもの（ :download:`/Scripts/Python/thue_morse2.py`）

.. literalinclude:: /Scripts/Python/thue_morse2.py
    :pyobject: tm




無限シュー・モールス文字列の :math:`n` 番目の文字を返す
------------------------------------------------------------

- 愚直な，遅いバージョン
- 何番目の文字列に出現するかを求めてから文字を返す :download:`/Scripts/Python/infthue_morse.py`
 
.. literalinclude:: /Scripts/Python/infthue_morse.py
    :pyobject: inftm

.. .. todo::
	他にも，効率のよいものが書けるのか？