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$となる.

$\displaystyle \sum_{k=1}^{18} A_{10^k}$の下9桁を求めよ.