The Thue-Morse sequence {T_{n}} is a binary sequence satisfying:
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_{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 | … |
A_{n} | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 9 | 10 | 11 | 12 | 13 | 18 | … |
We can also verify that A_{100} = 3251 and A_{1000} = 80852364498.
Find the last 9 digits of .
These problems are part of Project Euler and are licensed under CC BY-NC-SA 2.0 UK