Просмотр кода страницы Последовательность Рудина — Шапиро

'''Последовательность Рудина — Шапиро''', также известная как '''последовательность Голея — Рудина — Шапиро''' — это бесконечная последовательность, названная в честь Марсела Голея, [[Рудин, Уолт|Уолта Рудина]] и [[:en:Harold S. Shapiro|Гарольда Шапиро]], которые независимо исследовали её свойства.<ref name=bm>[http://www.joma.org/images/upload_library/22/Ford/Brillhart-Morton854-869.pdf A Case Study in Mathematical Research: The Golay-Rudin-Shapiro Sequence] {{Wayback|url=http://www.joma.org/images/upload_library/22/Ford/Brillhart-Morton854-869.pdf |date=20190225103207 }}, John Brillhart and Patrick Morton</ref>

== Определение ==
Каждый член последовательности Рудина-Шапиро — либо +1, либо &minus;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> четно, и &minus;1 иначе.<ref>{{MathWorld|urlname=Rudin-ShapiroSequence|title=Rudin-Shapiro Sequence}}</ref>

Например, <math>a_6 = 1, b_6 = -1</math>, поскольку в [[Двоичная система счисления|двоичной записи]] числа 6 (110) ''11'' встречается один раз; <math>a_7 = 2, b_7 = +1</math>, так как в двоичной записи числа 7 (111) ''11'' встречается два раза (с пересечениями): '''11'''1 и 1'''11'''.

Начиная с <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|A014081}})

Соответствующие члены <math>b_n</math> последовательности Рудина — Шапиро:

: +1, +1, +1, &minus;1, +1, +1, &minus;1, +1, +1, +1, +1, &minus;1, &minus;1, &minus;1, +1, &minus;1, … ({{OEIS|A020985}})

== Свойства ==
Последовательность Рудина — Шапиро может быть сгенерирована [[Конечный автомат|конечным автоматом]] с четырьмя состояниями.<ref>[http://www.emis.de/journals/SLC/opapers/s30allouche.pdf Finite automata and arithmetic] {{Wayback|url=http://www.emis.de/journals/SLC/opapers/s30allouche.pdf |date=20110605231459 }}, Jean-Paul Allouche</ref>

Значения <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> — не более пяти раз подряд.

Можно показать,<ref name=bm /> что значения последовательности частичных сумм последовательности Рудина — Шапиро,

: <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|A020986}})

удовлетворяют неравенству

: <math>\sqrt{\frac{3n}{5}} < s_n < \sqrt{6n} \text{ for } n \ge 1.</math>

== См. также ==
* [[Многочлены Шапиро]]<!--en:Shapiro_polynomials-->

== Примечания ==
{{reflist}}
{{refbegin}}
{{refend}}

== Литература ==
* Jean-Paul Allouche and Jeffrey Shallit ''Automatic Sequences'' [[Издательство Кембриджского университета|Cambridge University Press]] 2003

[[Категория:Целочисленные последовательности]]