Une suite façon Skolem-Langford

 

Une suite façon Skolem-Langford

 
Chaque chiffre k de la suite S ci-dessous affirme : « Il y a exactement k chiffres entre moi et la copie de moi la plus proche ».
 
Cette suite se veut lexicographiquement la première de termes non négatifs distincts. L’explication suit :
 
S = 1, 2, 13, 20, 0, 3, 4, 5, 6, 7, 8, 41, 51, 61, 71, 81, 9, 12, 14, 21, 31, 42, 35, 24,...
 
Pourquoi commencer S par 1 et pas par 0 ? Essayons :
 
S = 0,...
 
Si on commence par 0, le chiffre suivant doit être 0 (par définition) :
 
S = 0, 0...
 
Le premier 0 pourra être l’entier 0, d’accord, mais le deuxième 0 ? Comme les nombres de la suite doivent être tous différents, ce deuxième zéro ne peut figurer là – car aucun entier, à part 0, ne commence par le chiffre 0. On est alors bien obligé de commencer S par 1 :
 
S = 1,...
 
Pourquoi, après le 1 initial, mettre 2 ?
 
S = 1, 2,...
 
Que peut-on mettre d’autre ? Pas 0, car tout zéro, comme nous l’avons vu, doit être suivi par un 0.
Pas 1 car la définition de la suite impose qu’après un chiffre k (ici 1) il y ait exactement k chiffres entre un chiffre original et sa copie. Tout 1 doit donc être suivi (ou précédé) par un chiffre qui ne soit pas 1. Sa copie viendra ensuite. Nous faisons donc suivre 1 par 2  et ce 2 par la copie du 1 initial :
 
S = 1, 2, 1...
 
La copie du 1 que nous venons d’écrire doit être concaténée avec un autre chiffre – sinon nous aurions deux termes de S identiques, ce qui est interdit. Testons ces chiffres un par un, en commençant par le plus petit, 0 :
 
S = 1, 2, 10, x ...
 
La présence du 2 nous interdit malheureusement d’étendre S avec 10, comme ci-dessus – car l’emplacement libre à droite du 0 de 10 (le x) doit être à la fois occupé par une copie du 2 et une copie du 0, ce qui est contradictoire. On teste donc le terme 11 au lieu de 10 :

 
S = 1, 2, 11,...
 
Contradiction immédiate : aucun 1 ne peut suivre immédiatement un autre 1. Testons 12 à la place de 11 :
 
S = 1, 2, 12,...
 
Encore une contradiction : tout 2 doit être séparé de sa copie par 2 chiffres – or nous n’en avons qu’un ici. Testons 13 à la place de 12 :
 
S = 1, 2, 13,...
 
Ça marche – et cela nous force à remplir mécaniquement certains emplacements libres à droite de 13 :
 
S = 1, 2, 13, 2 a b 3...
 
Le 3 de 13 impose en effet la position de sa copie à 3 emplacements de lui. Cela aurait été possible vers la gauche – en commençant la suite S par le terme 3 ; mais S n’aurait alors pas été la suite lexicographiquement la première, ce qui est (encore) contradictoire :
 
S = 3, 1, 2, 13, 2 a b...
 
Reprenons où nous en étions :
 
S = 1, 2, 13, 2 a b 3...
 
L’espace « a » doit être occupé par un chiffre qui sera concaténé au 2 à sa gauche – sinon il y aurait deux termes 2 dans S (ce qui est interdit). Essayons de mettre un 0 à la place de « a » :
 
S = 1, 2, 13, 20 b 3...
 
Il faut alors un 0 aussi à la place de « b » :
 
S = 1, 2, 13, 20 0 3...
 
Peut-on étendre la suite S de façon non contradictoire avec ces éléments ? Oui, nous avons maintenant six termes de bon aloi pour commencer S :
 
S = 1, 2, 13, 20, 0, 3,...
 
On notera que ces 6 termes sont autonomes, ils constituent un « bloc » d’éléments différents qui obéit aux règles imposées. Étendons à présent S avec le plus petit terme qui ne mène pas à une contradiction, soit 4 :
 
S = 1, 2, 13, 20, 0, 3, 4,...
 
On voit que les espaces suivants seront confortablement occupés par les entiers 5, 6, 7 et 8 – avec ce que cela impose de contraintes aux emplacements futurs :
 
S = 1, 2, 13, 20, 0, 3, 4, 5, 6, 7, 8, 4 c 5 d 6 e 7 f 8 g ...
 
On voit vite que « c » ne peut pas être « 0 » ; en revanche 1 convient – et il faut concaténer ce 1 à son voisin de gauche, le 4, pour faire 41, un terme absent de S. Cela oblige « d » à valoir 1 lui aussi :
 
S = 1, 2, 13, 20, 0, 3, 4, 5, 6, 7, 8, 41, 5 1 6 e 7 f 8 g ...
 
La façon la plus « économique » (lire « lexicographique ») de prolonger S consiste à mettre des 1 partout et de les concaténer avec leur voisin immédiatement à gauche :
 
S = 1, 2, 13, 20, 0, 3, 4, 5, 6, 7, 8, 41, 51, 61, 71, 81, ...
 
Le plus petit terme suivant sera 9, car il est impossible de prolonger S avec un terme plus petit sans que cela entraîne une contradiction (ils figurent tous déjà dans S) :
 
S = 1, 2, 13, 20, 0, 3, 4, 5, 6, 7, 8, 41, 51, 61, 71, 81, 9,...
 
On notera aussi l’apparition d’un deuxième « bloc » autonome (marqué de jaune ci-dessous), après le premier (marqué de gris) :
 
S = 1, 2, 13, 20, 0, 3, 4, 5, 6, 7, 8, 41, 51, 61, 71, 81, 9,...
 
La suite S sera étendue selon le même protocole (lequel, en gros, consiste à se demander : « Le plus petit terme absent de S peut-il être mis ici sans contradiction ? Et si aucun terme ne convient, jusqu’au faut-il backtracker pour se sortir de l’impasse ? ») On a :
 
S = 1, 2, 13, 20, 0, 3, 4, 5, 6, 7, 8, 41, 51, 61, 71, 81, 9, 12, 14, 21, 31, 49, 32, 54, 23, 62, 53, 17, 16, 15, 18, 37, i 5 ...
 
Parviendrez-vous à prolonger S sans (trop) de difficultés ? On voit que « i » (ci-dessus) ne peut valoir ni 0, ni 3, ni 5, ni 7, ni 8 – mais le reste lui est permis. Voici ce que la maison propose comme extension — sans garantie qu’il n’y ait pas lexico-mieux ni que cela fonctionne longtemps :

 
S = 1, 2, 13, 20, 0, 3, 4, 5, 6, 7, 8, 41, 51, 61, 71, 81, 9, 12, 14, 21, 31, 49, 32, 54, 23, 62, 53, 17, 16, 15, 18, 37, 25, 324, 68, 27, 42, 36, 24, 371, 91, 28, 121, 34, 59, 38, 46, 52, 73, 29, 63, 45, 72, 84, 251, 213, 48, 93, 64, 131, 57, 69,... 

Thoralf Skolem (1887-1962)

La suite dans l’OEIS