Последовательность Рудина — Шапиро, также известная как последовательность Голея — Рудина — Шапиро — это бесконечная последовательность, названная в честь Марсела Голея, Уолта Рудина и Гарольда Шапиро, которые независимо исследовали её свойства.A Case Study in Mathematical Research: The Golay-Rudin-Shapiro Sequence , John Brillhart and Patrick Morton

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

,

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

Например, , поскольку в двоичной записи числа 6 (110) 11 встречается один раз; , так как в двоичной записи числа 7 (111) 11 встречается два раза (с пересечениями): 111 и 111.

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

0, 0, 0, 1, 0, 0, 1, 2, 0, 0, 0, 1, 1, 1, 2, 3, … ()

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

+1, +1, +1, −1, +1, +1, −1, +1, +1, +1, +1, −1, −1, −1, +1, −1, … ()

Свойства Последовательность Рудина — Шапиро может быть сгенерирована конечным автоматом с четырьмя состояниями.Finite automata and arithmetic , Jean-Paul Allouche

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

Если , где m — нечётное, то

Таким образом, , что может быть проверено непосредственно (двоичное представление числа 108, 1101100, содержит 11 в качестве подстроки дважды). Следовательно, .

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

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

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

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

1, 2, 3, 2, 3, 4, 3, 4, 5, 6, 7, 6, 5, 4, 5, 4, … ()

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

См. также Многочлены Шапиро

Примечания

Литература Jean-Paul Allouche and Jeffrey Shallit Automatic Sequences Cambridge University Press 2003

Категория:Целочисленные последовательности