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

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

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

• Чётные числа; поскольку сумма чётных чисел всегда чётна, никакое нечётное число нельзя получить как сумму чётных.
• Степени тройки; никакое число, имеющую цифру «2» в троичном представлении (2, 5, 6...), нельзя получить из таких чисел.

Без потери общности предположим, что последовательность a_n не убывает, и определим частичные суммы последовательности a_n

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

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

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

${\displaystyle s_{k-1}\geqslant a_{k}-1\,\forall \,k\geqslant 1}$

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

Из этого утверждения следует, что условия

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

${\displaystyle 2a_{k}\geqslant a_{k+1}\,\forall \,k\geqslant 1}$

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

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

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

• Последовательность чисел, начинающаяся с 1 с последующими простыми числами (последовательность изучал С. С. Пиллаи^[2] и др.). Следует из постулата Бертрана^[1].
• Последовательность практичных чисел имеет 1 в качестве первого члена и содержит все степени двойки в качестве подмножества^[3] (последовательность A005153 в OEIS)
• Числа Фибоначчи, как и числа Фибониччи с любом удалённым числом^[1]. Это следует из тождества, что сумма первых n чисел Фибоначчи равна (n + 2)-му числу Фибоначчи минус 1 (см. Числа Фибоначчи).
• Все n-шаговые числа Фибоначчи^[4], где n = 2 даёт обычные числа Фибоначчи, n = 3 даёт числа трибоначчи и т. д.
• Центральные многоугольные числа, которые дают максимальное число разбиений плоскости, которое можно получить с помощью прямых.
• Все центральные многоугольные числа размерности d > 2, которые используют гиперплоскости (размерности d − 1) для максимального разбиения пространства (последовательность A216274 в OEIS).
• Последовательность максимальных разбиений плоскости кругами^[5].
• Все последовательности максимальных разбиений пространства размерности d гиперсферами (размерности d − 1) (последовательность A059250 в OEIS).
• Упорядоченное множество собственных делителей каждого практичного числа (вместе с 1 и самим числом) образует полную подпоследовательность.

Так же, как степени двойки образуют полную последовательность (для двоичной системы счисления), фактически, любую полную последовательность можно использовать для кодировки целых чисел подобно битовым строкам. Самая правая битовая позиция соответствует первому (наименьшему) числу в последовательности. Затем выбирается следующий правый член и так далее. Это представление не обязательно будет единственным.

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

 110111 ${\displaystyle (F_{6}+F_{5}+F_{3}+F_{2}+F_{1}=8+5+2+1+1=17}$, максимальная форма)

 111001 ${\displaystyle (F_{6}+F_{5}+F_{4}+F_{1}=8+5+3+1=17)}$

 111010 ${\displaystyle (F_{6}+F_{5}+F_{4}+F_{2}=8+5+3+1=17)}$

1000111 ${\displaystyle (F_{7}+F_{3}+F_{2}+F_{1}=13+2+1+1=17)}$

1001001 ${\displaystyle (F_{7}+F_{4}+F_{1}=13+3+1=17)}$

1001010 ${\displaystyle (F_{7}+F_{4}+F_{2}=13+3+1=17}$, минимальная форма, используемая в фибоначчиевой системе счисления)

Максимальная форма всегда использует F₁ и всегда имеет на конце 1. Полный код без конечной единицы можно найти в последовательности A104326. Заметим, что кодировка для числа 17 с отброшенной конечной единицей находится на 16-й позиции в списке.

Минимальная форма никогда не содержит F₁ и всегда имеет на конце 0. Список кодировок без конечного нуля можно найти в последовательности A014417. Эта кодировка известна как представление Цекендорфа.

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

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

• Кодировки полной последовательностью простых чисел (включая 1) с помощью жадного алгоритма можно найти в последовательности A007924.
• Кодировки минимизирующего алгоритма той же последовательностью можно найти в последовательности A205598.
• Кодировки центральными многоугольными числами с помощью жадного алгоритма можно найти в последовательности A204009.

• Нумерация Островского^[англ.]

• Weisstein, Eric W. Complete Sequence (англ.) на сайте Wolfram MathWorld.