Project Euler 297

发表于 更新于 分类于 阅读次数： 本文字数： 1.1k 阅读时长 ≈ 1 分钟

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-1)$.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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)