Project Euler 297

题目

Zeckendorf Representation

Each new term in the Fibonacci sequence is generated by adding the previous two terms.

Starting with $1$ and $2$, the first $10$ terms will be: $1,2,3,5,8,13,21,34,55,89$.

Every positive integer can be uniquely written as a sum of nonconsecutive terms of the Fibonacci sequence. For example, $100=3+8+89$.

Such a sum is called the Zeckendorf representation of the number.

For any integer $n>0$, let $z(n)$ be the number of terms in the Zeckendorf representation of $n$.

Thus, $z(5)=1,z(14)=2,z(100)=3$ etc.

Also, for $0<n<{10}^6,\sum z(n)=7894453$.

Find $\sum z(n)$ for $0<n<{10}^{17}$.

齐肯多夫定理

齐肯多夫定理，任何一个数 $n$，都可以表示成多个不相邻斐波那契数之和，并且这种表示方法是唯一的。

解决方案

令 $N={10}^{17},f(n)=\sum _{i=1}^z(i).$

对于一个数 $n$ 求它的齐肯多夫表示法，不难想到使用贪心的方法：从大到小枚举斐波那契数 $m$，如果 $m$ 不超过 $n$，那么记录下 $m$，并从 $n$ 减去 $m$，否则跳过，直到 $n$ 变成 $0$.

当我们计算 $f(n)$ 时，记 $g(n)$ 为不超过 $n$ 的最大斐波那契数。在 $1\sim n$ 这一部分数中，不难发现，$1\sim g(n)-1$ 这一部分永远不会用到 $g(n)$ 来表示。而 $g(n)\sim n$ 中的所有数都会用到 $g(n)$ 表示，而将这一部分数都用 $g(n)$ 表示后，接下来就以同样的思想考虑 $0\sim n-g(n)$ 这一部分，也就是 $f(n-g(n))$。

那么，不难写出 $f(n)$ 的递推式：

$$f(n)=\{\begin{array}{rlrl}& 0& & \text{if}n=0\\ & f(g(n)-1)+f(n-g(n))+n-g(n)+1& & \text{else}\end{array}$$

使用记忆化的递归可以快速求出 $f(N-1)$.

代码

N = 10 ** 17
N -= 1
f = [1, 2]
mp = {0: 0}
while True:
    f.append(f[-1] + f[-2])
    if f[-1] > N:
        break


def dfs(n: int):
    if n in mp.keys():
        return mp[n]
    p = 0
    while p + 1 < len(f) and f[p + 1] <= n:
        p += 1
    ans = dfs(f[p] - 1) + dfs(n - f[p]) + n - f[p] + 1
    mp[n] = ans
    return ans


ans = dfs(N)
print(ans)