ProjectEuler 361 Subsequence of Thue-Morse sequence - 拼圖

361. Subsequence of Thue - Morse sequence

http://projecteuler.net/problem=361


Thue - Morse sequence {Tn} 是一個二進位制的數列，他符合以下條件：

T0 = 0

T2n = Tn

T2n+1 = 1 - Tn


我們可以知道 {Tn} 的前幾項是這樣的：

01101001100101101001011001101001....


定義 {An} 是一個整數數列，而他的每一項用二進位制表示都有出現在 {Tn} 之中

舉例來說，十進位制的 18 用二進位制表示就是 10010

10010 出現在 T8 到 T12 之間，所以 18 是 {An} 的其中一項

14 用二進位制表示為 1110，而 1110 從未出現在 {Tn} 中，故 14 不是 {An} 其中一項


An 的前幾項我們也知道了，如下：

n 0 1 2 3 4 5 6 7 8 9 10 11 12 ...

An 0 1 2 3 4 5 6 9 10 11 12 13 18 ...


我們還能證明出 A100 = 3251 而 A1000 = 80852364498

18
請計算出 Σ A10^k 的末九位
k=1

--