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

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

Определение

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

$a_n=\sum _i{\epsilon }_i{\epsilon }_{i+1}$

$b_n=(-1{)}^{a_n}$,

где ${\epsilon }_i$ — цифры двоичной записи n. Иначе говоря, $a_n$ — число (возможно, пересекающихся) подстрок 11 в двоичном представлении n, а $b_n$ есть +1, если $a_n$ четно, и −1 иначе.

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

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

0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2, 3, … (Шаблон:OEIS)

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

+1, +1, +1, −1, +1, +1, −1, +1, +1, +1, +1, −1, −1, −1, +1, −1, … (Шаблон:OEIS)

Свойства

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

Значения $a_n$ и $b_n$ в последовательности Рудина — Шапиро могут быть найдены рекурсивно следующим образом:

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

$a_n=\{\begin{array}{cc}{a}_{(m-1)/4}& \text{if }m\equiv 1(\mathrm{mod}4)\\ a_{(m-1)/2}+1& \text{if }m\equiv 3(\mathrm{mod}4)\end{array}$

$b_n=\{\begin{array}{cc}{b}_{(m-1)/4}& \text{if }m\equiv 1(\mathrm{mod}4)\\ -b_{(m-1)/2}& \text{if }m\equiv 3(\mathrm{mod}4)\end{array}$

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

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

$+1+1\to +1+1+1-1$

$+1-1\to +1+1-1+1$

$-1+1\to -1-1+1-1$

$-1-1\to -1-1-1+1$

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

$+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\dots$

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

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

$s_n=\sum _{k=0}^n{b}_k,$

1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 4, … (Шаблон:OEIS)

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

$\sqrt{\frac{3n}{5}}<s_n<\sqrt{6n}\text{ for }n\ge 1.$

См. также

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

Литература

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