Последовательность Рудина Шапиро

Последовательность Рудина — Шапиро, также известная какпоследовательность Голея — Рудина — Шапиро — этобесконечная последовательность, названная в честь Марсела Голея, УолтаРудина и Гарольда Шапиро, которые независимо исследовали её свойства.

Определение


 Каждый член последовательности Рудина-Шапиро — либо +1, либо −1. Членпоследовательности с номером n, bn, определяется по следующимправилам:

an=iεiεi+1
bn=(1)an,
 где εi — цифры двоичной записи n. Иначе говоря,an — число (возможно, пересекающихся) подстрок 11 в двоичномпредставлении n, а bn есть +1, если an четно, и −1 иначе.
 Например, a6=1,b6=1, поскольку в двоичной записи числа 6 (110)11 встречается один раз; a7=2,b7=+1, так как в двоичнойзаписи числа 7 (111) 11 встречается два раза (с пересечениями):111 и 111.
 Начиная с n=0, числа an образуют последовательность:

 0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2, 3, \ldots
 Соответствующие члены bn последовательности Рудина — Шапиро:

 +1, +1, +1, −1, +1, +1, −1, +1, +1, +1, +1, −1, −1, −1, +1, −1, \ldots

Свойства


 Последовательность Рудина — Шапиро может быть сгенерирована конечнымавтоматом с четырьмя состояниями.
 Значения an и bn в последовательности Рудина — Шапиро могут бытьнайдены рекурсивно следующим образом:
 Если n=m2k, где m — нечётное, то

 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\}

 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\}
 Таким образом, a108=a13+1=a3+1=a1+2=a0+2=2,что может быть проверено непосредственно (двоичное представление числа108, 1101100, содержит 11 в качестве подстроки дважды).Следовательно, b108=(1)2=+1.
 Слово Рудина-Шапиро+1+1+11+1+11+1+1+1+1111+11, получающеесяконкатенацией членов последовательности Рудина — Шапиро —неподвижная точка для замены подстрок по следующим правилам:

+1+1+1+1+11
+11+1+11+1
1+111+11
11111+1
 Действуя по этим правилам, получаем:

+1+1+1+1+11+1+1+11+1+11+1+1+1+11+1+11+1+1+1+1111+11
 Из правил замены очевидно, что в последовательности Рудина — Шапиро+1 может встречаться не более четырех, а 1 — не более пяти разподряд.
 Можно показать, что значения последовательности частичных суммпоследовательности Рудина — Шапиро,

sn=k=0nbk,


 1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 4, \ldots
 удовлетворяют неравенству

3n5<sn<6n for n1.