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

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

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

• 1 Условия полноты
• 2 Другие полные последовательности
• 3 Приложения
  • 3.1 Кодирование Фибоначчи
  • 3.2 Другие системы кодирования
• 4 См. Также
• 5 Ссылки
• 6 Внешние ссылки

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

$sn\; =\; \sum \; m\; =\; 0\; nam\; \{\backslash \; displaystyle\; s\_\; \{n\}\; =\; \backslash \; sum\; \_\; \{m\; =\; 0\}\; ^\; \{n\}\; a\_\; \{m\}\}$.

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

$a\; 0\; Знак\; равно\; 1\; \{\backslash \; displaystyle\; a\_\; \{0\}\; =\; 1\; \backslash ,\}$

$sk\; -\; 1\; \ge \; ak\; -\; 1\; для\; всех\; k\; \ge \; 1\; \{\backslash \; displaystyle\; s\_\; \{k-1\}\; \backslash \; geq\; a\_\; \{k\}\; -1\; \{\backslash \; text\; \{\; для\; всех\}\}\; k\; \backslash \; geq\; 1\}$

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

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

$a\; 0\; Знак\; равно\; 1\; \{\backslash \; displaystyle\; a\_\; \{0\}\; =\; 1\; \backslash ,\}$

$2\; ak\; \ge \; ak\; +\; 1\; для\; всех\; k\; \ge \; 1\; \{\backslash \; displaystyle\; 2a\_\; \{k\}\; \backslash \; geq\; a\_\; \{k\; +\; 1\}\; \{\backslash \; text\; \{для\; всех\}\; \}\; k\; \backslash \; geq\; 1\}$

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

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

Ниже приводится список наиболее известных полных последовательностей.

• Последовательность из числа 1, за которым следуют простые числа (изучено С.С. Пиллаи и другими); это следует из постулата Бертрана.
• Последовательность практических чисел, которая имеет 1 в качестве первого члена и содержит все остальные степени 2 в качестве подмножества. (последовательность A005153 в OEIS )
• Числа Фибоначчи, а также числа Фибоначчи с удалением любого одного числа. Это следует из тождества, что сумма первые n чисел Фибоначчи - это (n + 2) -ое число Фибоначчи минус 1 (см. Fibonacci_numbers # Second_identity ).
• Все числа n-шагов Фибоначчи, где n = 2 дает числа Фибоначчи выше, n = 3 дает Числа Трибоначчи и т. Д.
• Последовательность ленивого поставщика услуг, которая дает максимальное количество разделов, на которые может быть разделена плоскость , используя n прямых линии как разделители.
• Все высшие измерения последовательности ленивого поставщика услуг, в которой используется n гиперплоскостей (размерности d - 1) для максимального разделения пространства (размерности d). (последовательность A216274 в OEIS )
• Последовательность резака печенья, которая дает максимальное количество разделов, на которые может быть разделена плоскость, с использованием n кругов в качестве разделителей.
• Все высшие измерения последовательности резака печенья, которые используются es n гиперсферических поверхностей (размерности d - 1), чтобы максимально разделить пространство (размерности d). (последовательность A059250 в OEIS )
• Упорядоченный набор собственных делителей каждого практического числа (который включает 1 и само себя) образует полную подпоследовательность.

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

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

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

110111 (F 6 + F 5 + F 3 + F 2 + F 1 = 8 + 5 + 2 + 1 + 1 = 17, максимальная форма)

111001 (F 6 + F 5 + F 4 + F 1 = 8 + 5 + 3 + 1 = 17)

111010 (F 6 + F 5 + F 4 + F 2 = 8 + 5 + 3 + 1 = 17)

1000111 (F 7 + F 3 + F 2 + F 1 = 13 + 2 + 1 + 1 = 17)

1001001 (F 7 + F 4 + F 1 = 13 + 3 + 1 = 17)

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

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

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

Другие системы кодирования

Другие системы кодирования могут быть разработаны аналогичным образом. Как и в случае с последовательностью Фибоначчи выше, эти системы кодирования, которые используют полные последовательности, должны будут иметь дело с несколькими решениями кодирования. Два основных используемых метода - это жадный алгоритм, который попытается минимизировать количество терминов, необходимых для кодирования целого числа из полной последовательности, и минимизирующий алгоритм, который попытается максимизировать количество терминов, необходимых для кодирования такое же целое число.

• Кодирование последовательности числа 1, за которым следуют простые числа с использованием жадного алгоритма, можно найти по адресу

(последовательность A007924 в OEIS ).

• Кодирование для последовательность числа 1, за которой следуют простые числа с использованием алгоритма минимизации, можно найти по адресу

(последовательность A205598 в OEIS ).

• Кодирование для последовательности ленивого поставщика услуг с использованием жадного алгоритма можно найти по адресу

(последовательность A204009 в OEIS ).

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

1. ^ Honsberger, R. Mathematical Gems III. Вашингтон, округ Колумбия : Math. Assoc. Amer., 1985, стр.123-128.
2. ^Brown, JL (1961). «Примечание о полных последовательностях целых чисел». The American Mathematical Monthly. 68 (6) : 557–560. doi : 10.2307 / 2311150. JSTOR 2311150.
3. ^SS Pillai, «Арифметическая функция относительно простых чисел», Annamalai University Журнал (1930), стр. 159–167.
4. ^Сринивасан, AK (1948), «Практические числа» (PDF), Cur Rent Science, 17: 179–180, MR 0027799.
5. ^Вайсштейн, Эрик У. «Число n-шагов Фибоначчи». MathWorld.
6. ^Вайсштейн, Эрик У. «Деление плоскости кругами». MathWorld.
7. ^Стахов Алексей. «Основные операции арифметики Фибоначчи». Архивировано из оригинала 24 января 2013 года. Дата обращения 11 сентября 2016 года., Музей гармонии и золотого сечения. Первоначальный доступ: 27 июля 2010 г.

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