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

універсальний код

Система числення Фібоначчі — змішана система числення для цілих чисел на основі чисел Фібоначчі , , , , і т. д.

Число Запис

у СЧФ

код

Фібоначчі

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].

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

ред.

На основі системи числення Фібоначчі будується код (кодування) Фібоначчі — універсальний код[ru] для натуральних чисел (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

Схоже влаштована позиційна система числення з ірраціональною основою, рівною золотому перетину  .

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

 

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

 

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

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

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

 
 

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

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

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

ред.

Для цілих чисел   і   можна визначити «множення»[4]

 

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

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

 

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

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

Примітки

ред.
  1. Эдуард Цекендорф. Архів оригіналу за 6 травня 2017. Процитовано 15 грудня 2019.
  2. Antonio Aimi, Nicolino De Pasquale. Andean Calculators (PDF). Процитовано 12 грудня 2009.
  3. Система числення на основі золотого перетину[en]
  4. послідовність A101330 з Онлайн енциклопедії послідовностей цілих чисел, OEIS(англ.), Теорема Цекендорфа
  5. Notes on the Fibonacci circle and arroba products(англ.)
  6. D. E. Knuth.  // Applied Mathematics Letters. — 1988. — Т. 1, № 1. — С. 57—60. — DOI:10.1016/0893-9659(88)90176-0.

Література

ред.