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

Фибоначчиева система счисления — способ представления целых чисел через числа Фибоначчи F_k.

Представление натуральных чисел

Число	Запись в ФСС	Код Фибоначчи
0	0……0
F2=1	1	11
F3=2	10	011
F4=3	100	0011
4	101	1011
F5=5	1000	00011
6	1001	10011
7	1010	01011
F6=8	10000	000011
…
Fn-1	101010…	…0101011
Fn	10……00	00……011
Fn+1	10……01	10……011

Любому неотрицательному целому числу $a = 0,\ 1,\ 2,\dots$ можно единственным образом представить через последовательность битов …σ_k…σ₄σ₃σ₂: $a = \sum_k \sigma_k F_k,\ \sigma_k = 0,1$, причём последовательность {σ_k} содержит лишь конечное число единиц, и не имеет пар соседних единиц: $\forall k\ge 2: (\sigma_k=1) \rightarrow (\sigma_{k+1}=0)$. За исключением последнего свойства, данное представление аналогично двоичной системе счисления.

Обоснование

В основе лежит теорема Цеккендорфа — любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно.

Доказательство существования легко провести по индукции. Любое целое число $a\ge 1$ попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого $n\ge 2$ верно неравенство: $F_n \le a < F_{n+1}$. Таким образом, $a = F_n + a'$, где $a'=a-F_n\$, так что разложение числа $a'$ уже не будет содержать слагаемого $F_{n-1}$.

Использование в теории информации

На основе фибоначчиевой системы счисления строится код (кодирование) Фибоначчи — универсальный код для натуральных чисел (1, 2, 3…), использующий последовательности битов. Поскольку комбинация 11 запрещена в Фибоначчиевой системы счисления, её можно использовать как маркер конца записи. Для составления кода Фибоначчи по записи числа в фибоначчиевой системе счисления следует переписать цифры в обратном порядке (так, что старшая единица оказывается последним символом) и приписать в конце ещё раз 1 (см. таблицу).

Фибоначчиево «произведение»

Для $a = \sum_k \sigma_k F_k$ и $b = \sum_l \tau_l F_l$ можно определить «произведение» $a\circ b = \sum_{k,l} \sigma_k \tau_l F_{k+l}$, формула для которого аналогична формуле умножения двоичных чисел.

Разумеется, данная операция не является настоящим умножением чисел, однако Дональд Кнут доказал её ассоциативность.

Обобщение на действительные числа

Похожее устройство имеет позиционная система счисления для действительных чисел, основанием которой служит золотое сечение $\phi = (1 + \sqrt{5})/2$ — иррациональное число.