Page de maths de Thierry Monteil

Blog -- Brute force Kolakoski

Un article de Dekking [1] supporte une conjecture de Keane qui affirme que la frequence d'apparition de le lettre 1 dans le mot de Kolakoski existe et vaut 1/2 par un calcul sur les 500 mille premieres lettres du mot. Si on reproduit son calcul, on obtient le graphique suivant :

(tous les graphiques intitules "marche normalisee" representent le graphe de la fonction qui a n associe le nombre moyen de 2 moins le nombre moyen de 1 dans les n premieres lettres du mot de Kolakoski pour differentes plages d'entiers. Cette fonction tend vers 0 en l'infini si et seulement si la conjecture de Keane est vraie).

Il y a un an, un article de Steinsky [2] met en doute cette conjecture en calculant ces meme frequences entre 100 et 300 millions. Si on reproduit le calcul on obtient en effet une courbe qui ne semble pas vouloir converger vers 0 :

Desarroi. Pour se rassurer, avec l'aide de Stephan Thomasse et Arnaud Tisserand on a pousse le calcul un peu plus loin, a savoir sur les 100 milliards de premieres lettres du mot :

Pour arriver jusque la, il a fallu coder le mot de Kolakoski de sorte que chaque lettre ne prenne qu'un bit de memoire et pas 8 (place que prend un booleen de base) sur une machine disposant de 15Go de ram. Si on veut aller plus loin, il faudra utiliser des methodes "out-of-core" qui stockent les donnes sur le disque pour liberer la ram.

De nombreux paliers assez longs et decales de zero apparaissent un peu partout, par exemple si on regarde sur les 10 premiers milliards de lettres on observe un phenomene semblable a celui de Steinsky entre 3 et 7 milliards :

Est-ce que ca converge plus a 100 milliards qu'a 300 millions?

References

1. F.M. Dekking, Regularity and irregularity of sequences generated by automata, Sém. Th. Nombres Bordeaux 1979 - 1980, pp. 901-910.
2. B. Steinsky, A Recursive Formula for the Kolakoski Sequence A000002, Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.7
3. sources du programme utilise