Dal*_*ann 3 base-conversion fibonacci
Zeckendorf和黄金比率基数显然密切相关,但从一个转换到另一个似乎仍然很棘手.我知道Frougny和Sakarovitch有关于此的工作,但我还没有完全理解这一点.一个问题是黄金比率基数表示在小数点附近相当对称,这表明这些表示可以是无上下文的.Sakarovitch和Frougny通过使用"折叠"黄金比率基数来处理这个问题.通过这种修改过的表示,他们可以假设使用有限状态传感器进行转换,但我没有意识到这应该如何工作.
至于黄金比率基础的部分对称性,这与成对的根有关(我对乔治·伯格曼(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家族身份的组合证明,Fibonacci Quarterly,2008/2009中进行了讨论.
顺便说一句:尽管在斐波那契季刊中有一篇论文,但我在这方面绝对是业余爱好者.我的知识存在很多差距,包括我所询问的差距.
我知道这个答案是晚了1.75年,但是由于没有其他人试图回答它,我正在探索斐波那契数字,Zeckendorf表示和黄金比率基础之间的联系,我会继续发布我的内容已经在相关研究中发现了我最好的答案:
从现在开始,为了简洁,我将黄色比率基数称为基础phi或phinary.
基础phi与Lucas数字的关系比斐波那契数字更强,这解释了你直接转换它们时遇到的一些困难.但卢卡斯数与斐波纳契数相关:
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 因此,将为每个Lucas数设置基本phi中的第n和第n个数字.
根据F[n]phi的权力直接表示斐波纳契数是:
F[n] = ( phi^n - (-1/phi)^n )/sqrt(5) (注意减号而不是加号)
其中翻译为:
F[n] = ( 10^n - (-0.1)^n )/10.1
现在sprt(5)可以在pinary中直接表示为10.1,但如果整数的因子为5,它只会均匀地划分斐波纳契数,因为5和它的倍数是唯一的整数除法sqrt(5).这意味着,在基PHI,5不是素数,但sqrt(5) 是(在技术上它是一种原始素理想). sqrt(5)表现得像一个非常整数的方式.实际上,在基本phi中有限可表示的任何数字都称为Dirichlet Integer,因为它具有整数类行为.
我在这个网页上找到了上面的公式,其中有关于斐波那契数,卢卡斯数和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);
标准化为最小形式的方法记录在维基百科文章中,用于黄金比率基础,并且可以使用欧几里德分区算法来执行除法.
更好的方法可能是使用Balanced Ternary Tau系统,以便"围绕基数相当对称"属性变为"围绕第0个数字完全对称"属性(称为镜像对称属性).描述它的论文是由Alexey Stakhov 撰写的 " Brousentsov's三元原理,伯格曼数字系统和三元镜像对称算术 ".