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

Будь-яке невід'ємне ціле число ${\displaystyle a}$ можна єдиним чином подати послідовністю бітів ${\displaystyle \dots \varepsilon _{k}\dots \varepsilon _{4}\varepsilon _{3}\varepsilon _{2}}$ (${\displaystyle \varepsilon _{k}\in \{0,1\}}$) так що ${\displaystyle a=\sum _{k}\varepsilon _{k}F_{k}}$, причому послідовність ${\displaystyle \{\varepsilon _{k}\}}$ містить лише скінченне число одиниць, і не має пар сусідніх одиниць: ${\displaystyle \forall k\geq 2:(\varepsilon _{k}=1)\Rightarrow (\varepsilon _{k+1}=0)}$. За винятком останньої властивості, дане подання аналогічне двійковій системі числення .

Юпана

Юпана

Припускають, що деякі різновиди юпани (абака інків) використовували систему числення Фібоначчі, щоб мінімізувати необхідне для обчислень число зерен[2].

Число	Подання через степінь  ${\displaystyle \varphi }$
1	1
2	10,01
3	100,01
4	101,01
5	1000,1001
6	1010,0001
7	10000,0001
8	10001,0001
9	10010,0101
10	10100,0101
11	10101,0101
12	100000,101001
13	100010,001001
14	100100,001001

Схоже влаштована позиційна система числення з ірраціональною основою, рівною золотому перетину ${\displaystyle \varphi =(1+{\sqrt {5}})/2}$.

Будь-яке дійсне число ${\displaystyle x}$ з відрізка ${\displaystyle [0,1]}$ допускає розкладання в ряд через від'ємні степені золотого перетину:

${\displaystyle x=\sum _{k=-1}^{-\infty }\varepsilon _{k}\varphi ^{k},\qquad \varepsilon _{k}\in \{0,1\}}$

де ${\displaystyle \left\{\varepsilon _{k}\right\}}$ має ту ж властивість відсутності сусідніх одиниць. Коефіцієнти знаходяться послідовним порівнянням ${\displaystyle x}$ з ${\displaystyle \varphi ^{-1}}$ — золотим перетином відрізка ${\displaystyle [0,1]}$, відніманням ${\displaystyle \varphi ^{-1}}$ (якщо ${\displaystyle \varepsilon _{k}=1}$) і множенням на ${\displaystyle \varphi }$. З цього неважко бачити, що будь-яке невід'ємне дійсне число допускає розкладання:

${\displaystyle a=\sum _{k=N-1}^{-\infty }\varepsilon _{k}\varphi ^{k}\,,}$

де N таке, що ${\displaystyle a<\varphi ^{N}}$. Зрозуміло, слід вважати, що ${\displaystyle \varepsilon _{k}=0}$ для всіх ${\displaystyle k\geqslant N}$.

Ці формули повністю аналогічні формулам для звичайних позиційних систем з цілими основами. Виявляється, що будь-яке невід'ємне ціле число (і, більш загально, кожен невід'ємний елемент кільця ${\displaystyle {\mathbb {Z} }+\varphi {\mathbb {Z} }}$) має подання лише зі скінченною кількістю одиниць, тобто у вигляді скінченної суми неповторюваних степенів золотого перетину.[3]

Аналогія між числами Фібоначчі і степенями золотого перетину заснована на однаковій формі тотожностей:

${\displaystyle F_{k}=F_{k-1}+F_{k-2}}$

${\displaystyle \varphi ^{k}=\varphi ^{k-1}+\varphi ^{k-2}}$

які дозволяють усунення сусідніх одиниць. Прямого зв'язку між поданням натуральних чисел в системі золотого перетину і в системі Фібоначчі немає.

Правила додавання аналогічні показаним вище з тією поправкою, що перенесення в бік молодших розрядів поширюється без обмеження. У даній системі числення можна виконувати й множення.

Для цілих чисел ${\displaystyle a=\sum _{k}\varepsilon _{k}F_{k}\ }$ і ${\displaystyle b=\sum _{l}\zeta _{l}F_{l}\ }$ можна визначити «множення»[4]

${\displaystyle a\circ b=\sum _{k,l}\varepsilon _{k}\zeta _{l}F_{k+l},}$

аналогічне множенню чисел у двійковій системі числення.

Зрозуміло, що дана операція не є справжнім множенням чисел, і виражається формулою:[5]

${\displaystyle a\circ b=3ab-a\lfloor (b+1)\varphi ^{-2}\rfloor -b\lfloor (a+1)\varphi ^{-2}\rfloor ,}$

де ${\displaystyle \lfloor \cdot \rfloor }$ — ціла частина, ${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}$ — золотий перетин .

Ця операція має асоціативність, що вперше зауважив Дональд Кнут[6]. Слід зазначити, що інше «множення» ${\displaystyle \sum _{k,l}\varepsilon _{k}\zeta _{l}F_{k+l-2},}$ відрізняється лише зсувом на два розряди, вже не є асоціативним.

• Воробьёв Н. Н. Числа Фибоначчи. — Наука, 1978. — Т. 39. — (Популярные лекции по математике)(рос.)

• Система счисления Фибоначчи, реализация на C++. — 2014. Архівовано з джерела 16 жовтня 2014.(рос.)