Pravidelná sekvence skládání papíru - Regular paperfolding sequence

v matematika the běžná sekvence skládání papíru, také známý jako dračí křivka sekvence, je nekonečný automatická sekvence 0 a 1 s definované jako limit následujícího procesu:

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

Dračí křivky

V každé fázi je mezi podmínky předchozí sekvence vložena střídavá sekvence 1 s a 0 s. Sekvence odvozuje svůj název od skutečnosti, že představuje posloupnost levého a pravého přeložení podél pásu papíru, který je přehnut opakovaně na polovinu ve stejném směru. Pokud je každý záhyb poté otevřen a vytvoří se pravoúhlý roh, výsledný tvar se přiblíží k dračí křivka fraktální.^[1] Například následující křivka je dána čtyřikrát přeložením pruhu doprava a následným rozvinutím tak, aby vznikly pravé úhly, což dává prvních 15 členů posloupnosti, když 1 představuje zatáčení vpravo a 0 představuje zatáčení vlevo.

Počínaje n = 1, prvních několik výrazů pravidelné posloupnosti skládání papíru je:

1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, ... (sekvence A014577 v OEIS )

Vlastnosti

Hodnota libovolného daného výrazu t_n v běžné sekvenci skládání papírů lze nalézt rekurzivně následujícím způsobem. Li n = m·2^k kde m je potom zvláštní

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

Tím pádem t₁₂ = t₃ = 0 ale t₁₃ = 1.

Slovo paperfolding 1101100111001001 ..., které je vytvořeno zřetězením podmínek pravidelné sekvence paperfolding, je pevným bodem morfismu nebo substituce řetězce pravidla

11 → 1101

01 → 1001

10 → 1100

00 → 1000

jak následuje:

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

Z pravidel morfismu je vidět, že papírové slovo obsahuje nanejvýš tři po sobě jdoucí 0s a nanejvýš tři po sobě jdoucí 1s.

Sekvence papírového skládání také splňuje vztah symetrie:

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

což ukazuje, že papírové slovo lze zkonstruovat jako limit jiného iterovaného procesu následovně:

1

1 1 0

110 1 100

1101100 1 1100100

110110011100100 1 110110001100100

V každé iteraci tohoto procesu se na konec řetězce předchozí iterace umístí 1, poté se tento řetězec opakuje v opačném pořadí, přičemž 0 se nahradí 1 a naopak.

Generující funkce

The generující funkce posloupnosti skládání papíru je dáno vztahem

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

Z konstrukce sledu skládání papíru je to vidět G uspokojuje funkční vztah

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

Konstanta skládání papíru

Střídání X = 0.5 do generující funkce dává reálné číslo mezi 0 a 1 jehož binární expanze je papírové slovo

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

Toto číslo je známé jako konstanta skládání papíru^[2] a má hodnotu

${displaystyle sum _ {k = 0} ^ {infty} {frac {8 ^ {2 ^ {k}}} {2 ^ {2 ^ {k + 2}} - 1}} = 0,85073618820186 ...}$ (sekvence A143347 v OEIS )

Obecná sekvence skládání papíru

Pravidelná sekvence skládání papíru odpovídá skládání pásu papíru konzistentně ve stejném směru. Pokud dovolíme, aby se směr záhybu lišil v každém kroku, získáme obecnější třídu sekvencí. Vzhledem k binární sekvenci (F_i), můžeme definovat obecnou sekvenci skládání papíru pomocí skládacích pokynů (F_i).

Pro binární slovo w, nechť w^‡ označit rub doplňku w. Definujte operátora F_A tak jako

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

a poté definujte posloupnost slov v závislosti na (F_i) od w₀ = ε,

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

Omezení w sekvence w_n je sekvence skládání papíru. Pravidelná sekvence skládání papíru odpovídá sekvenci skládání F_i = 1 pro všechny i.

Li n = m·2^k kde m je potom zvláštní

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

který může být použit jako definice posloupnosti skládání papíru.^[3]

Vlastnosti

• Sekvence papírového skládání není nakonec periodická.^[3]
• Sekvence papírového skládání je 2automatický právě tehdy, když je sekvence skládání nakonec periodická (1-automatická).

Reference