Полная последовательность — такая целочисленная последовательность, что любое положительное целое число может быть выражено как сумма значений её членов, при этом каждое значение можно использовать только один раз.
Например, последовательность степеней двойки 1, 2, 4, 8, … — полная: произвольное натуральное число может быть записано в двоичном представлении числа и их сумма даст это число (например, 37 = 1001012 = 1 + 4 + 32); эта последовательность минимальна в том смысле, что ни одно число не может быть изъято из последовательности с сохранением выразимости всех натуральных чисел как сумма её членов. При этом последовательность степеней тройки неполна: никакое число, имеющую цифру «2» в троичном представлении (2, 5, 6, …) нельзя получить из таких чисел.
Любую полную последовательность можно использовать для кодировки целых чисел подобно битовым строкам: самая правая битовая позиция соответствует первому (наименьшему) числу в последовательности, затем выбирается следующий правый член и так далее. Это представление не обязательно будет единственным.
Условия полноты Для неубывающей последовательности с частичными суммами:
условия: ,
являются необходимыми и достаточными, чтобы она была полной. Требование неубывания не приводит к потере общности, так как
Из этого утверждения следует, что условия: ,
достаточны для того, чтобы последовательность была полной, однако существуют полные последовательности, которые не удовлетворяют условиям данного следствия (например последовательностьсостоящая из 1 и первого простого числа после каждой степени двойки).
Примеры Последовательность чисел, начинающаяся с 1 с последующими простыми числами (последовательность Пиллаи), как следует из постулата Бертрана — полна.
Последовательность практичных чисел имеет 1 в качестве первого члена и содержит все степени двойки в качестве подмножества, таким образом является полной.
Числа Фибоначчи, как и числа Фибониччи с любом удалённым числом дают полные последовательности — это следует из тождества, что сумма первых чисел Фибоначчи равна -у числу Фибоначчи минус единица. На этом свойстве полноты основана фибоначчиева система счисления. Также полны последовательности всех чисел Фибоначчи высокого порядка (трибоначчи, тетраначчи и так далее).
Центральные многоугольные числа — числа, дающие максимальное число разбиений плоскости, которое можно получить с помощью прямых — образуют полную последовательность. Также полны последовательности всех центральных многоугольных чисел размерности , которые используют гиперплоскости (размерности ) для максимального разбиения пространства; последовательность максимальных разбиений плоскости кругами; последовательности максимальных разбиений пространства размерности гиперсферами (размерности ).
Упорядоченное множество собственных делителей каждого практичного числа (вместе с 1 и самим числом) образует полную подпоследовательность.
Системы счисления Всякая полная последовательность позволяет построить систему счисления, притом, как и для последовательности Фибоначчи, такие системы кодирования могут давать несколько методов кодирования числа. Оптимизировать такие системы счисления возможно жадным алгоритмом, который пытается минимизировать число членов, необходимых для кодирования целого числа членами полной последовательности, а также (минимизирующим) алгоритмом, который пытается максимизировать число членов в кодировке того же целого числа. Изучены кодировки полной последовательностью простых чисел (включая 1) с помощью жадного алгоритма и минимизирующего алгоритма, кодировки центральными многоугольными числами с помощью жадного алгоритма.
Примечания
Литература , также книги автора:
Ссылки
Категория:Целочисленные последовательности