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

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

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

Условия полноты

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

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

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

$a_{0}=1\,$

$s_{k-1}\geq a_{k}-1{\text{ for all }}k\geq 1$

одновременно необходимы и достаточны для того, было _{чтобы n} полной последовательностью.

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

$a_{0}=1\,$

$2a_{k}\geq a_{k+1}{\text{ for all }}k\geq 0$

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

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

Другие

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

• Последовательность числа 1, за которым следуют простые числа (изученная С.С. Пиллаи и другие); это следует из постулата Бертрана .
• Последовательность практических чисел , в которой первым членом является 1, а в качестве подмножества содержатся все остальные степени двойки. (последовательность A005153 в OEIS )
• Числа Фибоначчи , а также числа Фибоначчи с удаленным любым одним числом. Это следует из тождества, что сумма первых 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» и наоборот в соответствии с определением чисел Фибоначчи. Постоянное применение этих правил приведет к переходу от максимального к минимальному и наоборот. Тот факт, что любое число (больше 1) может быть представлено с помощью терминала 0, означает, что всегда можно добавить 1, а учитывая, что 1 и 2 могут быть представлены в кодировании Фибоначчи, полнота следует по индукции .

См. также

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

Внешние ссылки

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