Считать с запретами
Пусть aₙ — число двоичных строк длины n, в которых нет двух соседних единиц.
Если первая цифра 0, дальше можно поставить любую допустимую строку длины n−1.
Если первая цифра 1, следующая обязана быть нулём, и остаётся строка длины n−2.
Поэтому aₙ = aₙ₋₁ + aₙ₋₂.
Получаем последовательность
2, 3, 5, 8, 13, …,
то есть числа Фибоначчи со сдвигом: aₙ = Fₙ₊₂.
Но здесь можно пойти в обратную сторону.
Возьмём числа Фибоначчи 1, 2, 3, 5, 8, 13, 21, … (одну из двух начальных единиц опускаем) и будем записывать число нулями и единицами: единица означает, что соответствующее число Фибоначчи входит в сумму. Запретим только соседние единицы.
Например, 11 = 8 + 3. Числа 8 и 3 не соседствуют в последовательности
1, 2, 3, 5, 8, 13, ….
Оказывается, каждое положительное целое число имеет ровно одно представление как сумма несоседних чисел Фибоначчи.
Это теорема Цекендорфа.
Например,
2026 = 1597 + 377 + 34 + 13 + 5.
Причём такую запись можно находить жадно: каждый раз брать наибольшее число Фибоначчи, не превосходящее остатка. Теорема гарантирует, что результат будет единственным.
Получается необычная система записи: веса разрядов уже не являются степенями основания, зато сама структура запрещённых сочетаний обеспечивает однозначность.
Пусть aₙ — число двоичных строк длины n, в которых нет двух соседних единиц.
Если первая цифра 0, дальше можно поставить любую допустимую строку длины n−1.
Если первая цифра 1, следующая обязана быть нулём, и остаётся строка длины n−2.
Поэтому aₙ = aₙ₋₁ + aₙ₋₂.
Получаем последовательность
2, 3, 5, 8, 13, …,
то есть числа Фибоначчи со сдвигом: aₙ = Fₙ₊₂.
Но здесь можно пойти в обратную сторону.
Возьмём числа Фибоначчи 1, 2, 3, 5, 8, 13, 21, … (одну из двух начальных единиц опускаем) и будем записывать число нулями и единицами: единица означает, что соответствующее число Фибоначчи входит в сумму. Запретим только соседние единицы.
Например, 11 = 8 + 3. Числа 8 и 3 не соседствуют в последовательности
1, 2, 3, 5, 8, 13, ….
Оказывается, каждое положительное целое число имеет ровно одно представление как сумма несоседних чисел Фибоначчи.
Это теорема Цекендорфа.
Например,
2026 = 1597 + 377 + 34 + 13 + 5.
Причём такую запись можно находить жадно: каждый раз брать наибольшее число Фибоначчи, не превосходящее остатка. Теорема гарантирует, что результат будет единственным.
Получается необычная система записи: веса разрядов уже не являются степенями основания, зато сама структура запрещённых сочетаний обеспечивает однозначность.