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