344
правки
Изменения
Нет описания правки
Целое число ''x'' в ''b''-ичной системе счисления представляется в виде конечной линейной комбинации степеней числа ''b'':
: <tex>x = \sum_{k=0}^{n-1} a_k b^k</tex>, где <tex>a_k</tex> — это целые числа, называемые '''цифрами''', удовлетворяющие неравенству <tex>0 \leq leqslant a_k \leq leqslant (b-1)</tex>.
Каждая степень <tex>b^k</tex> в такой записи называется весовым коэффициентом разряда. Старшинство разрядов и соответствующих им цифр определяется значением показателя <tex>k</tex> (номером разряда). Обычно для ненулевого числа <tex>x</tex> требуют, чтобы старшая цифра <tex>a_{n-1}</tex> в ''b''-ичном представлении <tex>x</tex> была также ненулевой.
: <tex>x = \sum_{k=0}^n f_k F_k</tex>, где <tex>F_k</tex> — числа Фибоначчи, <tex>f_k\in\{0,1\}</tex>, при этом в записи <tex>f_nf_{n-1}\ldots f_0</tex> не встречается две единицы подряд.
Таким образом, любое неотрицательное целое число <tex>a = 0,\ 1,\ 2,\ldots </tex> можно единственным образом представить через последовательность битов …ε<sub>k</sub>…ε<sub>4</sub>ε<sub>3</sub>ε<sub>2</sub>: <tex>a = \sum_k \varepsilon_k F_k,\ \varepsilon_k\in\{0,1\}</tex>, причём последовательность {ε<sub>k</sub>} содержит лишь конечное число единиц, и не имеет пар соседних единиц: <tex>\forall k \ge geqslant 2: (\varepsilon_k=1) \Rightarrow (\varepsilon_{k+1}=0)</tex>.
За исключением последнего свойства, данное представление аналогично двоичной системе счисления.
Любое неотрицательное целое число представимо в виде суммы некоторого набора чисел Фибоначчи, не содержащего пары соседних чисел Фибоначчи. Причём представление такое единственно.
|proof=
Доказательство существования легко провести по индукции. Любое целое число <tex>a \ge geqslant 1</tex> попадёт в промежуток между двумя соседними числами Фибоначчи, то есть для некоторого <tex>n\ge geqslant 2</tex> верно неравенство: <tex>F_n \le leqslant a < F_{n+1}</tex>. Таким образом, <tex>a = F_n + a'</tex>, где <tex>a'=a-F_n\ <\ F_{n-1}</tex>, так что разложение числа <tex>a'</tex> уже не будет содержать слагаемого <tex>F_{n-1}</tex>.
}}
