初看本题很容易联想到此前（比如第297题）出现过的Zeckendorf表示，从而被误导到需要找出两者的关系，不过实际解法直接得多。
首先注意到除$1$以外其他数的表示都不可避免地要用到$\varphi$的负幂，所以先考虑$\varphi$进制下$10\ldots0.0\ldots01$形式的回文数，亦即$\varphi^n+\varphi^{-n-1}$形式的数，它可以写成$p_k=F_{2k}+F_{2k+6}$，其中$F_k$是以$F_0=F_1=1$为起始项的斐波那契数列。
用$p_k$加上此前已生成过的、不超过$p_{k-2}$（不能出现相邻的幂）的回文数即可递归生成所有满足要求的回文数，最终结果是$35856681704365$。
N=10**10
res=[2,14]
a,b,c=6,14,36
while c<=N:
res.append(c)
for p in res:
if p>=a or p+c>N:
break
res.append(p+c)
a,b,c=b,c,3*c-b
print(1+sum(res))
|
