Subsequence of Thue-Morse Sequence

The Thue-Morse sequence $\{T_n\}$ is a binary sequence satisfying:
$T_0 = 0$
$T_{2n} = T_n$
$T_{2n + 1} = 1 – T_n$

The first several terms of $\{T_n\}$ are given as follows:
$01101001{\color{red}10010}1101001011001101001\cdots$

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_8$ to $T_{12}$), 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$
$\cdots$

$A_n$
$0$
$1$
$2$
$3$
$4$
$5$
$6$
$9$
$10$
$11$
$12$
$13$
$18$
$\cdots$

We can also verify that $A_{100} = 3251$ and $A_{1000} = 80852364498$.

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

The question about finding the last 9 digits of the cumulative sum of a specific sequence {A_n} up to the 10^kth term with k ranging from 1 to 18, has a direct connection with the number theory, combinatorics, and computational mathematics. Unfortunately, a standard mathematical approach or formula that allows the easy calculation of such digits of the sum of such kind of sequence does not exist.

The Thue-Morse sequence is a binary sequence, thus it deals with numbers and their representation in binary format. The sequence {A_n} is the sorted sequence of integers for which their binary representations appear as a subsequence in {T_n}. The direct mathematical calculation of this sequence {A_n} is not practically feasible in a simple way, especially for large numbers.

However, it is possible to calculate the exact values of A_{10^k} for small k using computer algorithms and programming. A possible approach would involve generating the Thue-Morse sequence up to a certain index and then checking binary representations of integers to find the members of the sequence {A_n}. This would involve both binary manipulation and big number arithmetic.

Finding the last 9 digits of a sum requires calculating the sum modular 10^9, because the remainder when divided by 10^9 gives the last 9 digits of the number. Therefore, each individual number A_{10^k} must be reduced modulo 10^9 before summing it.

Summarizing, to get the final answer, this problem requires a complex approach which implies the generation of the Thue-Morse sequence, the generation of the binary numbers and verification of their presence in the Thue-Morse sequence, the generation of the sequence {A_n}, and precise calculation of large numbers modulo 10^9. This lies within the field of computational mathematics and specifically computer programming, hence, it would be a good Challenge for the Math Olympiad or similar competition.

The detailed mathematical formulation or standard mathematical solution of this specific problem, however, does not exist and may require considerable computational resources to be solved.

More Answers: