---

Problem 361

---

Subsequence of Thue-Morse sequence

The Thue-Morse sequence {T_n} is a binary sequence satisfying:

• T₀ = 0
• T_2n = T_n
• T_2n+1 = 1 - T_n

The first several terms of {T_n} are given as follows:
01101001100101101001011001101001….

We define {A_n} as the sorted sequence of integers such that the binary expression of each element appears as a subsequence in {T_n}.
For example, the decimal number 18 is expressed as 10010 in binary. 10010 appears in {T_n} (T₈ to T₁₂), so 18 is an element of {A_n}.
The decimal number 14 is expressed as 1110 in binary. 1110 never appears in {T_n}, so 14 is not an element of {A_n}.

The first several terms of A_n are given as follows:

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	…

We can also verify that A₁₀₀ = 3251 and A₁₀₀₀ = 80852364498.

Find the last 9 digits of $\sum_{k=1}^{18}A_{10^k}$.

---

图厄-摩尔斯序列的子序列

图厄-摩尔斯序列 {T_n}是满足下列条件的二进制序列：

• T₀ = 0
• T_2n = T_n
• T_2n+1 = 1 - T_n

{T_n}的前几项如下所示：
01101001100101101001011001101001….

有些整数的二进制表示是序列{T_n}的子序列，我们定义{A_n}为将这些数排序后组成的序列。
例如，十进制数18的二进制表示为10010。10010出现在{T_n}中（从T₈到T₁₂），因此18是{A_n}中的元素。
十进制数14的二进制表示为1110。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₁₀₀ = 3251以及A₁₀₀₀ = 80852364498。

求$\sum_{k=1}^{18}A_{10^k}$的最后9位数字。

---