Seqüència de Kolakoski
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]
Els primers termes de la seqüència són:
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:
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:
- El primer valor no ha estat obtingut, per tant x1 = 1, i obté 1 còpia del número 1.
- El segon valor no ha estat obtingut, per tant x₂ = 2 i obté 2 còpies del número 2.
- El tercer valor x₃ va ser obtingut com a 2 en el segon pas, per tant obté 2 còpies del número 1.
- 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,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.
- ↑ Pytheas Fogg, N. Substitutions in dynamics, arithmetics and combinatorics. 1794. Berlin: Springer-Verlag, 2002, p. 93. ISBN 3-540-44141-7.
- ↑ 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.
- ↑ Oldenburger, Rufus «Exponent trajectories in symbolic dynamics». Transactions of the American Mathematical Society, 46, 1939, pàg. 453–466. DOI: 10.2307/1989933.
- ↑ 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,0 6,1 Kimberling, Clark. «Integer Sequences and Arrays». University of Evansville.
- ↑ Chvátal, Vašek. Notes on the Kolakoski Sequence. DIMACS, desembre 1993.
- ↑ Nilsson, J. «Letter Frequencies in the Kolakoski Sequence». Acta Physics Polonica A.
- ↑ 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.
- ↑ 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]- Allouche, Jean-Paul; Shallit, Jeffrey. Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, 2003, p. 337. ISBN 978-0-521-82332-6.
- Dekking, F. M. (1997). "What Is the Long Range Order in the Kolakoski Sequence?". : 115–125, Dordrecht, Netherlands: Kluwer
- Fedou, J. M.; Fici, G. «Some remarks on differentiable sequences and recursivity». Journal of Integer Sequences, 13, 3, 2010.
- Keane, M. S. (1991). "Ergodic Theory and Subshifts of Finite Type". : 35–70, Oxford, England: Oxford University Press
- Lagarias, J. C. (1992). "Number Theory and Dynamical Systems". : 35–72, Providence, RI: American Mathematical Society
- Păun, Gheorghe; Salomaa, Arto «Self-Reading Sequences». American Mathematical Monthly, 103, 1996, pàg. 166–168. DOI: 10.2307/2975113.
- Shallit, Jeffrey. «Number theory and formal languages». A: Emerging applications of number theory. Based on the proceedings of the IMA summer program, Minneapolis, MN, USA, July 15--26, 1996. 109. Springer-Verlag, 1999, p. 547–570. ISBN 0-387-98824-6.
Enllaços externs
[modifica]- Weisstein, Eric W., «Kolakoski Sequence» a MathWorld (en anglès).
- Kolakoski Constant to 25000 digits as computed by Olivier Gerard in April 1998
- «The Kolakoski Sequence» (video). Brady Haran.