0197 递归序列
* * * *
拉格朗日计划
* * * *
递归序列

设 $$f(x)=\lfloor 2^{30.403243784-x^2}\rfloor\cdot10^{-9},$$ 定义$u_0=-1$且$u_{n+1}=f(u_n)$。

求$u_{10^{12}}+u_{10^{12}+1}$,结果保留9位小数。

本题难度:



解答

显然出题人的意图不太可能是遍历$10^{12}+1$以内的所有数并一一计算,因此可以猜测$u_0$的轨道中或者有不动点,或者有循环节。

计算充分多的项后可以发现$u_{516}=u_{518}$,因此从$u_{516}$开始进入周期为$2$的循环,从而得结果 $$u_{10^{12}}+u_{10^{12}+1}=u_{516}+u_{517}=1.710637717.$$
f=lambda x:int(pow(2,30.403243784-x*x))*0.000000001
u=[]
s=set()
i,x=0,-1
while i < 1000 and x not in s:
    s.add(x)
    u.append(x)
    x=f(x)
    i+=1
if i < 1000:
    j=u.index(x)
    print i,j,sum(u[j:])