根据该论文的结论,形如 ()的乌拉姆序列中只有两项是偶数,分别是
且对充分大的k有具有如下的周期性:
的值在OEIS A100729中给出,的值在OEIS A100730中给出。
最小的、能满足上述周期性的k并未在上述文献中提及,不过观察时的序列(见OEIS A007300)以及时的序列(见OEIS A003668)可以猜测k从开始,最后的结果显示这至少对本题而言是正确。
仍需要生成至少一个周期内的项来计算第项。
首先注意到只有两项是偶数,因此除这两项以外,其它项显然只能由这两个偶数项(2或)之一加上另一个奇数项获得,从而容易看出前六项应当是
记,其它项可以用以下方式生成:
用哈希表和列表同时保存已生产的序列,假定当前项是,则只要不在已经生成的序列中,下一项就应该是,否则下一项应当具有的形式,其中b是已生成的项中第一个满足且不在已生成的序列中的项。
显然b是递增的,因此只需要从上一次的位置开始搜索即可。
结果是。
注:本题需要有较强的文献检索能力。
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
|