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

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

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

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

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

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

.

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

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

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

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

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

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

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

  • Последовательность чисел, начинающаяся с 1 с последующими простыми числами (последовательность изучал С. С. Пиллаи[2] и др.). Следует из постулата Бертрана[1].
  • Последовательность практичных чисел имеет 1 в качестве первого члена и содержит все степени двойки 2 в качестве подмножества[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 , максимальная форма)
 111001
 111010
1000111
1001001
1001010 , минимальная форма, используемая в фибоначчиевой системе счисления)
Максимальная форма всегда использует F1 и всегда имеет на конце 1. Полный код без конечной единицы можно найти в последовательности A104326. Заметим, что кодировка для числа 17 с отброшенной конечной единицей находится на 16-ой позиции в списке.
Минимальная форма никогда не содержит F1 и всегда имеет на конце 0. Список кодировок без конечного нуля можно найти в последовательности A014417. Эта кодировка известна как представление Цекендорфа.

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

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

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

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

См. также
  • Нумерация Островского

Примечания
  1. Honsberger, 1985, с. 123-128.
  2. Pillai, 1930, с. 159–167.
  3. Srinivasan, 1948, с. 179–180.
  4. Weisstein, Eric W. Fibonacci n-Step Number (англ.) на сайте Wolfram MathWorld.
  5. Weisstein, Eric W. Plane Division by Circles (англ.) на сайте Wolfram MathWorld.
  6. Стахов.

Литература
  • Алексей П. Стахов. Основные операции на «фибоначчиевыми» представлениями. Архивировано 15 июля 2017 года. См. также книги А.П. Стахова
    • Стахов А.П. Введение в алгоритмическую теория измерения. — М.: Сов. Радио, 1977.
    • Стахов А.П. Коды золотой пропорции. — М.: Радио и связь, 1984. — (Кибернетика).
  • Honsberger R. Mathematical Gems III.. — Washington, DC: Math. Assoc. Amer., 1985. — Т. 9. — (The Dolchiani Mathematical Expositions). — ISBN 0-88385-313-2.
  • Pillai S. S. An arithmetical function concerning primes // Annamalai University Journal. — 1930.
  • Srinivasan A. K. Practical numbers // Current Science. — 1948. — Т. 17.

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.