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

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

Например, последовательность степеней двойки (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 было полной последовательностью.

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

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

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

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

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

Другие полные последовательности

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

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

Приложения

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

Кодирование Фибоначчи

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

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

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

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

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

1001001 (F ₇ + F ₄ + F ₁ = 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 могут быть представлены в кодировке Фибоначчи, полнота следует по индукции .

Смотрите также

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

Рекомендации

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

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