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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Последовательность Рудина — Шапиро, также известная как последовательность Голея — Рудина — Шапиро — это бесконечная последовательность, названная в честь Марсела Голея, Уолта Рудина и Гарольда Шапиро, которые независимо исследовали её свойства.[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, получающееся конкатенацией членов последовательности Рудина — Шапиро — неподвижная точка для замены подстрок по следующим правилам:

+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\ldots

Из правил замены очевидно, что в последовательности Рудина — Шапиро +1 может встречаться не более четырех, а -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, … (последовательность A020986 в OEIS)

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

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 A Case Study in Mathematical Research: The Golay-Rudin-Shapiro Sequence, John Brillhart and Patrick Morton
  2. Weisstein, Eric W. Rudin-Shapiro Sequence (англ.) на сайте Wolfram MathWorld.
  3. Finite automata and arithmetic, Jean-Paul Allouche

Литература[править | править вики-текст]

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