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

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

Определение


 Каждый член последовательности Рудина-Шапиро — либо +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.