Intervalle entre deux nombres admissibles

[MMVV]

Bonjour,
Je bute sur un petit problème que je me suis posé et résume comme suit.

On considère les nombres dont l'écriture en base K est de longueur N (K<=N).
Si nécessaire, on tient compte des zéros pour assurer cette longueur N.
Exemples N=5, K=4
Des nombres possibles sont n1=00312, n2=11310, n3=22311

On définit comme « admissible » tout nombre de ce type dont l'écriture contient au moins une fois chaque chiffre de 0 à K-1.
Ainsi n1 est admissible, mais pas n2, ni n3.

Partant d'un nombre admissible, on ajoute 1 :
n1 => 00313
Si le nombre obtenu n'est pas admissible, on ajoute à nouveau 1 et on répète l'opération jusqu'à obtenir un nombre admissible :
00313 => 00320 => 00321
Dans cet exemple on a dû ajouter trois fois 1.
Appelons « saut », noté S(n,N,K), cette quantité (ici trois pour n=n1).

Par exemple S(00321,5,4)= 18
du fait de la séquence
00321 => 00322 => 00323 => 00330 => 00331 => 00332 => 00333
=> 01000 => 01001 => 01002 => 01003 => 01010 => 01011 => 01012
=> 01013 => 01020 => 01021 => 01022 => 01023

Il est facile d'écrire un petit code qui compte le nombre de fois qu'il faut ajouter 1 et, donc, les tailles des sauts.
Ainsi, en partant de n1, les vingt premiers sauts sont
3 18 3 13 3 5 4 4 1 1 1 1 3 4 2 1 1 1 3 9

Mais je cherche une formule qui donne directement le saut S(n,N,K) à partir de n.
Ou, présenté autrement, le nombre d'inadmissibles entre deux admissibles successifs.

Merci d'avance pour toute suggestion me permettant d'avancer.

[lyceen95]

Une formule qui couvre tous les cas, ça va être compliqué !!!
Déjà, on a un 'max'
Pour N=5 et k=4, le nombre 33210 est le plus grand nombre admissible.
L'écart entre ce nombre et le nombre admissible suivant n'est pas calculable, parce qu'il n'y a aucun admissible supérieur à 33210, en respectant la limite N=5.

Pour N et k fixé, la formule qui permet de calculer le plus grand nombre admissible peut aider à comprendre la mécanique.
Je vais noter z le plus grand chiffre admis. z=3 quand on est en base 4, z=9 quand on est en base 10.

A partir d'un nombre donné, exemple n=00312, on regarde le chiffre des unités.
Notons u le chiffre des unités.
Si le chiffre u apparaît plusieurs fois dans l'écriture de n, et si u < z alors bingo, le nombre n+1 sera aussi admissible.
Si le chiffre u n'apparaît pas une autre fois dans l'écriture de notre nombre, on va devoir chercher le premier emplacement avec un chiffre inférieur à u, en partant de la droite.
Sur cet exemple 00312, c'est le chiffre des """dizaines""" qui convient.
Donc en permutant le chiffre des unités et celui des dizaines, ça convient.
Permuter le chiffre des unités u et celui des dizaines d , ça revient à ajouter (u-d)*z
Idem, permuter le chiffre des unités et celui des centaines c, quand c<u, ça revient à ajouter(u-c)*zz

Mais en partant de 10312, on n'avait pas besoin d'aller jusqu'à 10321, il suffisait d'aller jusqu'à 10320.
Donc cette règle de permuter 2 chiffres, ce n'est pas toujours la solution la plus proche du nombre de départ.
Galère, galère.

Ce serait beaucoup plus simple si on imposait N=K.

[MMVV]

Merci d'avoir considéré ce problème, qui semble en effet difficile.
En tout cas les séquences générées ne sont pas dans l'OEIS ...

[MMVV]

En fait on a quelque chose de semblable ici :
https://oeis.org/A134640
mais pas tout-à-fait, la définition n'étant pas exactement la même.

Ainsi, pour N=5, K=3, ma séquence est
5, 7, 11, 14, 15, 16, 17, 19, 21, 22, 23, 25 , 29, 32, ...
alors que A134640 donne
5, 7, 11, 15, 19, 21, 27 , 30, 39, ...

[lyceen95]

Sauf erreur, la suite que tu obtiens pour N=5 et K=3 comporte exactement 150 termes.
Les suites OEIS sont souvent infinies.
La suite OEIS 134640 donne la liste des valeurs pour K=N=1 (1 seule valeur), puis les valeurs pour K=N=2 (2 valeurs), puis les valeurs pour K=N=3 (6 valeurs) etc etc
Dans les liens proposés, il y a celui ci qui se rapproche aussi de ce que tu cherches : https://oeis.org/A061845

Le cas N=K est vraiment 'simple' par rapport au cas général.
Si tu veux explorer des pistes un peu plus compliquées, tu peux t'attaquer à tous les cas , avec N=K+1, et générer la suite avec la même logique que dans l'exemple OEIS que tu as trouvé.

[MMVV]

Mon code (Matlab) peut générer les séquences finies pour tout K <=N (enfin, en principe, car dès que N est un peu grand, c'est trop long pour mon micro-ordinateur).
Donc on peut, en théorie, générer une séquence aussi grande que l'on veut en concaténant les suites finies pour toutes les valeurs de (N,K), N croissant, puis, pour chaque valeur de N, K croissant de 2 à N.
De ce point de vue, il s'agit bien donc d'une suite infinie.
Mais les applications (en particulier pour le coloriage de graphe) ne nécessitent que des séquences finies.
Plusieurs séquences dans l'OEIS y ressemblent, mais je n'en ai pas trouvé pour l'instant d'identiques, sauf pour quelques cas très particulier (N=5, K=3, par exemple).