0%

Problem 361


Problem 361


Subsequence of Thue-Morse sequence

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

  • T0 = 0
  • T2n = Tn
  • T2n+1 = 1 - Tn

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

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

The first several terms of An are given as follows:

n 10 11 12
$A_n$ 10 11 12 13 18

We can also verify that A100 = 3251 and A1000 = 80852364498.

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


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

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

  • T0 = 0
  • T2n = Tn
  • T2n+1 = 1 - Tn

{Tn}的前几项如下所示:
01101001100101101001011001101001….

有些整数的二进制表示是序列{Tn}的子序列,我们定义{An}为将这些数排序后组成的序列。
例如,十进制数18的二进制表示为10010。10010出现在{Tn}中(从T8到T12),因此18是{An}中的元素。
十进制数14的二进制表示为1110。1110永远不会出现在{Tn}中,因此14不是{An}中的元素。

An的前几项如下所示:

n 10 11 12
$A_n$ 10 11 12 13 18

我们还可以验证A100 = 3251以及A1000 = 80852364498。

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