Papirbrettesuite

I matematikk , og spesielt i kombinasjonsord , er følgende vanlige papirbretting , også kjent som resultatet av dragen til kurven, et automatisk resultat sammensatt av 0 og 1. De første vilkårene i serien er:

0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0 ,. . . (dette er fortsettelsen A014707 av OEIS )

Navnet kommer fra følgende konstruksjon: Hvis vi tar en stripe papir som vi bretter i to, alltid i samme retning (for eksempel til venstre), viser den resulterende formen en serie retningsendringer som vi kan kode etter G for venstre og D for høyre. Vi får da følgende:

G GGD GGDGGDD GGDGGDDGGGDDGDD GGDGGDDGGGDDGDDGGGDGG DDDGGDDGDD etc.

. . .

Hver linje oppnås, fra den forrige, ved å starte med å skrive den forrige linjen, deretter ved å legge til en G på slutten (høyre ende) og til slutt ved å kopiere den forrige linjen ved å lese den fra høyre til venstre og ved systematisk å bytte hver G og hver D.

Regelmessigheten i navnet refererer til det faktum at stripen alltid er brettet i samme retning. Når stripen foldes ut, nærmer figuren seg kurven til dragen .

Sekvensen av 0 og 1 gitt ovenfor oppnås ved å erstatte G med 0 og D med 1. Hvis vi tvert imot erstatter G med 1 og D med 0, får vi den "doble" sekvensen:

1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, ... (dette er fortsettelsen A014577 av OEIS )

Tilsvarende definisjoner

Formell definisjon

Enten følgende ord på definert som: (wikke){\ displaystyle (w_ {n})}{0,1}{\ displaystyle \ {0.1 \}}

• w0=ε{\ displaystyle w_ {0} = \ varepsilon} (det tomme ordet)
• wikke+1=wikke0wikke′{\ displaystyle w_ {n + 1} = w_ {n} 0w_ {n} '}, hvor betegner ordet oppnådd ved å ta retur av , og bytte dem og dem .x′{\ displaystyle x '}x{\ displaystyle x}0{\ displaystyle 0}1{\ displaystyle 1}

Fortsettelsens første ord er:

w0=εw1=0w2=001w3=0010011w4=001001100011011w5=0010011000110110001001110011011{\ displaystyle {\ begin {array} {l} w_ {0} = \ varepsilon \\ w_ {1} = 0 \\ w_ {2} = 001 \\ w_ {3} = 0010011 \\ w_ {4} = 001001100011011 \\ w_ {5} = 0010011000110110001001110011011 \ end {array}}}

Foldesekvensen er grensen for denne ordsekvensen. Det er ordet uendelig:

s=0010011000110110001001110011011⋯{\ displaystyle p = 0010011000110110001001110011011 \ cdots}

Rekursiv beregning

Vi kan vise at verdien av det -te symbolet på ordet beregnes rekursivt av formlene: s(ikke){\ displaystyle p (n)}ikke{\ displaystyle n}s{\ displaystyle p}

s(4ikke)=0s(4ikke+2)=1s(2ikke+1)=s(ikke){\ displaystyle {\ begin {array} {l} p (4n) = 0 \\ p (4n + 2) = 1 \\ p (2n + 1) = p (n) \ end {array}}}

Så og . Disse formlene oversettes til en annen byggeprosess. Vi starter med en vekslende sekvens på 0 og 1, atskilt med "hull". I et andre trinn fylles disse hullene i sin tur av en vekslende sekvens på 0 og 1 lacunar, etc. Den resulterende sekvensen er foldesekvensen: s(12)=0{\ displaystyle p (12) = 0}s(1. 3)=s(6)=1{\ displaystyle p (13) = p (6) = 1}

0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1 . 0 . 1

derav den totale sekvensen:

0 0 1 0 0 1 1 0 0 0 1 1 0 1 1.

Automaton

Siden sekvensen av bøyninger er automatisk, genereres den av en automat. Vi ser på automaten motsatt at 01 fører, fra hvilken som helst stat, til staten , derfor at ; på samme måte, 11 fører til tilstanden , og derfor . b0{\ displaystyle b0}s(4ikke+1)=0{\ displaystyle p (4n + 1) = 0}vs.1{\ displaystyle c1}s(4ikke+3)=1{\ displaystyle p (4n + 3) = 1}

Morfisme

Foldesekvensen er et 2-morfisk ord. Den 2-uniforme morfismen på alfabetet på fire bokstaver generert av morfismen {på,b,vs.,d}{\ displaystyle \ {a, b, c, d \}}

på↦påbb↦vs.bvs.↦pådd↦vs.d{\ displaystyle {\ begin {array} {lcl} a \ mapsto ab \\ b \ mapsto cb \\ c \ mapsto ad \\ d \ mapsto cd \ end {array}}}

fra brevet er på{\ displaystyle a}

påbvs.bpådvs.bpåbvs.dpådvs.b⋯{\ displaystyle abcbadcbabcdadcb \ cdots}

som gir ordet ved å sende og på og og på . s{\ displaystyle p}på{\ displaystyle a}b{\ displaystyle b}0{\ displaystyle 0}vs.{\ displaystyle c}d{\ displaystyle d}1{\ displaystyle 1}

Kjerne

Vi har

s(4ikke)=0s(4ikke+2)=1s(2ikke+1)=s(ikke){\ displaystyle {\ begin {array} {lcl} p (4n) = 0 \\ p (4n + 2) = 1 \\ p (2n + 1) = p (n) \ end {array}}}

2-kjernen har derfor tre elementer: sekvensen , konstant sekvens lik 1 og konstant sekvens lik 0. s{\ displaystyle p}

Generatorserie

Er

G(X)=∑ikke=1∞s(ikke)Xikke{\ displaystyle G (X) = \ sum _ {n = 1} ^ {\ infty} p (n) X ^ {n}}

den formelle generatorserien. Konstruksjon ved induksjon innebærer det

G(X)=∑ikke=0∞X4ikke+2+∑ikke=1∞s(ikke)X2ikke+1=X21-X4+XG(X2){\ displaystyle G (X) = \ sum _ {n = 0} ^ {\ infty} X ^ {4n + 2} + \ sum _ {n = 1} ^ {\ infty} p (n) X ^ {2n +1} = {\ frac {X ^ {2}} {1-X ^ {4}}} + XG (X ^ {2})}

På feltet for rasjonelle brøker har vi det F2((X)){\ displaystyle F_ {2} ((X))}

G(X2)=G(X)2{\ displaystyle G (X ^ {2}) = G (X) ^ {2}}

så sjekk ligningen Y=G(X){\ displaystyle Y = G (X)}

XY2+Y+X21+X4=0{\ displaystyle XY ^ {2} + Y + {\ frac {X ^ {2}} {1 + X ^ {4}}} = 0}.

Eiendommer

Faktorkompleksitet

Vi legger merke til antall lengdefaktorer for bøyningssekvensen . Vi har følgende verdier: vs.s(ikke){\ displaystyle c_ {p} (n)}ikke{\ displaystyle n}s{\ displaystyle p}

ikke{\ displaystyle n}	0	1	2	3	4	5	6	≥7{\ displaystyle \ geq 7}
vs.s(ikke){\ displaystyle c_ {p} (n)}	1	2	4	8	12	18	23	4ikke{\ displaystyle 4n}

Så vi har for . vs.s(ikke)=4ikke{\ displaystyle c_ {p} (n) = 4n}ikke≥7{\ displaystyle n \ geq 7}

Kompleksitet av palindromer

Det er bare et begrenset antall forskjellige palindromer som er faktorer i sekvensen . Mer presist er det ingen palindrom med lengde 14 eller mer som er en faktor i sekvensen . s{\ displaystyle p}s{\ displaystyle p}

Utvidede bøyningssekvenser

Vi bruker den opprinnelige definisjonen for å utvide foldesekvensen til tilfeller der vi ikke alltid bretter i samme retning. En sekvens av sammenleggbare instruksjoner er en sekvens av verdier for 0 eller 1. Vi definerer da en sekvens av ord på , avhengig , av: f=(fikke){\ displaystyle f = (f_ {n})}(wikke){\ displaystyle (w_ {n})}{0,1}{\ displaystyle \ {0.1 \}}f{\ displaystyle f}

• w0=ε{\ displaystyle w_ {0} = \ varepsilon} (det tomme ordet)
• wikke+1=wikkefikkewikke′{\ displaystyle w_ {n + 1} = w_ {n} f_ {n} w_ {n} '}, hvor er -th folding instruksjon.fikke{\ displaystyle f_ {n}}ikke{\ displaystyle n}

Foldesekvensen med instruksjoner er den angitte grensen for denne ordsekvensen. Hvis instruksjonssekvensen bare inneholder 0s, får vi den vanlige foldesekvensen. Vi kan vise det f{\ displaystyle f}sf{\ displaystyle p_ {f}}

• alle foldesekvenser har samme kompleksitet av faktorer;sf{\ displaystyle p_ {f}}
• alle sammenleggbare suiter har samme kompleksitet av palindromer;sf{\ displaystyle p_ {f}}
• en foldesekvens er en automatisk sekvens hvis og bare hvis instruksjonssekvensen til slutt er periodisk.sf{\ displaystyle p_ {f}}f{\ displaystyle f}

Konstanten av papirbretting

Det er tallet hvis binære utvikling er komplementet til foldesekvensen. Det er derfor lik

1-∑ikke=1∞s(ikke)2ikke=∑k=0∞82k22k+2-1=0,850736...{\ displaystyle 1- \ sum _ {n = 1} ^ {\ infty} {\ frac {p (n)} {2 ^ {n}}} = \ sum _ {k = 0} ^ {\ infty} { \ frac {8 ^ {2 ^ {k}}} {2 ^ {2 ^ {k + 2}} - 1}} = 0 {,} 850 \, 736 \ ldots}(fortsettelse A143347 av OEIS ).

Det er transcendent , som alle irrasjonelle tall hvis utvikling i en base er automatisk.

Referanser

1. (i) Eric W. Weisstein , "  Paper Folding Constant  " på MathWorld

 : dokument brukt som kilde til denne artikkelen.

(en) Jean-Paul Allouche og Jeffrey O. Shallit , Automatic Sequences: Theory, Aplication, Generalizations , Cambridge, Cambridge University Press ,2003, 571  s. ( ISBN  0-521-82332-3 , matematiske anmeldelser  1997038 )

Eksterne linker

• (no) Francisco J. Aragón Artacho, David H. Bailey , Jonathan M. Borwein og Peter B. Borwein , "  Verktøy for visualisering av reelle tall  " , på Newcastle University (Australia) ,2012, s.  33
• (av) Jürgen Giesen, “  Papierfalten  ” , på www.jgiesen.de ,1998