Русская Википедия:Полная последовательность
Шаблон:Не переведено 5 называется полной последовательностью, если любое положительное целое число может быть выражено в виде суммы значений из последовательности, при этом каждое значение можно использовать только один раз.
Например, последовательность Шаблон:Не переведено 5 {1, 2, 4, 8, ...}, базис двоичной системы счисления, является полной системой. Если задано любое натуральное число, мы можем выбрать значения, соответствующие единицам в двоичном представлении числа и их сумма даст это число (например, 37 = 1001012 = 1 + 4 + 32). Эта последовательность минимальна, поскольку ни одно число не может быть изъято из последовательности без того, чтобы некоторое натуральное число нельзя было бы выразить в виде суммы членов последовательности. Простые примеры неполных последовательностей:
- Чётные числа; поскольку сумма чётных чисел всегда чётна, никакое нечётное число нельзя получить как сумму чётных.
- Степени тройки; никакое число, имеющую цифру «2» в троичном представлении (2, 5, 6...), нельзя получить из таких чисел.
Условия полноты
Без потери общности предположим, что последовательность an не убывает, и определим частичные суммы последовательности an
- <math>s_n = \sum_{m=0}^n a_m.</math>
Тогда условия
- <math>a_0 = 1,</math>
- <math>s_{k-1} \geqslant a_k - 1 \, \forall \, k \geqslant 1</math>
являются необходимыми и достаточными для последовательности an, чтобы она была полнойШаблон:Sfn.
Из этого утверждения следует, что условия
- <math>a_0 = 1,</math>
- <math>2a_k \geqslant a_{k+1} \, \forall \, k \geqslant 1</math>
достаточны для того, чтобы последовательность an была полнойШаблон:Sfn.
Однако существуют полные последовательности, которые не удовлетворяют условиям данного следствия. Например, последовательность Шаблон:OEIS2C, состоящая из 1 и первого простого числа после каждой степени двойки.
Другие полные последовательности
Ниже приведён список наиболее известных полных последовательностей.
- Последовательность чисел, начинающаяся с 1 с последующими простыми числами (последовательность изучал С. С. ПиллаиШаблон:Sfn и др.). Следует из постулата БертранаШаблон:Sfn.
- Последовательность практичных чисел имеет 1 в качестве первого члена и содержит все степени двойки в качестве подмножестваШаблон:Sfn (Шаблон:OEIS)
- Числа Фибоначчи, как и числа Фибониччи с любом удалённым числомШаблон:Sfn. Это следует из тождества, что сумма первых n чисел Фибоначчи равна (n + 2)-му числу Фибоначчи минус 1 (см. Числа Фибоначчи).
- Все n-шаговые числа Фибоначчи[1], где n = 2 даёт обычные числа Фибоначчи, n = 3 даёт числа трибоначчи и т. д.
- Центральные многоугольные числа, которые дают максимальное число разбиений плоскости, которое можно получить с помощью прямых.
- Все центральные многоугольные числа размерности d > 2, которые используют гиперплоскости (размерности d − 1) для максимального разбиения пространства (Шаблон:OEIS).
- Последовательность максимальных разбиений плоскости кругами[2].
- Все последовательности максимальных разбиений пространства размерности d гиперсферами (размерности d − 1) (Шаблон:OEIS).
- Упорядоченное множество собственных делителей каждого практичного числа (вместе с 1 и самим числом) образует полную подпоследовательность.
Приложения
Так же, как степени двойки образуют полную последовательность (для двоичной системы счисления), фактически, любую полную последовательность можно использовать для кодировки целых чисел подобно битовым строкам. Самая правая битовая позиция соответствует первому (наименьшему) числу в последовательности. Затем выбирается следующий правый член и так далее. Это представление не обязательно будет единственным.
Фибоначчиева система счисления
Например, в системе арифметики Фибоначчи, основанной на последовательности Фибоначчи, число 17 может быть представлено несколькими способами:
- 110111 <math>(F_6 + F_5 + F_3 + F_2 + F_1 = 8 + 5 + 2 + 1 + 1 = 17</math>, максимальная форма)
- 111001 <math>(F_6 + F_5 + F_4 + F_1 = 8 + 5 + 3 + 1 = 17)</math>
- 111010 <math>(F_6 + F_5 + F_4 + F_2 = 8 + 5 + 3 + 1 = 17)</math>
- 1000111 <math>(F_7 + F_3 + F_2 + F_1 = 13 + 2 + 1 + 1 = 17)</math>
- 1001001 <math>(F_7 + F_4 + F_1 = 13 + 3 + 1 = 17)</math>
- 1001010 <math>(F_7 + F_4 + F_2 = 13 + 3 + 1 = 17</math>, минимальная форма, используемая в фибоначчиевой системе счисления)
- Максимальная форма всегда использует F1 и всегда имеет на конце 1. Полный код без конечной единицы можно найти в последовательности Шаблон:OEIS2C. Заметим, что кодировка для числа 17 с отброшенной конечной единицей находится на 16-ой позиции в списке.
- Минимальная форма никогда не содержит F1 и всегда имеет на конце 0. Список кодировок без конечного нуля можно найти в последовательности Шаблон:OEIS2C. Эта кодировка известна как представление Цекендорфа.
В этой системе счисления любая подстрока «100» может быть заменена на «011» и наоборот согласно определению чисел ФибоначчиШаблон:Sfn. Последовательное применение этих правил переводит максимальную форму в минимальную, и наоборот. Факт, что любое число (большее 1) может быть представлено 0 на конце, означает, что всегда можно добавить 1, а поскольку 1 и 2 могут быть представлены в фибоначчиевой системе счисления, полнота последовательности доказывается по индукции.
Другие системы кодирования
Можно придумать и другие аналогичные системы счисления. Как и для последовательности Фибоначчи, эти системы кодирования, использующие полные последовательности, дают несколько методов кодирования числа. Основным методом является жадный алгоритм, который пытается минимизировать число членов, необходимых для кодирования целого числа членами полной последовательности, а также (минимизирующего) алгоритмa, который пытается максимизировать число членов в кодировке того же целого числа.
- Кодировки полной последовательностью простых чисел (включая 1) с помощью жадного алгоритма можно найти в последовательности Шаблон:OEIS2C.
- Кодировки минимизирующего алгоритма той же последовательностью можно найти в последовательности Шаблон:OEIS2C.
- Кодировки центральными многоугольными числами с помощью жадного алгоритма можно найти в последовательности Шаблон:OEIS2C.
См. также
Примечания
Литература
- Шаблон:Статья См. также книги А. П. Стахова
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья
Ссылки
Шаблон:Последовательности и ряды Шаблон:Rq
