Vjylku

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

Определение |

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

an=∑iεiεi+1{displaystyle a_{n}=sum _{i}varepsilon _{i}varepsilon _{i+1}}

bn=(−1)an{displaystyle b_{n}=(-1)^{a_{n}}},

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

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

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

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

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

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

Свойства |

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

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

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

an={a(m−1)/4if m≡1(mod4)a(m−1)/2+1if m≡3(mod4){displaystyle a_{n}={begin{cases}a_{(m-1)/4}&{text{if }}mequiv 1{pmod {4}}\a_{(m-1)/2}+1&{text{if }}mequiv 3{pmod {4}}end{cases}}}

bn={b(m−1)/4if m≡1(mod4)−b(m−1)/2if m≡3(mod4){displaystyle b_{n}={begin{cases}b_{(m-1)/4}&{text{if }}mequiv 1{pmod {4}}\-b_{(m-1)/2}&{text{if }}mequiv 3{pmod {4}}end{cases}}}

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

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

+1+1→+1+1+1−1{displaystyle +1+1to +1+1+1-1}

+1−1→+1+1−1+1{displaystyle +1-1to +1+1-1+1}

−1+1→−1−1+1−1{displaystyle -1+1to -1-1+1-1}

−1−1→−1−1−1+1{displaystyle -1-1to -1-1-1+1}

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

+1+1→+1+1+1−1→+1+1+1−1+1+1−1+1→+1+1+1−1+1+1−1+1+1+1+1−1−1−1+1−1…{displaystyle +1+1to +1+1+1-1to +1+1+1-1+1+1-1+1to +1+1+1-1+1+1-1+1+1+1+1-1-1-1+1-1ldots }

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

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

sn=∑k=0nbk,{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)

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

3n5<sn<6n for n≥1.{displaystyle {sqrt {frac {3n}{5}}}<s_{n}<{sqrt {6n}}{text{ for }}ngeq 1.}

См. также |

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

Примечания |

Литература |

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