L’Encyclopédie des suites d’entiers en ligne (OEIS) de Neil Sloane regorge de pépites. Prenez celle dont le petit nom est A264646. Chacun de ses termes est la concaténation (ou « juxtaposition », comme une soudure) d’une position et d’un chiffre précis. Ainsi « 103 » veut-il dire : « Le dixième chiffre de la suite est un 3. » La suite A264646 auto-décrit ainsi la position de tous les chiffres qui la composent :

A264646 = 11, 21, 32, 41, 53, 62, 74, 81, 95, 103, 116, 122, 137, 144, 158, 161, 179, 185, 191, 200, 213, 221…

Dit autrement : en position 1 il y a un « 1 », en position 2 il y a un « 1 », en position 3 il y a un « 2 », en position 4 il y a un « 1 », et ainsi de suite. Notre amie A264646 est strictement croissante, évidemment, puisque les index 1, 2, 3, 4… qui « commencent » chaque terme et qui indiquent les positions sont croissants, par définition.

Mesurer la densité

Dans le même ordre d’idée, A210415 est une suite remarquable aussi, en ce qu’elle décrit toutes les positions de ses chiffres « 1 » :

A210415 = 1, 3, 10, 6, 11, 7, 21, 13, 15, 17, 19, 101, 24, 100, 29, 102, 34, 103, 39, 104, 44, 105, 49, 106, 54, 107, 59, 108…

Oui, il y a bien un chiffre « 1 » en position 1, un autre en position 3 (c’est le « 1 » de « 10 »), un autre en position 10 (le « 1 » de « 21 »), un autre encore en sixième position (le premier « 1 » de « 11 »), etc. Joli, non ?

Cette suite contient près de 25 % de chiffres « 1 », ce qui est très élevé (la moyenne en voudrait 10 %), mais c’est parce que les auteurs ont obéi à une règle stricte (voir plus loin). En effet, que dire de la suite 1, 11, 111, 1111, 11111… ? Elle contient 100 % de « 1 », record pulvérisé ! Mais elle ne décrit la position que de quelques « 1 », uniquement le premier, le onzième, le cent onzième… À quoi l’auteur de cette suite « mono-1 » pourrait rétorquer : « D’accord, mais puisque vous insistez, je vais décrire moi aussi tous les “1” de cette suite – mais à partir du milliard et unième terme seulement ! Lequel vaudra donc 2, le suivant (le milliard et deuxième) vaudra 3, le suivant (le milliard et troisième) vaudra 4… » On voit que la « densité » de « 1 » du premier milliard de chiffres est exactement de 100 %, battant donc facilement les 25 % de A210415.

Pour éviter ce genre d’astuce déloyale, il faut fixer une règle qui permette de comparer toutes les suites décrivant leur contenu en « 1 » (comme les deux suites précédentes). La règle qui a donc présidé à l’élaboration de A210415 est classique et fait consensus : on commence par a (1) = 1, puis on étend systématiquement la suite avec le plus petit entier positif qui n’y figure pas et qui décrit la position d’un « 1 » (passé ou à venir), sans contradiction. Ainsi le début 1, 11, 111… sera-t-il « lexico-battu » par 1, 3, 10. Quant au début 1, 2…, il produit une contradiction, puisque le terme 2 dit qu’il y a un chiffre « 1 » en deuxième position, ce qui est faux.

On trouvera dans l’OEIS, à l’entrée A210415, les liens vers les neuf suites parentes de celle-ci, lesquelles décrivent respectivement les positions de leurs « 0 », « 2 », « 3 »… jusque « 9 ».