Система числення Фібоначчі — змішана система числення для цілих чисел на основі чисел Фібоначчі , , , , і т. д. Число Запис у код Фібоначчі 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

Подання натуральних чисел Будь-яке невід'ємне ціле число можна єдиним чином подати послідовністю бітів () так що , причому послідовність містить лише скінченне число одиниць, і не має пар сусідніх одиниць: . За винятком останньої властивості, дане подання аналогічне двійковій системі числення.

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

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

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

Юпана

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

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

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

ε2ε3…εn1,

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

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

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

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

Узагальнення на дійсні числа Число Подання через степінь 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 Схоже влаштована позиційна система числення з ірраціональною основою, рівною золотому перерізу .

Будь-яке дійсне число з відрізка допускає розкладання в ряд через від'ємні степені золотого перерізу:

де має ту ж властивість відсутності сусідніх одиниць. Коефіцієнти знаходяться послідовним порівнянням з  — золотим перерізом відрізка , відніманням (якщо ) і множенням на . З цього неважко бачити, що будь-яке невід'ємне дійсне число допускає розкладання:

де таке, що . Зрозуміло, слід вважати, що для всіх .

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

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

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

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

Множення Фібоначчі Для цілих чисел і можна визначити «множення», Теорема Цекендорфа

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

Зрозуміло, що дана операція не є справжнім множенням чисел, і виражається формулою:Notes on the Fibonacci circle and arroba products

де  — ціла частина,  — золотий переріз.

Ця операція має асоціативність, що вперше зауважив Дональд Кнут. Слід зазначити, що інше «множення» відрізняється лише зсувом на два розряди, вже не є асоціативним.

Примітки

Література