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

Если открывать математическую книжку по теории чисел где-то в середине то часто первая мысль будет «да что должно было быть у человека в голове чтобы придумал такую теорему?» Ну ладно, на самом деле первая будет "что это за закорючки, это что, эльфийский?" Но второй точно про теоремы! Это конечно восхительное ощущение, потому что часто в контексте необходимость такой теоремы выглядит логично, и дальше это можно развернуть в детектив чтобы понять, где же просчитался садовник.

На днях (я ниже расскажу как так вышло) я так наткнулся на теорему Цекендорфа, которая говорит что любое натуральное число можно единственным образом представить в виде суммы одного или нескольких различных чисел Фибоначчи. Причём, если они различные то они не соседи в последовательности. Доказательства обоих частей теоремы в традиционном современном подходе изложения доказательств как обычно вызывает у меня кучу вопросов, поэтому давайте лучше поговорим о последствиях/приминениях.

Как всегда, бог в деталях, дьявол в мелочах:
©️ Из такого условия наши натуральные ℕ — без нуля
Если бы мы учитывали ноль, пришлось бы брать отрицательную одинаковую пару. С одной стороны, лягушатники идут опять нафиг, с другой вообще говоря последовательность Фибоначчи принято начинать с нуля, merde! Ладно. Хотя ноль писать будет всё время тупо. Поэтому с нуля, французы всё равно идут нафиг. А вот кстати, обобщение последовательности Фибоначчи на отрицательные числа называется негафиобначчивыми числами 🤭 Но я отвлёкся, désolé!

©️ **Единственность означает что есть однозначный перевод из **"Фибоначчевого мира" в "Мир натуральных чисел".
Тут должна фонить мысль кому это может быть надо, и это правильно, потому что надо начать думать когда это нам вдруг может понадобиться одно число представить комбинацией коэффициентов.

©️ То что разложение не на соседей — сайд эффект
Я сначала не понял, а потом понял, что это вообще не часть теоремы а так, добавка. В последовательности фибоначи если мы попали так что нам надо два соседа мы можем просто взять следующее число потому что оно будет суммой предыдущих двух, тадааа 🎉. Короче это скорее прикольное наблюдение будто бы. Это скорее что-то говорит нам про компактность такой записи.

Ну тут в общем, самый главный пункт — в середине. Когда нам нужно разложить число на коэффициенты вида "брать или не брать"? В бинарной системе счисления:
839 =
512 + 256 + 64 + 4 + 2 + 1 =
0y1101000111

Там где 1 там "эту степень двойки берём", там где нолик "эту степень не берём", получается сумма с коэффициентами.

КОРОЧЕ, кто нам запрещает взять вместо степеней двойки числа Фибоначчи? Правильно, никто. Но получается штука, которая ломает мозг.

В бинарной системе счисления 0y0101 + 0y1001 = 0y1110, типа просты понятные правила перепрыгивания чисел из одного разряда в другой, соседний чаще всего: 0y01 + 0y01 даст нам 0y10, всё компактно и рядом. А в Фибоначчиевой системе счисления, как вы понимает, нихрена подобного!

Вот, допустим, число 7. В Фибоначчиевой системе счисления это будет 7 = 5 + 2, запишем как 0ф1010. Добавляем единицу:
0ф1010 + 0ф0001 это 7+1 , но это 8, а значит это шестое число последовательности фибоначи и получается:
0ф1010 + 0ф0001 = 0ф10000. Ничёси!

Справдливости ради, в бинарной 7+1 тоже становится новым разрядом:
0y111 + 0y001 = 0y1000
но там всё понятно и привычно! А тут — нет! :D Непривычно. Понятно, но непривычно.

А раз непривычно, можно задуматься "а почему мы делаем так", поискать какие-то ещё приколы и внезапно вытащить ещё пару теорем и следствий понимания мира. А зачем? Да просто потому что прикольно, тут уже причин не надо

А, да, как так вышло-то? Ну я читал про кошек, потом про Майя и инков, а оказалось что все подозревают что их абаки использовали эту систему счисления — в ней получается как можно меньше нужно "единичек", компактно-удобно-красиво. Молодцы, чо