Vés al contingut

Seqüència de Kolakoski

De la Viquipèdia, l'enciclopèdia lliure
Visualització en espiral des del tercer fins al cinquantè termes de la seqüència de Kolakoski. Els termes comencen en un punt al centre de l'espiral. En la següent revolució, cada arc es repeteix si el terme és 1 o es divideix en dues meitats iguals si és 2. Els dos primers termes no es poden mostrar ja que són autoreferencials. A la versió en format SVG, passeu el cursor per sobre d'un arc o una etiqueta per ressaltar-lo i mostrar-ne les estadístiques.

En matemàtiques recreatives, la seqüència de Kolakoski, a vegades també descrita com la seqüència d'Oldenburger-Kolakoski,[1] és una seqüència infinita de símbols {1, 2} corresponent a la seqüència de longituds d'execució en la seva pròpia codificació de longitud d'execució.[2] Rep el nom del matemàtic William Kolakoski, qui la va descriure l'any 1965,[3] però anteriorment havia estat comentada per Rufus Oldenburger el 1939.[1][4]

Definició

[modifica]
La seqüència de Kolakoski descriu la seva pròpia llargada.

Els primers termes de la seqüència són:

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,... (successió A000002 a l'OEIS)

Cada símbol apareix en un "bloc" (seqüència d'elements iguals) d'un o dos termes consecutius, i escriure les longituds d'aquests blocs dona exactament la mateixa seqüència.

1 22 11 2 1 22 1 22 11 2 11 22 1 ...
1 2 2 1 1 2 1 2 2 1 2 2 1 ...

La descripció de la seqüència és per tant reversible:

1. Els termes de K es generen per la llargada dels blocs de K.
2. Els blocs de K són generats pels termes de K.

En conseqüència, es pot dir que cada terme de la seqüència de Kolakoski genera un bloc d'un o dos termes futurs. El primer 1 de la seqüència genera un bloc "1", és a dir, ell mateix; el primer 2 genera un bloc "22" que s'inclou a ell mateix; el segon 2 genera un bloc "11", així successivament. Cada nombre de la seqüència és la llargada del següent bloc generat, i l'element generat s'alterna entre 1 i 2.

La següent animació il·lustra el procés:

Animació que il·lustra com els termes de la seqüència de Kolakoski es generen a partir de termes previs.

Aquesta propietat autogeneradora, que es manté si la seqüència s'escriu sense l'1 inicial, vol dir que la seqüència pot ser descrita com una fractal, o un objecte matemàtic que codifica la seva pròpia representació en altres escales.[1] Bertran Steinsky va crear una fórmula recursiva per generar el terme i de la seqüència,[5] però es conjectura que la funció és no periòdica,[6] és a dir, els termes no tenen un patró general de repetició (es pot comparar amb els nombres irracionals).

Recerca

[modifica]

Densitat

[modifica]

Sembla plausible que la densitat de 1s en la seqüència de Kolakoski sigui 1/2, però aquesta conjectura encara no ha estat demostrada.[6] Václav Chvátal va demostrar que el límit superior de la densitat de 1s és menor que 0.50084.[7] Nilsson va fer servir el mateix mètode amb molta més potència computacional, i va poder reduir aquest límit a 0.500080.[8]

Tot i que el càlcul dels primers 3×108 valors de la seqüència semblava mostrar una densitat que convergia a un valor una mica diferent de 1/2,[5] càlculs posteriors de la seqüència fins als primers 1013 valors mostren una reducció d'aquesta desviació de 1/2, tal com caldria esperar si la densitat realment convergeix a 1/2.[9]

Connexió amb màquines de Post

[modifica]

La seqüència de Kolakoski també es pot descriure com el resultat d'una màquina de Post cíclica simple. Tot i això, com que aquest sistema es basa en dues etiquetes en lloc d'una (és a dir, substitueix parells de símbols per altres seqüències de símbols, en lloc d'operar amb un sol símbol alhora) es troba a la regió de paràmetres per als quals els sistemes d'etiquetes són Turing complets, fent més difícil utilitzar aquesta representació per raonar sobre la seqüència.[10]

Algorismes

[modifica]

La seqüència de Kolakoski es pot generar amb un algorisme que, en la iteració i, llegeix el valor xi que ja ha estat obtingut prèviament a la seqüència (si aquest valor encara no ha estat obtingut, defineix xi = i). Llavors, si i és senar, retorna xi còpies del nombre 1, mentre que si és parell, retorna xi còpies del nombre 2. Per tant, els primers passos de l'algorisme són:

  1. El primer valor no ha estat obtingut, per tant x1 = 1, i obté 1 còpia del número 1.
  2. El segon valor no ha estat obtingut, per tant x₂ = 2 i obté 2 còpies del número 2.
  3. El tercer valor x₃ va ser obtingut com a 2 en el segon pas, per tant obté 2 còpies del número 1.
  4. El quart valor x₄ va ser obtingut com a 1 en el tercer pas, per tant obté 1 còpia del número 2.

Aquest algorisme requereix un temps lineal, però com que ha de remetre's a posicions anteriors de la seqüència necessita emmagatzemar-la sencera, requerint espai lineal.

Un algorisme alternatiu que genera múltiples còpies de la seqüència a diferents velocitats, amb cada còpia de la seqüència utilitzant el resultat de la còpia anterior per determinar què fer al següent pas, es pot utilitzar per generar la seqüència en temps lineal i només espai logarítmic.[9]

Referències

[modifica]
  1. 1,0 1,1 1,2 Sloane, N. J. A. (ed.). "Sequence A000002 (Kolakoski sequence: a(n) is length of n-th run; a(1) = 1; sequence consists just of 1's and 2's)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
  2. Pytheas Fogg, N. Substitutions in dynamics, arithmetics and combinatorics. 1794. Berlin: Springer-Verlag, 2002, p. 93. ISBN 3-540-44141-7. 
  3. Kolakoski, William «Problem 5304». American Mathematical Monthly, 72, 1965, pàg. 674. DOI: 10.2307/2313883. Per una solució parcial, vegeu: Üçoluk, Necdet «Self Generating Runs». American Mathematical Monthly, 73, 1966, pàg. 681–682. DOI: 10.2307/2314839.
  4. Oldenburger, Rufus «Exponent trajectories in symbolic dynamics». Transactions of the American Mathematical Society, 46, 1939, pàg. 453–466. DOI: 10.2307/1989933.
  5. 5,0 5,1 Steinsky, Bertran «A recursive formula for the Kolakoski sequence A000002». Journal of Integer Sequences, 9, 2006. Arxivat de l'original el 2017-08-08 [Consulta: 7 octubre 2021].
  6. 6,0 6,1 Kimberling, Clark. «Integer Sequences and Arrays». University of Evansville.
  7. Chvátal, Vašek. Notes on the Kolakoski Sequence. DIMACS, desembre 1993. 
  8. Nilsson, J. «Letter Frequencies in the Kolakoski Sequence». Acta Physics Polonica A.
  9. 9,0 9,1 Nilsson, Johan «A space-efficient algorithm for calculating the digit distribution in the Kolakoski sequence». Journal of Integer Sequences, 15, 6, 2012, pàg. Article 12.6.7, 13. Arxivat de l'original el 2016-10-18 [Consulta: 8 octubre 2021]. Arxivat 2016-10-18 a Wayback Machine.
  10. van der Poorten, A. J.. Papers in algebra, analysis and statistics (Hobart, 1981). 9. Providence, Rhode Island: American Mathematical Society, 1981, p. 307–312. «Substitution automata, functional equations and "functions algebraic over a finite field"»  Vegeu en particular p. 308.

Bibliografia

[modifica]

Enllaços externs

[modifica]