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

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

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

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

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

.

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

необходимы и достаточны для ап быть полной последовательностью.[1][2]

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

достаточно для ап быть полной последовательностью.[1]

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

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

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

Приложения

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

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

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

110111 (F6 + F5 + F3 + F2 + F1 = 8 + 5 + 2 + 1 + 1 = 17, максимальная форма)
111001 (F6 + F5 + F4 + F1 = 8 + 5 + 3 + 1 = 17)
111010 (F6 + F5 + F4 + F2 = 8 + 5 + 3 + 1 = 17)
1000111 (F7 + F3 + F2 + F1 = 13 + 2 + 1 + 1 = 17)
1001001 (F7 + F4 + F1 = 13 + 3 + 1 = 17)
1001010 (F7 + F4 + F2 = 13 + 3 + 1 = 17, минимальная форма, как используется в Кодирование Фибоначчи )

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

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

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

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

  1. ^ а б c d Хонсбергер Р. Математические жемчужины III. Вашингтон, округ Колумбия: Математика. Доц. Америк., 1985, стр.123-128.
  2. ^ Браун, Дж. Л. (1961). «Примечание о полных последовательностях целых чисел». Американский математический ежемесячник. 68 (6): 557–560. Дои:10.2307/2311150. JSTOR  2311150.
  3. ^ С. С. Пиллаи, "Арифметическая функция относительно простых чисел", Annamalai University Journal (1930), стр. 159–167.
  4. ^ Сринивасан, А. К. (1948), «Практические цифры» (PDF), Текущая наука, 17: 179–180, МИСТЕР  0027799.
  5. ^ Стахов Алексей. «Основные операции арифметики Фибоначчи». Архивировано из оригинал 24 января 2013 г.. Получено 11 сентября, 2016., Музей гармонии и золотого сечения. Первоначальный доступ: 27 июля 2010 г.

внешняя ссылка