Последовательность Рудина — Шапиро (Hkvly;kfgmyl,ukvm, Jr;nug — Oghnjk)

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

Определение

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

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

b_{n}=(-1)^{a_{n}}

,

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

Например, $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, … (последовательность A014081 в OEIS)

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

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

Свойства

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

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

Если $n=m\cdot 2^{k}$ , где 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}}

Таким образом, $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\ldots$ , получающееся конкатенацией членов последовательности Рудина — Шапиро — неподвижная точка для замены подстрок по следующим правилам: