Thue - Morse列

2015  May 19
Masahiro Mizutani

Thue - Morse列

定義(1)

Thue-Morse列の再帰的定義
thue[0] = 0
thue[2 n] = thue[n]
thue[2 n + 1] = 1 - thue[n]

thue[n_Integer]:=Which[
n==0,0,
EvenQ[n],thue[n/2],
OddQ[n],1-thue[(n-1)/2]
]

thue[5]

定義(1’) 制約条件(condition)を使う

patt /; test  のように書いて、制約条件 test がTrueとなった場合に限りpatt にマッチするとできるMathematica記法を使うと、ほぼ漸化式の定義のように定義できる。

thue[0]:=0;
thue[n_]:=thue[n/2] /; EvenQ[n];
thue[n_]:=thue[(n-1)/2] /; OddQ[n]

thue[5]

定義 (2)

(Subscript[t, n])=nを2進展開して得られる0,1列の総和をMod 2

thue2[n_Integer]:=Mod[Apply[Plus,IntegerDigits[n,2]],2]

Table[thue2[i],{i,0,20}]

n番目までのThue-Morse列

関数 thuemorse[n] はn番目までのThue-Morse列のリストを返す

thuemorse[n_Integer]:=Table[thue[i],{i,0,n}]

thuemorse[20]

n番目までのThue-Morse列の0と1の場所

n番目までの非負整数集合はThue-Morse列値の値 s=0,1 に応じて、disjointに二分割される。
ただし、Mathematicaのリスト位置は1から始まることを考慮し、n=0番目を考えて全体を -1 しておく。

positionThueMorse[n_Integer,s_]:=Flatten[Position[thuemorse[n],s]-1]

positionThueMorse[20,0]

positionThueMorse[20,1]

Multigradeの性質

a=positionThueMorse[8,0]

b=positionThueMorse[8,1]

Apply[Plus,a^1]

Apply[Plus,b^1]

Table[{Apply[Plus,a^i],Apply[Plus,a^i]},{i,1,30}]

定義 (3) as morphism

tm[0]:={0,1};  
tm[1]:= {1,0};
SetAttributes[tm, Listable];

ProuhetThueMorse[lst_List, n_Integer] := Flatten[Nest[tm, lst, n]]

ProuhetThueMorse[{0},3]