Problem 361 「スー・モース数列の部分数列」

スー・モース数列 (Thue-Morse sequence) {Tn} は, 以下の条件を満たす二値数列である.

{Tn} の最初のいくつかの項は以下のようになる.
01101001100101101001011001101001....

{Tn} の部分数列として現れる各要素を二進表記の整数とし, それを(小さい方から)並べた数列を {An} を定義する.
たとえば, 十進数の 18 は二進表記で 10010 と表される. これは {tn} に現れる ( T&sub{8}; から T&sub{12}; ). したがって, 18 は {An} の要素となる.
十進数の 14 は二進表記で 1110 と表される. これは {tn} に現れない. したがって, 14 は {An} の要素ではない.

数列 {An} の最初のいくつかの項は以下のようになる.

n0123456789101112
An012345691011121318

同様に, A&sub{100}; = 3251, A&sub{1000}; = 80852364498 となる.

&ref(): File not found: "p_361_Thue-Morse1.gif" at page "Problem 361";の最後の9桁を求めよ.


トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2011-12-04 (日) 13:43:29