Project Euler 297

发表于 更新于 分类于 阅读次数： 本文字数： 1.2k 阅读时长 ≈ 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)= \left \{\begin{aligned} &0 & & \text{if}\quad n=0 \\ &f(g(n)-1)+f(n-g(n))+n-g(n)+1 & & \text{else} \end{aligned}\right. \]

使用记忆化的递归可以快速求出\(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)