0167 乌拉姆序列
* * * *
拉格朗日计划
* * * *
乌拉姆序列

任取两个正整数a和b,乌拉姆序列U(a,b)按如下方式定义:U(a,b)1=aU(a,b)2=b,对k>2U(a,b)k是比U(a,b)k1大,且能用U(a,b)1U(a,b)k1之间的不同两项之和所唯一表示的最小整数。

例如U(1,2)的前几项如下: 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, 其中由于 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, 都不是唯一表示,因此跳过了这些数字。

求出下式的值: n=210U(2,2n+1)1011.
本题难度:



解答

根据该论文的结论,形如U(2,2n+1) (n1)的乌拉姆序列中只有两项是偶数,分别是 U(2,2n+1)1=2,U(2,2n+1)n+4=4n+4, 且对充分大的k有具有如下的周期性: U(2,2n+1)k+Tn=U(2,2n+1)k+Dn. Tn的值在OEIS A100729中给出,Dn的值在OEIS A100730中给出。

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

仍需要生成至少一个周期内的项来计算第1011项。

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

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

显然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