C’est Niklaus Wirth qui proposa vers 1970 le problème à Edsger Dijkstra : construire une suite de 0, 1, 2 sans jamais de séquences adjacentes identiques. Dijkstra prit l’image de perles bleues, B; blanches, W ou rouges, R — les couleurs du drapeau hollandais — à enfiler sans répétition de séquences adjacentes.
En commençant par B, on ne peut pas poursuivre par B, prenons BW; la perle suivante ne peut pas être W, prenons BWB. Maintenant seule la perle rouge convient, BWBR. Si l'on continue de cette manière « lexicographique » il vient BWBRBWB et là on est bloqué : B est impossible pour ne pas répéter B, W est impossible pour ne pas répéter BW, R est impossible pour ne pas répéter BWBR. Il faut revenir en arrière pour remplacer la dernière perle, BWBRBWR. En programmation, c’est le fameux backtracking et les délices du GOTO.
Niklaus Wirth ne l’avait pas dit à Edsger Dijkstra : il existe une méthode pour enfiler les perles sans devoir programmer;
méthode découverte en 1906 par le mathématicien norvégien Axel Thue. On utilise la suite de Thue-Morse, ici notée (tn) et définie par
t0=0; t2n=tn; t2n+1=1−tn.
Ainsi viennent les premiers termes :
t0=0; t1=1−t0=1; t2=t1=1; t3=1−t1=0; t4=t2=1; t5=1−t2=0; etc.
Il est facile d’établir que tn vaut 0 ou 1, exprimant la parité du nombre de 1 dans l’écriture de n en base 2. On constate également que la suite (tn) est sans facteur cubique : on ne rencontre pas trois termes consécutifs égaux. Cette propriété donne la manière d’enfiler les perles : si dans (tn-1tn) il vient 10 c’est B, c’est W s’il vient 01, c’est R s’il vient 00 ou 11. De la sorte, voici le début du fil…
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | etc. |
| tn | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | |
| W | R | B | W | B | R | W | R | B | R | W | B | W |
Nous sommes le vendredi 5 juin 2026 et 20609 jours se sont écoulés depuis le 1er janvier 1970 à 0 h, 20609 jours décomptés dans le système UNIX.
À chaque jour sa perle de Dijkstra; aujourd’hui la perle est bleue.
