记$f(x)=\sum_{n=1}^{x}z(n)$，$g(x)$为不超过$x$的最大斐波那契数。
显然，要表示$1$到$g(x)-1$之间的数无需用到$g(x)$，而$g(x)$到$x$之间的每个数减去$g(x)$后就又转化了前者的情形，因此有递推公式
$$f(x)=f(g(x)-1)+f(x-g(x))+x-g(x)+1,$$
以及初值$f(0)=0$，递推计算即得结果$2252639041804718029$。
import bisect
from functools import *
n=10**17-1
a=[1,2]
while a[-1]<=n:
a.append(a[-1]+a[-2])
s=set(a)
g=lambda x:0 if x<=0 else a[bisect.bisect(a,x)-1]
@cache
def f(x):
if x==0:
return 0
else:
return f(g(x)-1)+f(x-g(x))+x-g(x)+1
print(f(n))
|
