3

Zeckendorf と Golden Ratio Base は明らかに密接に関連していますが、それでも一方から他方へ変換するのは難しいようです。これについて Frougny と Sakarovitch による研究があることは知っていますが、私はこれを完全には理解していません。1 つの問題は、黄金比の基本表現が基数点を中心にかなり対称的であることです。これは、これらの表現がコンテキストフリーである可能性があることを示唆しています。Sakarovitch と Frougny は、「折り畳まれた」黄金比基数を使用してこれに対処しています。この修正された表現を使用すると、有限状態変換器で変換できると思われますが、これがどのように機能するかはわかりませんでした。

黄金比ベースの部分的な対称性に関しては、これは根が対になっていることに関係しています (これについては、George Bergman (pc) からの長い説明があります)。

これら 2 つの表現の関係について私が知っていることの 1 つは、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 著 Combinatorialproofs of Zeckendorf family identities Fibonacci Quarterly、2008/2009 で説明されています。

ところで: Fibonacci Quarterly に論文を書いているにもかかわらず、私はこの分野ではまったくの素人です。私が質問しているギャップを含め、私の知識には多くのギャップがあります。

4

1 に答える 1

6

この回答はパーティーに1.75年遅れていることは知っていますが、誰も回答を試みておらず、フィボナッチ数、ゼッケンドルフ表現、黄金比ベースの関係を自分で調べていたので、先に進んで投稿します。私は関連する研究で見つけました、そして答えで私の最高の刺し傷：

これからは、簡潔にするために黄金比ベースをベースファイまたはファイナリーと呼びます。

ベースファイは、フィボナッチ数よりもリュカ数と強く結びついています。これは、それらを直接変換する際に苦労したことのいくつかを説明しています。しかし、リュカ数は次のようにフィボナッチ数に関連しています。

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

と

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

リュカ数は次のようにベースファイに関連しています。

L[n] = phi^n + (-1/phi)^nしたがって、ベースphiのn番目と-n番目の桁は、各リュカ数に設定されます。

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整数と呼ばれます。

このWebページで、フィボナッチ数、リュカ数、およびファイの関係に関する詳細情報が記載された上記の式を見つけました。

これが私のアルゴリズムの試みです。間違いを見つけて修正するのを手伝ってくれるようコミュニティにお願いします。ゼッケンドルフとベースファイの表現は、ゼッケンドルフ配列が0からn、フィナリー配列が-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の三元原理、Bergmanの記数法および三元鏡対称算術」です。

于 2013-02-20T19:10:47.563 に答える