Последовательность Рудина — Шапиро
Последовательность Рудина — Шапиро, также известная как последовательность Голея — Рудина — Шапиро — это бесконечная последовательность, названная в честь Марсела Голея, Уолта Рудина и Гарольда Шапиро, которые независимо исследовали её свойства.[1]
Определение
Каждый член последовательности Рудина-Шапиро — либо +1, либо −1. Член последовательности с номером n, [math]\displaystyle{ b_n }[/math], определяется по следующим правилам:
- [math]\displaystyle{ a_n=\sum_i \varepsilon_i \varepsilon_{i+1} }[/math]
- [math]\displaystyle{ b_n=(-1)^{a_n} }[/math],
где [math]\displaystyle{ \varepsilon_i }[/math] — цифры двоичной записи n. Иначе говоря, [math]\displaystyle{ a_n }[/math] — число (возможно, пересекающихся) подстрок 11 в двоичном представлении n, а [math]\displaystyle{ b_n }[/math] есть +1, если [math]\displaystyle{ a_n }[/math] четно, и −1 иначе.[2]
Например, [math]\displaystyle{ a_6 = 1, b_6 = -1 }[/math], поскольку в двоичной записи числа 6 (110) 11 встречается один раз; [math]\displaystyle{ a_7 = 2, b_7 = +1 }[/math], так как в двоичной записи числа 7 (111) 11 встречается два раза (с пересечениями): 111 и 111.
Начиная с [math]\displaystyle{ n = 0 }[/math], числа [math]\displaystyle{ a_n }[/math] образуют последовательность:
Соответствующие члены [math]\displaystyle{ b_n }[/math] последовательности Рудина — Шапиро:
- +1, +1, +1, −1, +1, +1, −1, +1, +1, +1, +1, −1, −1, −1, +1, −1, … (последовательность A020985 в OEIS)
Свойства
Последовательность Рудина — Шапиро может быть сгенерирована конечным автоматом с четырьмя состояниями.[3]
Значения [math]\displaystyle{ a_n }[/math] и [math]\displaystyle{ b_n }[/math] в последовательности Рудина — Шапиро могут быть найдены рекурсивно следующим образом:
Если [math]\displaystyle{ n = m\cdot 2^k }[/math], где m — нечётное, то
- [math]\displaystyle{ a_n = \begin{cases} a_{(m-1)/4} & \text{if } m \equiv 1 \pmod{4} \\ a_{(m-1)/2} + 1 & \text{if } m \equiv 3 \pmod{4} \end{cases} }[/math]
- [math]\displaystyle{ b_n = \begin{cases} b_{(m-1)/4} & \text{if } m \equiv 1 \pmod{4} \\ -b_{(m-1)/2} & \text{if } m \equiv 3 \pmod{4} \end{cases} }[/math]
Таким образом, [math]\displaystyle{ a_{108} = a_{13} + 1 = a_3 + 1 = a_1 + 2 = a_0 + 2 = 2 }[/math], что может быть проверено непосредственно (двоичное представление числа 108, 1101100, содержит 11 в качестве подстроки дважды). Следовательно, [math]\displaystyle{ b_{108} = (-1)^2 = +1 }[/math].
Слово Рудина-Шапиро [math]\displaystyle{ +1 +1 +1 -1 +1 +1 -1 +1 +1 +1 +1 -1 -1 -1 +1 -1 \ldots }[/math], получающееся конкатенацией членов последовательности Рудина — Шапиро — неподвижная точка для замены подстрок по следующим правилам:
- [math]\displaystyle{ +1 +1 \to +1 +1 +1 -1 }[/math]
- [math]\displaystyle{ +1 -1 \to +1 +1 -1 +1 }[/math]
- [math]\displaystyle{ -1 +1 \to -1 -1 +1 -1 }[/math]
- [math]\displaystyle{ -1 -1 \to -1 -1 -1 +1 }[/math]
Действуя по этим правилам, получаем:
- [math]\displaystyle{ +1 +1 \to +1 +1 +1 -1 \to +1 +1 +1 -1 +1 +1 -1 +1 \to +1 +1 +1 -1 +1 +1 -1 +1 +1 +1 +1 -1 -1 -1 +1 -1\ldots }[/math]
Из правил замены очевидно, что в последовательности Рудина — Шапиро [math]\displaystyle{ +1 }[/math] может встречаться не более четырех, а [math]\displaystyle{ -1 }[/math] — не более пяти раз подряд.
Можно показать,[1] что значения последовательности частичных сумм последовательности Рудина — Шапиро,
- [math]\displaystyle{ s_n = \sum_{k=0}^n b_k \, , }[/math]
удовлетворяют неравенству
- [math]\displaystyle{ \sqrt{\frac{3n}{5}} \lt s_n \lt \sqrt{6n} \text{ for } n \ge 1. }[/math]
См. также
Примечания
- ↑ 1,0 1,1 A Case Study in Mathematical Research: The Golay-Rudin-Shapiro Sequence Архивная копия от 25 февраля 2019 на Wayback Machine, John Brillhart and Patrick Morton
- ↑ Weisstein, Eric W. Rudin-Shapiro Sequence (англ.) на сайте Wolfram MathWorld.
- ↑ Finite automata and arithmetic Архивная копия от 5 июня 2011 на Wayback Machine, Jean-Paul Allouche
Литература
- Jean-Paul Allouche and Jeffrey Shallit Automatic Sequences Cambridge University Press 2003