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

---

Фибоначчиева система счисления — смешанная система счисления для целых чисел на основе чисел Фибоначчи F₂=1, F₃=2, F₄=3, F₅=5, F₆=8 и т. д.

Любое неотрицательное целое число ${\displaystyle a}$ можно единственным образом представить последовательностью битов …ε_k…ε₄ε₃ε₂ (${\displaystyle \varepsilon _{k}\in \{0,1\}}$) так, что ${\displaystyle a=\sum _{k}\varepsilon _{k}F_{k}}$, причём последовательность {ε_k} содержит лишь конечное число единиц, и не имеет пар соседних единиц: ${\displaystyle \forall k\geq 2\colon (\varepsilon _{k}=1)\Rightarrow (\varepsilon _{k+1}=0)}$. За исключением последнего свойства, данное представление аналогично двоичной системе счисления.

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

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

Предполагают, что некоторые разновидности юпаны (абака инков) использовали фибоначчиеву систему счисления, чтобы минимизировать необходимое для вычислений число зёрен^[2].

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

---