任取两个正整数a和b，乌拉姆序列$U(a,b)$按如下方式定义：$U(a,b)_1=a$，$U(a,b)_2=b$，对$k>2$，$U(a,b)_k$是比$U(a,b)_{k-1}$大，且能用$U(a,b)_1$到$U(a,b)_{k-1}$之间的不同两项之和所唯一表示的最小整数。

例如$U(1,2)$的前几项如下： \begin{align*} U(1,2)_1&=1, \\ U(1,2)_2&=2, \\ U(1,2)_3&=U(1,2)_1+U(1,2)_2=1+2=3, \\ U(1,2)_4&=U(1,2)_1+U(1,2)_3=1+3=4, \\ U(1,2)_5&=U(1,2)_2+U(1,2)_4=2+3=6, \\ U(1,2)_6&=U(1,2)_2+U(1,2)_5=2+6=8, \\ U(1,2)_7&=U(1,2)_3+U(1,2)_6=3+8=11, \\ \end{align*} 其中由于 \begin{align*} 5&=1+4=2+3=U(1,2)_1+U(1,2)_4=U(1,2)_2+U(1,2)_3, \\ 7&=1+6=3+4=U(1,2)_1+U(1,2)_5=U(1,2)_3+U(1,2)_4, \\ 9&=1+8=3+6=U(1,2)_1+U(1,2)_6=U(1,2)_3+U(1,2)_5, \\ 10&=2+8=4+6=U(1,2)_2+U(1,2)_6=U(1,2)_4+U(1,2)_5, \\ \end{align*} 都不是唯一表示，因此跳过了这些数字。

求出下式的值： $$\sum_{n=2}^{10}U(2,2n+1)_{10^{11}}.$$

本题难度:

解答

根据该论文的结论，形如$U(2,2n+1)$ ($n\ge 1$)的乌拉姆序列中只有两项是偶数，分别是 $$U(2,2n+1)_1=2, \quad U(2,2n+1)_{n+4}=4n+4,$$ 且对充分大的k有具有如下的周期性： $$U(2,2n+1)_{k+T_n}=U(2,2n+1)_{k}+D_n.$$ $T_n$的值在OEIS A100729中给出，$D_n$的值在OEIS A100730中给出。

最小的、能满足上述周期性的k并未在上述文献中提及，不过观察$n=2$时的序列(见OEIS A007300)以及$n=3$时的序列(见OEIS A003668)可以猜测k从$n+5$开始，最后的结果显示这至少对本题而言是正确。

仍需要生成至少一个周期内的项来计算第$10^{11}$项。

首先注意到只有两项是偶数，因此除这两项以外，其它项显然只能由这两个偶数项（2或$4n+4$）之一加上另一个奇数项获得，从而容易看出前六项应当是 $$2,2n+1,2n+3,\ldots,4n+3,v,4n+5,4n+7,$$ 记$v=4n+4$，其它项可以用以下方式生成：

用哈希表和列表同时保存已生产的序列，假定当前项是$a$，则只要$a+2-v$不在已经生成的序列中，下一项就应该是$a+2$，否则下一项应当具有$b+v$的形式，其中b是已生成的项中第一个满足$b+v>a$且$b+v-2$不在已生成的序列中的项。

显然b是递增的，因此只需要从上一次的位置开始搜索即可。

结果是$3916160068885$。

注：本题需要有较强的文献检索能力。

t=[0,0,32,26,444,1628,5906,80,126960,380882,2097152]
d=[0,0,126,126,1778,6510,23622,510,507842,1523526,8388606]
z=10**11

r=0
for n in range(2,11):
    m,k=z/t[n],z%t[n]
    if k<=n+4:
        k+=t[n]
        m-=1
    v=4*n+4
    u=[0,2]+[2*(n+i)-3 for i in range(2,n+4)]+[v]+[v+1,v+3]
    s=set(u)
    j=2
    while len(u) < k+1:
        if u[-1]+2-v not in s:
            s.add(u[-1]+2)
            u.append(u[-1]+2)
        else:
            while u[j]+v < u[-1] or j==n+4 or u[j]+v-2 in s:
                j+=1
            s.add(u[j]+v)
            u.append(u[j]+v)
            j+=1
    r+=m*d[n]+u[-1]
    print n,r
print r