fibonacci - Zeckendorf 和 Golden Ratio Base 之间的转换

Question

Zeckendorf 和 Golden Ratio Base 显然密切相关，但从一个转换为另一个似乎仍然很棘手。我知道 Frougny 和 Sakarovitch 在这方面有工作，但我还没有完全理解这一点。一个问题是黄金比例基础表示围绕小数点相当对称，这表明这些表示可能是上下文无关的。 Sakarovitch 和 Frougny 通过使用“折叠的”黄金比例基数来解决这个问题。有了这个修改后的表示，他们可以用有限状态传感器进行转换，但我不明白这应该如何工作。

至于黄金比例基数的部分对称性，这与成对出现的根有关(George Bergman (pc) 对此有更详细的解释)。

关于这两种表示之间的关系，我确实知道的一件事是，对于形式为 d-1...d_i*d_j...d_n(使用“*”作为小数点)的每个黄金比例基本表示，有是涉及斐波那契数列的相应方程:

Example 4 = 101.01 <=> 4f_n = f_{n+2} + f_n + f_{n-2}   (with f_0 = f_1 = 1
                                                          and f_n = f_{n-1} + f_{n-2})
For n=3,  f_n=3:  12 =   10101
for n=4,  f_n=5:  20 =  101010
for n=5   f_n=8:  32 = 1010100    

(等等。有一整串数字都具有与 4 的黄金比例基本表示相同的 Zeckendorf 位模式)。这看起来确实应该有所帮助，但如何呢？

D. Gerdemann 在 Zeckendorf family identities Fibonacci Quarterly，2008/2009 的组合证明中讨论了这种模式。

顺便说一句:尽管在 Fibonacci Quarterly 上有一篇论文，但我在这个领域绝对是个业余爱好者。我的知识有很多差距，包括我要问的差距。

Answer 1

我知道这个答案晚了 1.75 年，但由于没有其他人试图回答它，我正在探索斐波那契数、Zeckendorf 表示法和黄金比例之间的联系我自己，我会继续发布我在相关研究中的发现以及我的最佳答案:

从现在开始我会引用golden ratio base为简洁起见，作为基础 phi 或 phinary。

基础 phi 与 Lucas numbers 的联系更紧密比Fibonacci numbers ，这解释了您在直接转换它们时遇到的一些困难。但是卢卡斯数与斐波那契数的关系是:

L[n] = F[n-1] + F[n+1]

和

5 * F(n) = (L[n-1] + L[n+1])

卢卡斯数以这种方式与基本 phi 相关:

L[n] = phi^n + (-1/phi)^n 因此将为每个卢卡斯数设置基数 phi 中的第 n 和 -n 位数字。

根据 phi 的幂，斐波那契数 F[n] 的直接表示是:

F[n] = ( phi^n - (-1/phi)^n )/sqrt(5)(注意减号而不是加号)

将其翻译成:

F[n] = ( 10^n - (-0.1)^n )/10.1

现在 sprt(5) 在 phinary 中可以直接表示为 10.1，但如果整数中有 5 的因数，它只会整除斐波那契数，因为 5 及其倍数是只有整数 sqrt(5) 相除。这意味着在基数 phi 中，5 不是素数，但 sqrt(5) 是(从技术上讲，它是原始素数理想)。 sqrt(5) 的行为非常类似于整数。事实上，在基 phi 中可以有限表示的任何数字都称为 Dirichlet Integer。因为它的整数行为。

我在 this web page 上找到了以上公式其中包含有关斐波那契数、卢卡斯数和 phi 之间关系的更多信息。

这是我对算法的尝试。我请求社区帮助我发现并纠正任何错误。我假设 Zeckendorf 和基本 phi 表示存储在一个数组中，其中 Zeckendorf 数组从 0 到 n，Phinary 数组从 -n 到 n，我正在使用类似 C 的伪代码:

for (int n = 0; n < length(Zeckendorf); n++) {
    if (Zeckendorf[n] == 1) {
        Phinary[n] = 1;
        /* in a real array, the negative n needs to be offset like fixed point */
        Phinary[-n] = -1; /* negative phinary digits
        can be converted to positive ones later
        (see Golden Ratio Base article on wikipedia) */
    }
}
Standardize(Phinary); /* Change -1's to 1's with 0,-1,0 -> -1,0,1
negatives will eventually cancel with their positive 1 neighbors to the left. */
/* Divide by sqrt 5 = 10.1 in phinary */
Sqrt5[-1 .. 1] = {1, 0, 1}
PhinalNumber = PhiDivide(Phinary, Sqrt5);

标准化为最小形式的方法记录在维基百科文章中 golden ratio base可以使用 Euclidean Division algorithm 执行除法.

更好的方法可能是使用 Balanced Ternary Tau system这样“围绕基数相当对称”的属性就变成了“围绕第 0 个数字完全对称”的属性(称为镜像对称属性)。描述它的论文是 Alexey Stakhov 的“Brousentsov’s Ternary Principle, Bergman’s Number System and Ternary Mirror-symmetrical Arithmetic”。