Zeckendorf和黄金比例进制之间的转换

Question

Zeckendorf和黄金比例进制之间的转换

3

Zeckendorf数和黄金比例进位制显然密切相关，但似乎从一个转换到另一个很棘手。我知道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

（等等。有一整个数字系列，它们的Zeckendorf位模式与4的黄金比例基数表示相同）。这看起来确实很有帮助，但是应该怎么用呢？

这种模式在D. Gerdemann 的文章“组合证明 Zeckendorf 家族恒等式”中有讨论。

顺便说一句：尽管我曾在《斐波那契季刊》上发表过论文，但我在这个领域仅仅是一个业余爱好者。我的知识还有很多空白，包括我正在问的这个空白。

- Dale Gerdemann

请尝试访问http://math.stackexchange.com/。 - skaffman

很高兴了解StackExchange，但似乎对此没有帮助。毕竟，我正在寻找一种算法。 - Dale Gerdemann

在这种情况下，尝试使用http://cstheory.stackexchange.com/ :) - skaffman

再次感谢。在Zeckendorf方面也没有找到任何信息。但这个网站看起来很不错。所以在这里提问已经对我有所帮助了。 - Dale Gerdemann

编程算法在这里是相关主题。您正在寻找编程算法吗？ - user1228

是的，我不在寻找一个思维实验算法。 - Dale Gerdemann

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- hatch22 · Accepted Answer

我知道这个答案迟了1.75年，但由于没有其他人尝试回答，而我正在探索斐波那契数列、塞康多夫表示和黄金比例基数之间的联系，因此我将发布我在相关研究中发现的内容和最佳答案:

从现在开始，我将简称黄金比例基数为phi或phinary。

基于phi的紧密关系更强地与卢卡斯数相关，而不是与斐波那契数列相关，这解释了你在直接转换它们时遇到的一些困难。但是，卢卡斯数与斐波那契数列相关，具体来说是：

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 ，因此每个卢卡斯数的第n和-n位数字在phi基数下都会被设置。

一个斐波那契数的直接表示方法是：

F[n] = ( phi^n - (-1/phi)^n )/sqrt(5) (请注意，这里有一个负号而不是加号)

这在phinary（即基于黄金比例基数的二进制）中的表示为：

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

现在sprt(5)可以直接在phinary中表示为10.1，但仅当整数中有因子5时，它才能均匀地分割斐波那契数，因为5及其倍数是唯一被sprt(5)除尽的整数。这意味着，在phi基数下，5不是一个质数，但sprt(5)是（技术上它是原始质数理想）。 sprt(5)的行为方式非常类似于整数。实际上，在基于phi的数字有限性表示的任何数字都称为狄利克雷整数，因为它们的整数化行为。

我在这个网页上找到了上述公式，该网页提供有关斐波那契数列、卢卡斯数和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);

将数字标准化为最小形式的方法在维基百科文章黄金分割基数中有记录，可以使用欧几里得除法算法进行除法。

更好的方法可能是使用平衡三进制tau系统，使“相对于基数对称”的属性变成“围绕第0位完全对称”的属性（称为镜像对称属性）。描述该方法的论文是Alexey Stakhov撰写的《Brousentsov的三元原理、Bergman的编号系统和三元镜像对称算术》。