## Subsequence of Thue-Morse sequence

### Problem 361

Published on Sunday, 4th December 2011, 04:00 am; Solved by 217; Difficulty rating: 90%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:

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 .