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

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

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

${\displaystyle a_{n}=\sum _{i}\varepsilon _{i}\varepsilon _{i+1}}$

${\displaystyle b_{n}=(-1)^{a_{n}}}$,

где ${\displaystyle \varepsilon _{i}}$ — цифры двоичной записи n. Иначе говоря, ${\displaystyle a_{n}}$ — число (возможно, пересекающихся) подстрок 11 в двоичном представлении n, а ${\displaystyle b_{n}}$ есть +1, если ${\displaystyle a_{n}}$ четно, и −1 иначе.^[2]

Например, ${\displaystyle a_{6}=1,b_{6}=-1}$, поскольку в двоичной записи числа 6 (110) 11 встречается один раз; ${\displaystyle a_{7}=2,b_{7}=+1}$, так как в двоичной записи числа 7 (111) 11 встречается два раза (с пересечениями): 111 и 111.

Начиная с ${\displaystyle n=0}$, числа ${\displaystyle a_{n}}$ образуют последовательность:

0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2, 3, … (последовательность A014081 в OEIS)

Соответствующие члены ${\displaystyle b_{n}}$ последовательности Рудина — Шапиро:

+1, +1, +1, −1, +1, +1, −1, +1, +1, +1, +1, −1, −1, −1, +1, −1, … (последовательность A020985 в OEIS)

Последовательность Рудина — Шапиро может быть сгенерирована конечным автоматом с четырьмя состояниями.^[3]

Значения ${\displaystyle a_{n}}$ и ${\displaystyle b_{n}}$ в последовательности Рудина — Шапиро могут быть найдены рекурсивно следующим образом:

Если ${\displaystyle n=m\cdot 2^{k}}$, где m — нечётное, то

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

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

Таким образом, ${\displaystyle a_{108}=a_{13}+1=a_{3}+1=a_{1}+2=a_{0}+2=2}$, что может быть проверено непосредственно (двоичное представление числа 108, 1101100, содержит 11 в качестве подстроки дважды). Следовательно, ${\displaystyle b_{108}=(-1)^{2}=+1}$.

Слово Рудина-Шапиро ${\displaystyle +1+1+1-1+1+1-1+1+1+1+1-1-1-1+1-1\ldots }$, получающееся конкатенацией членов последовательности Рудина — Шапиро — неподвижная точка для замены подстрок по следующим правилам:

${\displaystyle +1+1\to +1+1+1-1}$

${\displaystyle +1-1\to +1+1-1+1}$

${\displaystyle -1+1\to -1-1+1-1}$

${\displaystyle -1-1\to -1-1-1+1}$

Действуя по этим правилам, получаем:

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

Из правил замены очевидно, что в последовательности Рудина — Шапиро ${\displaystyle +1}$ может встречаться не более четырех, а ${\displaystyle -1}$ — не более пяти раз подряд.

Можно показать,^[1] что значения последовательности частичных сумм последовательности Рудина — Шапиро,

${\displaystyle s_{n}=\sum _{k=0}^{n}b_{k}\,,}$

1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 4, … (последовательность A020986 в OEIS)

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

${\displaystyle {\sqrt {\frac {3n}{5}}}<s_{n}<{\sqrt {6n}}{\text{ for }}n\geq 1.}$

• Многочлены Шапиро

• Jean-Paul Allouche and Jeffrey Shallit Automatic Sequences Cambridge University Press 2003