令p(n)为将n写成素数和的方式总数，a(n)为n的素因子之和，并规定初值$p(0)=1$, $p(1)=a(0)=a(1)=0$，则根据OEIS A000607，p(n)可由以下方式递推计算:
$$p(n)=\sum_{k=1}^na(k)p(n-k),$$
尝试猜测一个上界（此处用的是100），用筛法生成该范围内的a(n)后易得结果是$n=71$，此时$p(n)=5007$。
target=100
d=[[2] if i%2==0 else [] for i in range(target)]
n=3
while n < target:
for i in range(n,target,n):
d[i].append(n)
n+=1
while n < target and len(d[n])>0:
n+=1
a=[0,0]
p=[1,0]
n=1
while n < target and p[n]<=5000:
n+=1
a.append(sum(d[n]))
p.append(sum(a[k]*p[n-k] for k in range(1,n+1))/n)
print n,p[n]
|
