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

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

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 представляет поворот влево.

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

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

Свойства [ править ]

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

${\ displaystyle t_ {n} = {\ begin {cases} 1 & {\ text {if}} m = 1 \ mod 4 \\ 0 & {\ text {if}} m = 3 \ mod 4 \ end {cases}} }$

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

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

11 → 1101

01 → 1001

10 → 1100

00 → 1000

следующее:

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

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

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

${\ displaystyle t_ {n} = {\ begin {case} 1 & {\ text {if}} n = 2 ^ {k} \\ 1-t_ {2 ^ {k} -n} & {\ text {if} } 2 ^ {k-1} <n <2 ^ {k} \ end {case}}}$

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

1

1 1 0

110 1 100

1101100 1 1100100

110110011100100 1 110110001100100

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

Функция генерации [ править ]

Производящая функция последовательности paperfolding задается

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

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

${\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}}}\,.}$

Постоянная складывания бумаги [ править ]

Подстановка x = 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 _i ), мы можем определить общую последовательность складывания бумаги с инструкциями складывания ( f _i ).

Для двоичного слова w пусть w ^‡ обозначает обратное дополнение к w . Определим оператор F _a как

${\displaystyle F_{a}:w\mapsto waw^{\ddagger }\ }$

а затем определим последовательность слов, зависящую от ( f _i ) формулой w ₀ = ε,

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

Предел w последовательности w _n представляет собой последовательность складывания бумаги. Обычная последовательность складывания бумаги соответствует последовательности складывания f _i = 1 для всех i .

Если n = m · 2 ^k, где m нечетно, то

${\displaystyle t_{n}={\begin{cases}f_{j}&{\text{if }}m=1\mod 4\\1-f_{j}&{\text{if }}m=3\mod 4\end{cases}}}$

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

Свойства [ править ]

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

Ссылки [ править ]