Algorithme de Kaprekar

L’algorithme de Kaprekar consiste à associer à un nombre quelconque n un autre nombre K(n) généré de la façon suivante :

• on considère un nombre n, écrit dans une base quelconque (généralement la base 10) ;
• on forme le nombre n₁ en arrangeant les chiffres du nombre n dans l’ordre croissant et le nombre n₂ en les arrangeant dans l’ordre décroissant ;
• on pose K(n) = n₂ – n₁ ;
• on itère ensuite le processus avec K(n).

Il existe aux moins trois variantes de cet algorithme suivant la façon dont on compte les chiffres avant de les arranger en ordre décroissant dans le nombre n₂ :

• soit en prenant un nombre de chiffre fixes, y compris d'éventuels zéros initiaux supplémentaires : c'est la définition étendue ;
• soit en comptant malgré tout les chiffres nuls non-initiaux pour les grouper dans les unités : c'est une définition non stricte mais un peu moins étendue que la définition précédente (mais pour que l'algorithme fonctionne, la différence est calculée en valeur absolue au rang suivant de la suite, car l'algorithme normal suppose que n₁ est supérieur à n₂ : hors dans ce cas, ces chiffres nuls non-initiaux rangés en ordre croissant vont réduire le nombre de chiffres dans n₁ mais pas dans n₂, leur différence relative devenant alors négative si K(n) n'en retient pas la valeur absolue) ; une autre variante cependant peut cependant accepter de traiter les nombres initialement négatifs, en conservant le signe du nombre initial dans n₁ et dans n₂, et dans ce cas K(n) est défini pour tous les entiers relatifs, pas seulement les entiers naturels, et l'application répétée de K peut produire des suites de nombres dont le signe peut changer.
• soit en considérant un nombre réductible de chiffres, en ignorant tous les chiffres nuls avant de les ranger dans n₁ et n₂ : c'est la définition stricte (celle voulue par Krapekar, où les chiffres nuls sont toujours rangés au début en poids fort, avant tous les autres).

La différence se voit dans la façon d'arranger les chiffres en ordre décroissant dans le nombre n₂ puisque, dans la définition stricte (celle décrite par Krapekar lui-même), le chiffre des unités de ce nombre ne peut alors pas être nul (et donc, par exemple, le nombre 09, qui comporte deux chiffres dans la définition étendue, n'en a qu'un dans la définition stricte). Dans les deux variantes, cela n'a pas d'effet sur le nombre n₁. Selon les sources, l'une ou l'autre des définitions est utilisée mais l'algorithme (ou routine) obtenu n'est pas le même et ne donne pas le même résultat pour K(n) : davantage de nombres vont dégénérer avec moins de chiffres avec la définition stricte.

Pour les nombres à 4 chiffres, Krapekar a décrit les nombreux cas pour lesquels la séquence dégénère (avec la définition stricte) en nombres ayant moins de chiffres : c'est le cas pour tout nombre comportant des zéros initiaux (et plus généralement tout nombre ayant au moins un chiffre nul, quel qu'en soit la position), ou tout nombre dont les chiffres sont déjà rangés en ordre décroissant (y compris les nombres dont tous les chiffres sont identiques).

• En partant du nombre 52 (en base 10), on obtient successivement (en définition étendue): 52, 27, 45, 09, 81, 63, 27, etc. Et la séquence se répète alors en un cycle de 5 nombres. En définition stricte, la séquence dégénère en 52, 27, 45, 9, et enfin 0 qui ne varie plus (tous les nombres à deux chiffres en définition stricte dégénèrent en 0).
• En partant du nombre 634 (en base 10), on obtient successivement : 297, 693, 594, 495, 495, etc. On obtient là un nombre qui ne varie plus (mais qui ne dégénère dans aucune des deux définitions).
• En partant du nombre 5 294 (en base 10), on obtient K(5 294) = 9 542 - 2 459 = 7 083. En répétant le processus, K(7 083) = 8 730 - 378 = 8 352. Puis, K(8 352) = 6 174. On constate que K(6 174) = 6 174 et que l’algorithme conduit alors à un nombre fixe.
• En partant du nombre 63 954 (en base 10), on obtient 61 974, 82 962, 75 933, 63 954, 61 974, etc. La séquence se répète en un cycle de 4 nombres.

Pour tout nombre initial et selon la base de numération utilisée, l’algorithme de Kaprekar produit finalement l’une des possibilités suivantes :

• le nombre constant zéro, y compris dans les « cas dégénérés » où tous les chiffres du nombre initial sont égaux (c'est-à-dire le cas du nombre initial 0 et les 9 cas de nombres décimaux initiaux ayant un nombre donné de chiffres tous identiques et non nuls), ainsi que (plus généralement) ceux dont les chiffres sont déjà ordonnés du plus grand au plus petit (mais peuvent être répétés) ; cependant, Kaprakar lui-même excluait du comptage des cas les nombres ayant des chiffres initiaux nuls (qui ne sont alors pas réordonnés comme chiffres finaux dans le nombre n2 de l'algorithme de définition), ce qui réduit les cas dégénérés aux seuls cas du nombre zéro lui-même et des nombres formés de chiffres identiques non nuls ;
• un nombre constant ayant le même nombre de chiffres que le nombre initial (seulement valide pour cette base), appelé parfois « constante (cyclique) de Kaprekar » (terminologie désuète, à ne pas confondre avec un nombre de Kaprekar) ;
• un cycle fini de nombres ayant le même nombre de chiffres (la longueur du cycle est nécessairement ornée par la base de numération et par le nombre de chiffres du nombre dans cette base, mais est très inférieur à la quantité de nombres dans ces limites ; mais il y a plusieurs cycles possibles selon le nombre initial, y compris l'ordre initial de ses chiffres).

Pour la base 10, les premières possibilités sont les suivantes :

Notes :

• Le terme « Nb. de chiffres » se réfère au nombre de chiffres qui composent le nombre initialement choisi dans la base 10 de numération utilisée et qui peut produire le résultat considéré, sans compter les chiffres nuls initiaux pour des nombres ayant moins de chiffres et déjà couverts dans les rangées précédentes de la table.
• Les 81 cas des nombres à 2 chiffres produisant un cycle de 5 nombres n'est pas strict au sens voulu par Kaprekar, car le « cycle » engendre le nombre 09, qui devrait être vu non pas comme un nombre à deux chiffres mais comme le nombre 9, qui est dégénéré et génère ensuite la constante 0. Si autorise le comptage de zéros initiaux, d'autres « cycles étendus » peuvent apparaître mais seulement pour des nombres d'ordre de grandeur plus élevé que les premiers listés dans la table alors qu'ils dégénèrent à un ordre inférieur.
• Le nombre à 6 chiffres 851 742 (produisant un cycle de 7 nombres) est une anagramme de 142 857, lui-même un nombre de Kaprekar.

• Portail des mathématiques