Введение

О уникальном представлении целых чисел в виде сумм не соседних чисел Фибоначчи

В математике теорема Зекендорфа, названная в честь бельгийского математика-любителя Эдуарда Зекендорфа, – это теорема о представлении целых чисел в виде сумм чисел Фибоначчи. Теорема Зекендорфа утверждает, что любое положительное целое число может быть представлено единственным образом как сумма одного или нескольких различных чисел Фибоначчи, при этом сумма не должна включать два соседних числа Фибоначчи. Более точно, для любого положительного целого числа N существуют положительные целые числа ci ≥ 2, такие что ci+1 > ci + 1, и

где Fn – n-е число Фибоначчи. Такая сумма называется представлением Зекендорфа числа N. Фибоначчиево кодирование числа N может быть получено из его представления Зекендорфа. Например, представление Зекендорфа числа 64 равно 64 = 55 + 8 + 1. Существуют другие способы представления 64 в виде суммы чисел Фибоначчи, например:

64 = 55 + 5 + 3 + 1
64 = 34 + 21 + 8 + 1
64 = 34 + 21 + 5 + 3 + 1
64 = 34 + 13 + 8 + 5 + 3 + 1

но эти представления не являются представлениями Зекендорфа, поскольку 34 и 21 – соседние числа Фибоначчи, как и 5 и 3. Для любого заданного положительного целого числа его представление Зекендорфа можно найти с помощью жадного алгоритма, выбирая на каждом шаге наибольшее возможное число Фибоначчи.

История

Хотя теорема названа в честь автора, чья статья была опубликована в 1972 году, тот же результат был опубликован на 20 лет раньше Герритом Леккеркеркером. Следовательно, теорема представляет собой пример закона Стиглера об эпонимии.