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

=============================
Paperfolding文字列
=============================
| 初期文字  :math:`a` , :math:`b` , :math:`c` , :math:`d`  による :math:`n` 番目のPaperfolding文字列

.. raw:: html
         
   　　　<script type="text/javascript"  src="../../_static/Paperfolding.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="a"/>
		  </div>
		  <div>
		  b = <input id="b" type="text" size="64" value="b"/>
          </div>
		  <div>
		  c = <input id="c" type="text" size="64" value="c"/>
          </div>
		  <div>
		  d = <input id="d" type="text" size="64" value="d"/>
          </div>
		  </form>
		  <div style="word-wrap:break-word;"> ・P(n) = <Pf>dummy</Pf> </div>
		  <div style="word-wrap:break-word;"> ・P(n) = <Pf_replace>dummy</Pf_replace> </div>

		  
| **注** ：:math:`n` を大きい数にするとおかしくなります．(入力制限で :math:`n<30` としています)
| アルゴリズムはループの方を使用．

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

:math:`n` 番目の **Paperfolding文字列** *(Paperfolding Word)* :math:`P_n` を以下のような定義で生成する．

また，:math:`P_{n}` は， :math:`P_{n-1}` に対して次の規則に従った変換を行うことにより生成することもできる．
ただし， :math:`P_0 = a` とする．

- :math:`a → ab`
- :math:`b → cb`
- :math:`c → ad`
- :math:`d → cd`


 
性質
========================

 - :math:`a → 0`
 - :math:`b → 0`
 - :math:`c → 1`
 - :math:`d → 1`

の置き換えを行うと
 
 - :math:`z_{4n}=0`
 - :math:`z_{4n+2}=1`
 - :math:`z_{2n+1}=z_n`
 
が成立する文字列になる．

| Paperfolding wordに含まれる回文の長さは{0,1,2,3,4,5,6,7,9,11,13}となり14文字以上の長さの回文は出現しない.
| ( :math:`n =` 5のとき初めて13文字の回文が出現する.)



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

:math:`n` 番目のPaperfolding文字列を返す
-----------------------------------------

.. literalinclude:: /Scripts/Python/paperfolding.py
   :pyobject: Pf


参考文献
--------
 - M.Lothaire (July 25, 2005), Applied combinatorics on words (Encyclopedia of Mathematics and its Applications), Cambridge University Press