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

Система числення Фібоначчі — змішана система числення для цілих чисел на основі чисел Фібоначчі $F_{2}=1$, $F_{3}=2$, $F_{4}=3$, $F_{5}=5$, $F_{6}=8$ і т. д.

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

Обґрунтування

В основі лежить теорема Цекендорфа: будь-яке невід'ємне ціле число можна єдиним чином подати у вигляді суми деякого набору чисел Фібоначчі з індексами більшими від одиниці, який не містить пар сусідніх чисел Фібоначчі.

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

Використання

Юпана

Юпана

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

У теорії інформації

На основі системи числення Фібоначчі будується код (кодування) Фібоначчі — універсальний код для натуральних чисел (1,   2,   3 …), який використовує послідовності бітів. Оскільки комбінація   11 заборонена в системі числення Фібоначчі, її можна використовувати як маркер кінця запису.

Для складання коду Фібоначчі за записом числа в системі числення Фібоначчі слід переписати цифри у зворотному порядку (так, що старша одиниця виявляється останнім символом) і приписати в кінці ще раз   1 (див. таблицю). Тобто, кодова послідовність має вигляд:

ε₂ε₃…ε_n1,

де n — номер найстаршого розряду з одиницею.

Арифметика

Додавання чисел у позиційних системах числення виконується з використанням переносу, що дозволяє усувати наслідки переповнення розряду. Наприклад, у двійковій системі: 01 + 01 = 02 = 10.

У системі числення Фібоначчі ситуація складніша:

• По-перше, вага старших розрядів не є кратною вазі розряду, з якого виконується перенесення. При додаванні двох одиниць в одному розряді потрібне перенесення не тільки вліво, але й управо: 0200 = 1001. При перенесенні у відсутні розряди ε₁ і ε₀ слід пам'ятати, що F₁=1=F₂ і F₀=0.
• По-друге, потрібно позбавлятися від сусідніх одиниць: 011 = 100. Правило для розкриття двійок є наслідком цієї рівності: 0200 = 0100 + 0011 = 0111 = 1001.

Узагальнення на дійсні числа

Число	Подання через степінь  $\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

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

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

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

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

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

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

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

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

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

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

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

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

Множення Фібоначчі

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

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

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

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

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

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

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

Література

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

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