> For the complete documentation index, see [llms.txt](https://project-euler-ja.gitbook.io/project-euler-ja/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://project-euler-ja.gitbook.io/project-euler-ja/301-400/361-370/p361.md).

# 361 : スー・モース数列の部分数列

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

* $$T\_0 = 0$$
* $$T\_{2n} = T\_n$$
* $$T\_{2n+1} = 1 - T\_n$$

$${T\_n}$$の最初のいくつかの項は以下のようになる.\
01101001\_10010\_1101001011001101001....\
(\* 10010だけ赤強調)

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

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

| $$n$$    | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8  | 9  | 10 | 11 | 12 | … |
| -------- | - | - | - | - | - | - | - | - | -- | -- | -- | -- | -- | - |
| $$A\_n$$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 9 | 10 | 11 | 12 | 13 | 18 | … |

同様に, $$A\_{100} = 3251, A\_{1000} = 80852364498$$となる.

![p\_361\_Thue-Morse1.gif](http://odz.sakura.ne.jp/projecteuler/index.php?plugin=ref\&page=Problem%20361\&src=p_361_Thue-Morse1.gif)$$\displaystyle \sum\_{k=1}^{18} A\_{10^k}$$の下9桁を求めよ.