Пересчет между Цекендорфом и Базой Золотого сечения

Question

Zeckendorf и Golden Ratio Base явно тесно связаны, но все же сложно перевести их с одного на другой.Я знаю, что есть работы Фруни и Сакаровича по этому вопросу, но я не до конца это понял.Одна из проблем заключается в том, что представления с базисом золотого сечения довольно симметричны вокруг радиуса, что говорит о том, что эти представления могут быть свободными от контекста.Сакарович и Фроньи справляются с этим, используя «свернутые» номера базы золотого сечения.С этим измененным представлением они могут предположительно выполнять преобразование с помощью датчика конечного состояния, но я не понял, как это должно работать.

Что касается частичной симметрии основания Золотого сечения, это связано с корнями, приходящими парами (у меня есть более длинное объяснение этого у Джорджа Бергмана (шт.)).

Одна вещь, которую я действительно знаю об отношении между этими двумя представлениями, состоит в том, что для каждого базового представления Золотого сечения формы 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).Это действительно выглядит так, как будто это должно быть полезно, но как?

Эта модель обсуждается в работе Д. Гердеманна, Комбинаторные доказательства идентичностей в семействе Цекендорфа Fibonacci Quarterly, 2008/2009.

Кстати: несмотря на то, что у меня есть газета в Фибоначчи, я строго любитель в этой области.В моих знаниях много пробелов, включая тот, о котором я спрашиваю.

Answer 1

Я знаю, что этот ответ опоздал на вечеринку на 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 поэтому для каждого номера Лукаса будут установлены 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). Это означает, что в базовой фи 5 не является простым, но sqrt(5) - это (технически это примитивный простой идеал). sqrt(5) ведет себя очень целочисленным образом. Фактически, любое число, конечно представимое в базовой фи, называется целым числом Дирихле из-за его целочисленного поведения.

Я нашел вышеупомянутые формулы на этой веб-странице , которая содержит больше информации о связи между числами Фибоначчи, числами Лукаса и phi.

Итак, вот моя попытка алгоритма. Я прошу сообщество помочь мне определить и исправить любые ошибки. Я предполагаю, что представления Zeckendorf и base 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);

Методы стандартизации до минимальной формы описаны в статье в википедии для золотое сечение , и деление может быть выполнено с использованием алгоритма евклидова деления .

Еще лучшим подходом может быть использование Сбалансированной троичной системы Тау , чтобы свойство «довольно симметрично относительно радиуса» стало свойством «полностью симметрично относительно 0-й цифры» (так называемое зеркальное симметричное свойство) , Документ, описывающий его, - « троичный принцип Броусенцова, система счисления Бергмана и троичная зеркально-симметричная арифметика » Алексея Стахова.