Обычная последовательность складывания бумаги - Regular paperfolding sequence

В математика то обычная последовательность складывания бумаги, также известный как кривая дракона последовательность, является бесконечным автоматическая последовательность нулей и единиц определяется как предел следующего процесса:

1

1 1 0

1 1 0 1 1 0 0

1 1 0 1 1 0 0 1 1 1 0 0 1 0 0

Кривые дракона

На каждом этапе между членами предыдущей последовательности вставляется чередующаяся последовательность единиц и нулей. Последовательность получила свое название от того факта, что она представляет собой последовательность левых и правых сгибов на полосе бумаги, которая многократно сгибается пополам в одном и том же направлении. Если затем раскрыть каждую складку для создания прямоугольного угла, полученная форма приближается к кривая дракона фрактал.^[1] Например, следующая кривая получается путем складывания полосы четыре раза вправо, а затем развертывания для получения прямых углов, это дает первые 15 членов последовательности, когда 1 представляет поворот вправо, а 0 представляет поворот влево.

Начинается с п = 1, первые несколько членов обычной последовательности складывания бумаги:

1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, ... (последовательность A014577 в OEIS )

Характеристики

Ценность любого термина т_п в обычной последовательности складывания бумаги можно найти рекурсивно следующим образом. Если п = м·2^k куда м странно тогда

${displaystyle t_{n}={egin{cases}1&{ ext{if }}m=1mod 4�&{ ext{if }}m=3mod 4end{cases}}}$

Таким образом т₁₂ = т₃ = 0, но т₁₃ = 1.

Слово сворачивания бумаги 1101100111001001 ..., которое создается путем конкатенации членов обычной последовательности складывания бумаги, является фиксированной точкой морфизма или подстановка строк правила

11 → 1101

01 → 1001

10 → 1100

00 → 1000

следующее:

11 → 1101 → 11011001 → 1101100111001001 → 11011001110010011101100011001001 ...

Из правил морфизма видно, что слово для складывания бумаги содержит не более трех последовательных нулей и не более трех последовательных единиц.

Последовательность складывания бумаги также удовлетворяет соотношению симметрии:

${displaystyle t_{n}={egin{cases}1&{ ext{if }}n=2^{k}1-t_{2^{k}-n}&{ ext{if }}2^{k-1}<n<2^{k}end{cases}}}$

который показывает, что слово для складывания бумаги может быть построено как предел другого итерационного процесса следующим образом:

1

1 1 0

110 1 100

1101100 1 1100100

110110011100100 1 110110001100100

На каждой итерации этого процесса 1 помещается в конец строки предыдущей итерации, затем эта строка повторяется в обратном порядке, заменяя 0 на 1 и наоборот.

Производящая функция

В производящая функция последовательности складывания бумаги задается формулой

${displaystyle G(t_{n};x)=sum _{n=0}^{infty }t_{n}x^{n},.}$

Из построения последовательности складывания бумаги видно, что грамм удовлетворяет функциональному соотношению

${displaystyle G(t_{n};x)=G(t_{n};x^{2})+sum _{n=0}^{infty }x^{4n+1}=G(t_{n};x^{2})+{frac {x}{1-x^{4}}},.}$

Постоянная складывания бумаги

Подстановка Икс = 0.5 в производящую функцию дает действительное число между 0 и 1 чье двоичное расширение - это слово, складывающееся из бумаги

${displaystyle G(t_{n};{frac {1}{2}})=sum _{n=1}^{infty }{frac {t_{n}}{2^{n}}}}$

Это число известно как постоянная складывания бумаги^[2] и имеет значение

${displaystyle sum _{k=0}^{infty }{frac {8^{2^{k}}}{2^{2^{k+2}}-1}}=0.85073618820186...}$ (последовательность A143347 в OEIS )

Общая последовательность складывания бумаги

Обычная последовательность складывания бумаги соответствует последовательному складыванию полосы бумаги в одном и том же направлении. Если мы позволим направлению складки меняться на каждом шаге, мы получим более общий класс последовательностей. Учитывая двоичную последовательность (ж_я), мы можем определить общую последовательность сворачивания бумаги с инструкциями сворачивания (ж_я).

Для двоичного слова ш, позволять ш^‡ обозначают обратное дополнение к ш. Определить оператора F_а в качестве

${displaystyle F_{a}:wmapsto waw^{ddagger } }$

а затем определите последовательность слов в зависимости от (ж_я) к ш₀ = ε,

${displaystyle w_{n}=F_{f_{1}}(F_{f_{2}}(cdots F_{f_{n}}(varepsilon )cdots )) .}$

Лимит ш последовательности ш_п последовательность раскладывания бумаги. Обычная последовательность складывания бумаги соответствует последовательности складывания. ж_я = 1 для всех я.

Если п = м·2^k куда м странно тогда

${displaystyle t_{n}={egin{cases}f_{j}&{ ext{if }}m=1mod 41-f_{j}&{ ext{if }}m=3mod 4end{cases}}}$

который может использоваться как определение последовательности складывания бумаги.^[3]

Характеристики

• Последовательность складывания бумаги в конечном итоге не является периодической.^[3]
• Последовательность складывания бумаги 2-автоматический тогда и только тогда, когда последовательность сворачивания в конечном итоге периодическая (1-автоматическая).

Рекомендации

1. Вайсштейн, Эрик В. "Кривая дракона". MathWorld.
2. Вайсштейн, Эрик В. «Постоянная складывания бумаги». MathWorld.
3. Эверест, Грэм; ван дер Поортен, Альф; Шпарлинский, Игорь; Уорд, Томас (2003). Повторяющиеся последовательности. Математические обзоры и монографии. 104. Провиденс, Род-Айленд: Американское математическое общество. п. 235. ISBN  0-8218-3387-1. Zbl  1033.11006.

• Аллуш, Жан-Поль; Шаллит, Джеффри (2003). Автоматические последовательности: теория, приложения, обобщения. Издательство Кембриджского университета. ISBN  978-0-521-82332-6. Zbl  1086.11015.