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

Постоянная последовательность — это последовательность элементов, которая полностью определяется конечным числом своих членов, то есть каждая последующая часть последовательности детерминирована начальным фрагментом. Понятие встречается в нескольких областях математики и информатики: в теории чисел и комбинаторике — как последовательность, периодическая от некоторого момента; в теории алгоритмов и вычислимости — как последовательность, вычислимая за конечное время; в теории автоматов — как последовательность, порождаемая конечным автоматом.

¶Определение и общие свойства

В общем виде постоянная последовательность — это такая последовательность $\{a_n\}$, для которой существует момент $N$ и период $T$, начиная с которого $a_{n+T} = a_n$ для всех $n \geq N$. Такие последовательности называют также предпериодическими: до момента $N$ они ведут себя произвольно, а затем переходят в цикл длины $T$. Если $N = 0$, последовательность называется строго периодической.

Простейший пример — последовательность, все члены которой равны одному и тому же числу: $1, 1, 1, \dots$. Более содержательный пример — десятичное разложение дроби $1/7 = 0.\overline{142857}$, где периодическая часть $142857$ повторяется бесконечно.

¶В теории чисел

¶Десятичные дроби

Периодичность десятичных разложений — классический результат арифметики. Дробь $a/b$ (в несократимом виде) имеет конечное десятичное разложение тогда и только тогда, когда знаменатель $b$ не содержит простых множителей, отличных от $2$ и $5$. В противном случае разложение становится периодическим, причём длина периода $T$ удовлетворяет условию $T \mid \varphi(b)$, где $\varphi$ — функция Эйлера.

¶Циклические числа

Число $142857$ — циклическое: при умножении на $2, 3, 4, 5, 6$ получаются циклические сдвиги той же цифровой строки. Это свойство связано с тем, что $7$ — простое число, а $10$ является первообразным корнем по модулю $7$.

¶В комбинаторике и теории автоматов

¶Конечные автоматы

Последовательность, порождаемая конечным автоматом с $m$ состояниями, обязательно становится периодической не позднее чем после $m$ шагов: поскольку состояний конечное число, рано или поздно одно из них повторяется, и дальнейшее поведение детерминировано. Это лежит в основе алгоритма поиска цикла в последовательностях (алгоритм Флойда — «черепаха и заяц»).

¶Линейные рекуррентные последовательности

Последовательность, определяемая линейной рекуррентной формулой с постоянными коэффициентами, например $a_{n+2} = a_{n+1} + a_n$ (числа Фибоначчи), не является постоянной в целом, но её остатки по модулю $m$ всегда становятся периодическими. Этот факт называется периодичностью по модулю и применяется в криптографии и теории чисел. Период Фибоначчи по модулю $10$ равен $60$.

¶В теории алгоритмов

¶Вычислимые последовательности

Постоянная последовательность в смысле теории вычислимости — это последовательность, каждая из членов которой может быть вычислена алгоритмом за конечное время. В отличие от произвольных последовательностей (которые могут быть невычислимыми, как последовательность чисел Халтона или Борда — последовательность, содержащая все вычислимые последовательности), постоянные последовательности образуют счётное подмножество.

¶Сложность вычисления

Для постоянных последовательностей, заданных формулой, важен вопрос о сложности вычисления $n$-го члена. Например, последовательность простых чисел — постоянная (в смысле вычислимости), но известных полиномиальных алгоритмов для её вычисления не существует, что связано с гипотезой о простых числах.

¶Применение

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

¶Источники

• Кнут Д. «Искусство программирования», том 2: получисленные алгоритмы
• Голомб С. «Периодические последовательности»
• Постников М. М. «Лекции по общей алгебре»
• Ландо С. К. «Лекции по теории чисел»