Problem 361 の変更点

• 追加された行はこの色です。
• 削除された行はこの色です。
• Problem 361 へ行く。

*[[Problem 361:http://projecteuler.net/problem=361]] 「スー・モース数列の部分数列」 [#m481064b]

''スー・モース数列'' (Thue-Morse sequence) {T&tex{_{n}};} は, 以下の条件を満たす二値数列である.

- T&sub{0}; = 0
- T&tex{_{2n}}; = T&tex{_{n}};
- T&tex{_{2n+1}}; = 1 - T&tex{_{n}};

{T&tex{_{n}};} の最初のいくつかの項は以下のようになる. ~
01101001&color(#f00){10010};1101001011001101001....~

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

数列 {A&tex{_{n}};} の最初のいくつかの項は以下のようになる.
|CENTER:|CENTER:|CENTER:|CENTER:|CENTER:|CENTER:|CENTER:|CENTER:|CENTER:|CENTER:|CENTER:|CENTER:|CENTER:|CENTER:|CENTER:|c
|&tex{n};|0|1|2|3|4|5|6|7|8|9|10|11|12|…|
|A&tex{_{n}};|0|1|2|3|4|5|6|9|10|11|12|13|18|…|

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

&ref(p_361_Thue-Morse1.gif,nolink);の最後の9桁を求めよ.