О Фибоначчиевой системе счисления

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

Определение[1-4]
Рассмотрим последовательность u₀,u₁,u₂, ... , u_n,
     ∀n>1 u_n=u_n-1+u_n-2
     Предположим, что u₀=1, u₁=1
Полученная последовательность называется рядом Фибоначчи, а ее члены числами Фибоначчи. С числами Фибоначчи познакомились благодаря сочинению "Liber abacci" ("Книга об абаке"), написанным знаменитым итальянским математиком Леонардо из Пизы (1170-1250), известным более по прозвищу Фибоначчи (Fibonacci - сокращение от filius Bonacci - сын Боначчи). Важно обратить внимание на то, что последовательность Фибоначчи использовалась в Древней Индии задолго до того, как стала известна в Европе после изучения и описания ее Леонардо Пизанским Фибоначчи.

1. Сумма первых n+1 чисел
   u₀+u₁+u₂+ ... + u_n=u_n+2-u₁=u_n+2-1
2. Сумма чисел с нечетными номерами
   u₁+u₃+u₅+ ... + u_2n-1=u_2n
3. Сумма чисел с четными номерами
   u₀+u₂+u₄+ ... + u_2n=u_2n+1-1
4. Сумма квадратов n+1 чисел
   u₀²+u₁²+u₂²+ ... + u_n²=u_nu_n+1

Теорема Цекендорфа[2]
Любое неотрицательное целое число единственным образом представимо в виде суммы некоторого набора попарно различных чисел Фибоначчи с индексами, большими единицы, не содержащего пар соседних чисел Фибоначчи.
На основании теоремы Цекендорфа [2] Для ∀ натурального n ∃ единственное представление в фибоначчиевой системе счисления:
n=∑_ke_kF_k, где F_k - числа Фибоначчи, e_k∈{0,1}, причём последовательность {e_k} содержит конечное число знаков, а также не имеет пар соседних единиц: (*) ∀k>1:{e_k=1->e_k+1=0}. Таким образом за исключением свойства (*), система аналогична двоичной системе счисления. Алфавит системы - {0,1}, базисом является последовательность чисел Фибоначчи 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,... ( F₀=1 не входит в базис).
Для представления целого десятичного числа N в фибоначчиевой системе счисления используется циклический процесс, состоящий из следующих шагов:

1. Выбирается наибольший член последовательности Фибоначчи для числа N. Для N₁=N ∃k₁: F_k1≤ N₁ < F_k1+1
2. Для остатка N₂=N₁-F_k1 ∃k₂: F_k2≤ N₂ < F_k2+1
3. ...
   Для остатка N_n-1 ∃ k_n-1: F_kn-1≤ N_n-1  < F_kn-1+1
   Процесс продолжается до тех пор пока на n-ом шаге остаток N_n не станет равным нулю.
   И тогда в результате имеем убывающую последовательность чисел Фибоначчи {F_ki}₁^n-1: N=F_k1+F_k2+...+F_kn-1

Для перевода числа из фибоначчиевой в десятичную систему счисления следует просуммировать элементы последовательности Фибоначчи с ненулевыми индексами.

В упражнениях рассматриваются десятичные 64-разрядные числа. Для представления таких чисел в Фибоначчиевой системе счисления используются 91 первых члена ряда Фибоначчи. Результат представления десятичного числа по усмотрению пользователя может быть представлен в двоичной фибоначчиевой системе счисления, с помощью убывающей последовательности ненулевых индексов ряда Фибоначчи или с помощью убывающей последовательности значений разрядов в разложении десятичного числа в ряд Фибоначчи.

Литература

1. Н.Н. Воробьев Числа Фибоначчи. М. Главная редакция физико-математической литературы издательства "Наука". Серия: Популярные лекции по математике. Выпуск 6. 1978.
2. Википедия. Фибоначчиева система счисления
3. Фибоначчиева система счисления
4. Фибоначчиева система счисления