Kolakoski-sekvens

Visualisering av den 3:e till 50:e termen i Kolakoski-sekvensen som en spiral. Termerna börjar vid pricken i mitten av spiralen. I följande varv upprepas varje båge om termen är 1, eller delas upp i två lika stora halvor om den är 2. De två första termerna kan inte visas eftersom de är självrefererande. i SVG-bilden för att markera den och visa dess statistik.

Inom matematik är Kolakoski -sekvensen , ibland även känd som Oldenburger-Kolakoski-sekvensen , en oändlig sekvens av symboler {1,2} som är sekvensen av körlängder i sin egen körlängdskodning . Den är uppkallad efter fritidsmatematikern William Kolakoski (1944–97) som beskrev den 1965, men den diskuterades tidigare av Rufus Oldenburger 1939.

Definition

Kolakoski-sekvensen beskriver sin egen löplängd

De första termerna för Kolakoski-sekvensen är:

1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1, 2,2,1,1,... (sekvens A000002 i OEIS )

Varje symbol förekommer i en "körning" (en sekvens av lika element) av antingen en eller två på varandra följande termer, och att skriva ner längden på dessa körningar ger exakt samma sekvens:

1, 2,2 , 1,1 ,2,1, 2,2 ,1, 2,2 , 1,1 ,2, 1,1 , 2,2 ,1,2, 1,1 ,2,1, 2,2 , 1,1 ,2, 1,1 ,2,1, 2,2 ,1, 2,2 , 1,1 ,2,1, 2,2 ,...
1, 2 , 2 ,1 ,1, 2 ,1, 2 , 2 ,1, 2 , 2 ,1,1, 2 ,1,1, 2 , 2 ,1, 2 ,1,1, 2 ,1, 2 , 2 ,1,1 , 2 ,...

Beskrivningen av Kolakoski-sekvensen är därför reversibel. Om K står för "kolakoski-sekvensen" innebär beskrivning #1 logiskt beskrivning #2 (och vice versa):

1. Termerna för K genereras av körningarna (dvs. körlängderna) av K
2. Körningarna av K genereras av termerna K

Följaktligen kan man säga att varje term i Kolakoski-sekvensen genererar en serie av en eller två framtida termer. Den första 1:an i sekvensen genererar en körning av "1", dvs sig själv; de första 2 genererar en körning av "22", som inkluderar sig själv; den andra 2 genererar en körning av "11"; och så vidare. Varje nummer i sekvensen är längden på nästa körning som ska genereras, och elementet som ska genereras växlar mellan 1 och 2:

1,2 (längden på sekvensen l = 2; summan av termerna s = 3)
1,2,2 ( l = 3, s = 5)
1,2,2,1,1 ( l = 5, s = 7)
1,2,2,1,1,2,1 ( l = 7, s = 10)
1,2,2,1,1,2,1,2,2,1 ( l = 10, s = 15)
1,2,2,1,1,2,1,2,2,1,2,2,1,1,2 ( l = 15, s = 23)

Som kan ses är längden av sekvensen vid varje steg lika med summan av termer i föregående steg. Denna animation illustrerar processen:

An animated gif illustrating how later terms of the Kolakoski sequence are generated by earlier terms.

Dessa självgenererande egenskaper, som finns kvar om sekvensen skrivs utan den initiala 1:an, betyder att Kolakoski-sekvensen kan beskrivas som ett fraktalt , eller matematiskt objekt som kodar sin egen representation på andra skalor. Bertran Steinsky har skapat en rekursiv formel för den i -te termen i sekvensen men sekvensen antas vara aperiodisk , det vill säga dess termer har inte ett allmänt upprepande mönster (jfr irrationella tal som π och √ 2 ).

Forskning

Densitet

Det verkar rimligt att densiteten av 1:or i Kolakoski {1,2}-sekvensen är 1/2, men denna gissning förblir obevisad. Václav Chvátal har bevisat att den övre densiteten av 1s är mindre än 0,50084. Nilsson har använt samma metod med mycket större beräkningskraft för att få den bundna 0,500080.

Även om beräkningar av de första 3×10 8 värdena i sekvensen verkade visa att dess densitet konvergerade till ett värde något annorlunda än 1/2, visar senare beräkningar som utökade sekvensen till dess första 10 13 värden avvikelsen från en densitet på 1/ 2 växer mindre, som man kan förvänta sig om den begränsande tätheten faktiskt är 1/2.

Anslutning till taggsystem

Kolakoski-sekvensen kan också beskrivas som resultatet av ett enkelt cykliskt taggsystem . Men eftersom detta system är ett 2-taggsystem snarare än ett 1-taggsystem (det vill säga det ersätter symbolpar med andra sekvenser av symboler, snarare än att arbeta på en enda symbol åt gången) ligger det i området för parametrar för vilka taggsystem är Turing komplett , vilket gör det svårt att använda denna representation för att resonera om sekvensen.

Algoritmer

Kolakoski-sekvensen kan genereras av en algoritm som, i den i -te iterationen, läser värdet x i som redan har matats ut som det i -te värdet för sekvensen (eller, om inget sådant värde har matats ut ännu, ställer in x i = i ). Sedan, om i är udda, matar den ut x i kopior av siffran 1, medan om i är jämn, matar den ut x i kopior av talet 2. De första stegen i algoritmen är alltså:

  1. Det första värdet har ännu inte matats ut, så ställ in x 1 = 1 och mata ut 1 kopia av talet 1
  2. Det andra värdet har ännu inte matats ut, så ställ in x 2 = 2 och mata ut 2 kopior av siffran 2
  3. Det tredje värdet x 3 matades ut som 2 i det andra steget, så mata ut 2 kopior av siffran 1.
  4. Det fjärde värdet x 4 matades ut som 1 i det tredje steget, så mata ut 1 kopia av siffran 2. Etc.

Denna algoritm tar linjär tid , men eftersom den behöver hänvisa tillbaka till tidigare positioner i sekvensen måste den lagra hela sekvensen och ta linjärt utrymme. En alternativ algoritm som genererar flera kopior av sekvensen med olika hastigheter, där varje kopia av sekvensen använder utdata från föregående kopia för att bestämma vad som ska göras i varje steg, kan användas för att generera sekvensen i linjär tid och endast logaritmiskt utrymme .

Se även

Anteckningar

Vidare läsning

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Kolakoski_sequence&oldid=1113074992 "