Полная последовательность

В математике последовательность натуральных чисел называется полной последовательностью, если каждое положительное целое число можно выразить в виде суммы значений последовательности, используя каждое значение не более одного раза.

Например, последовательность степеней двойки (1, 2, 4, 8, ...), основа двоичной системы счисления , является полной последовательностью; для любого натурального числа мы можем выбрать значения, соответствующие битам 1 в его двоичном представлении, и сложить их, чтобы получить это число (например, 37 = 100101 ₂ = 1 + 4 + 32). Эта последовательность минимальна, поскольку из нее нельзя удалить ни одного значения, не сделав некоторые натуральные числа невозможными для представления. Простые примеры последовательностей, которые не являются полными, включают четные числа , поскольку сложение четных чисел дает только четные числа — нечетное число образоваться не может.

Без потери общности предположим, что последовательность a _n находится в неубывающем порядке, и определим частичные суммы a _n как:

${\displaystyle s_{n}=\sum _{m=0}^{n}a_{m}}$.

Тогда условия

${\displaystyle a_{0}=1\,}$

${\displaystyle s_{k-1}\geq a_{k}-1{\text{ для всех }}k\geq 1}$

являются как необходимыми, так и достаточными для того, _{чтобы n} было полной последовательностью. ^{[1] [2]}

Следствием вышесказанного является то, что

${\displaystyle a_{0}=1\,}$

${\displaystyle 2a_{k}\geq a_{k+1}{\text{ для всех }}k\geq 0}$

достаточны для того, _{чтобы n} было полной последовательностью. ^[1]

Однако существуют полные последовательности, которые не удовлетворяют этому следствию,например (последовательность A203074 в OEIS ), состоящая из числа 1 и первого простого числа после каждой степени числа 2.

Полные последовательности включают в себя:

• Последовательность числа 1, за которой следуют простые числа (изученная С.С. Пиллаи ^[3] и другими); это следует из постулата Бертрана . ^[1]
• Последовательность практических чисел , которая имеет 1 в качестве первого члена и содержит все остальные степени числа 2 в качестве подмножества. ^[4] (последовательность A005153 в OEIS )
• Числа Фибоначчи , а также числа Фибоначчи с удаленным одним числом. ^[1] Это следует из тождества, что сумма первых n чисел Фибоначчи равна ( n  + 2)-му числу Фибоначчи минус 1.

Так же, как степени двойки образуют полную последовательность благодаря двоичной системе счисления, фактически любая полная последовательность может быть использована для кодирования целых чисел в виде битовых строк. Самая правая позиция бита назначается первому, наименьшему члену последовательности; следующая справа — следующему члену; и так далее. Биты, установленные в 1, включаются в сумму. Эти представления могут быть не уникальными.

Например, в арифметической системе Фибоначчи , основанной на последовательности Фибоначчи, число 17 можно закодировать шестью различными способами:

 110111 (F ₆ + F ₅ + F ₃ + F ₂ + F ₁ = 8 + 5 + 2 + 1 + 1 = 17, максимальная форма)

 111001 (Ф ₆ + Ф ₅ + Ф ₄ + Ф ₁ = 8 + 5 + 3 + 1 = 17)

 111010 (Ф ₆ + Ф ₅ + Ф ₄ + Ф ₂ = 8 + 5 + 3 + 1 = 17)

1000111 (Ф ₇ + Ф ₃ + Ф ₂ + Ф ₁ = 13 + 2 + 1 + 1 = 17)

1001001 (Ф ₇ + Ф ₄ + Ф ₁ = 13 + 3 + 1 = 17)

1001010 (F ₇ + F ₄ + F ₂ = 13 + 3 + 1 = 17, минимальная форма, используемая в кодировке Фибоначчи )

Максимальная форма выше всегда будет использовать F ₁ и всегда будет иметь конечный ноль. Полное кодирование без конечного ноля можно найти в (последовательность A104326 в OEIS ). Отбрасывая конечный ноль, кодирование для 17 выше происходит как 16-й член A104326. Минимальная форма никогда не будет использовать F ₁ и всегда будет иметь конечный ноль. Полное кодирование без конечного ноля можно найти в (последовательность A014417 в OEIS ). Это кодирование известно как представление Цекендорфа .

В этой системе счисления любая подстрока «100» может быть заменена на «011» и наоборот из-за определения чисел Фибоначчи. ^[5] Постоянное применение этих правил будет переводить от максимального к минимальному, и наоборот. Тот факт, что любое число (больше 1) может быть представлено с помощью конечного 0, означает, что всегда можно добавить 1, и учитывая, что для 1 и 2 можно представить в кодировке Фибоначчи, полнота следует по индукции .

• Нумерация Островского

• Вайсштейн, Эрик В. «Полная последовательность». MathWorld .