- Последовательность Рудина
-
Последовательность Рудина — Шапиро, также известная как последовательность Голея — Рудина — Шапиро — это бесконечная последовательность, названная в честь Марсела Голея, Уолта Рудина и Гарольда Шапиро, которые независимо исследовали её свойства.[1]
Содержание
Определение
Каждый член последовательности Рудина-Шапиро — либо +1, либо −1. Член последовательности с номером n,
, определяется по следующим правилам:
,
где
— цифры двоичной записи n. Иначе говоря,
— число (возможно, пересекающихся) подстрок 11 в двоичном представлении n, а
есть +1, если
четно, и −1 иначе.[2]
Например,
, поскольку в двоичной записи числа 6 (110) 11 встречается один раз;
, так как в двоичной записи числа 7 (111) 11 встречается два раза (с пересечениями): 111 и 111.
Начиная с
, числа
образуют последовательность:
Соответствующие члены
последовательности Рудина — Шапиро:
- +1, +1, +1, −1, +1, +1, −1, +1, +1, +1, +1, −1, −1, −1, +1, −1, … (последовательность A020985 в OEIS)
Свойства
Последовательность Рудина — Шапиро может быть сгенерирована конечным автоматом с четырьмя состояниями.[3]
Значения
и
в последовательности Рудина — Шапиро могут быть найдены рекурсивно следующим образом:
Если
, где m — нечётное, то
Таким образом,
, что может быть проверено непосредственно (двоичное представление числа 108, 1101100, содержит 11 в качестве подстроки дважды). Следовательно,
.
Слово Рудина-Шапиро
, получающееся конкатенацией членов последовательности Рудина — Шапиро — неподвижная точка для замены подстрок по следующим правилам:
Действуя по этим правилам, получаем:
Из правил замены очевидно, что в последовательности Рудина — Шапиро
может встречаться не более четырех, а
— не более пяти раз подряд.
Можно показать,[1] что значения последовательности частичных сумм последовательности Рудина — Шапиро,
удовлетворяют неравенству
См. также
Примечания
- ↑ 1 2 A Case Study in Mathematical Research: The Golay-Rudin-Shapiro Sequence, John Brillhart and Patrick Morton
- ↑ Weisstein, Eric W. Rudin-Shapiro Sequence (англ.) на сайте Wolfram MathWorld.
- ↑ Finite automata and arithmetic, Jean-Paul Allouche
Литература
- Jean-Paul Allouche and Jeffrey Shallit Automatic Sequences Cambridge University Press 2003
Категория:- Целочисленные последовательности
Wikimedia Foundation. 2010.