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

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

  • T0 = 0
  • T2n = Tn
  • T2n+1 = 1 - Tn

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

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

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

n0123456789101112
An012345691011121318

同様に, A100 = 3251, A1000 = 80852364498 となる.

p_361_Thue-Morse1.gifの最後の9桁を求めよ.


添付ファイル: filep_361_Thue-Morse1.gif 359件 [詳細]

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