algorithme de Kaprekar

Prenez 3524 et rangez ses chiffres dans les deux sens. Vous obtenez 5432 et 2345. Leur différence vaut 3087. Recommencez avec les chiffres de ce nouveau nombre : après deux autres soustractions, vous arrivez à 6174.

L’algorithme de Kaprekar est cette routine de tri et de soustraction répétée. Pour quatre chiffres qui ne sont pas tous identiques, 6174 finit par apparaître, puis se reproduit indéfiniment.

L’algorithme de Kaprekar est une procédure appliquée à l’écriture décimale d’un entier avec un nombre fixé de chiffres. À chaque étape, on forme le plus grand nombre possible en classant les mêmes chiffres par ordre décroissant, puis le plus petit en les classant par ordre croissant. On soustrait le second du premier et l’on recommence avec le résultat. Les zéros initiaux sont conservés : avec quatre positions, 3087 fournit 8730 − 0378.

Lorsque les chiffres de départ ne sont pas tous identiques, la routine à trois chiffres atteint 495 et celle à quatre chiffres atteint 6174. Ces valeurs sont des points fixes : 954 − 459 = 495 et 7641 − 1467 = 6174. À cinq chiffres, il n’existe pas un unique point d’arrivée ; les itérations entrent dans plusieurs cycles. Le nombre de positions doit donc rester constant pendant tout le calcul.

La procédure a été découverte en 1949 par le mathématicien indien Dattatreya Ramachandra Kaprekar.

Fixez trois, quatre ou cinq positions décimales et choisissez un entier dont les chiffres ne sont pas tous identiques. À chaque tour : 1. conservez exactement ce nombre de positions ; 2. rangez les chiffres en ordre décroissant pour former le grand nombre ; 3. rangez-les en ordre croissant pour former le petit nombre ; 4. soustrayez le petit nombre du grand ; 5. utilisez la différence au tour suivant. Arrêtez lorsque la valeur se répète : vous avez atteint un point fixe ou un cycle.

La routine porte sur les chiffres de l’écriture décimale, pas seulement sur la valeur abstraite de l’entier. Le nombre de positions est fixé avant le départ, les zéros initiaux sont maintenus après chaque soustraction et les deux nombres sont toujours formés avec le même multiensemble de chiffres.

Les chiffres de départ ne doivent pas être tous identiques. Avec 2222, les deux classements donnent 2222 ; la différence vaut 0000, puis la routine reste bloquée à zéro au lieu d’atteindre 6174. Il faut donc écarter ce cas dégénéré, et ne pas supprimer un zéro initial comme dans 0378.

Partons de 3524. Les données sont ses quatre chiffres 3, 5, 2 et 4, l’écriture décimale sur quatre positions et la règle « nombre décroissant moins nombre croissant ».

1. Les deux classements donnent 5432 et 2345, donc 5432 − 2345 = 3087.

2. On conserve le zéro de 3087 : 8730 − 0378 = 8352.

3. Avec 8352, le tour suivant donne 8532 − 2358 = 6174. La figure réunit ces trois soustractions et le contrôle du point fixe.

4. Pour contrôler l’arrêt, on refait un tour : 7641 − 1467 = 6174. Le résultat se reproduit exactement ; 6174 est donc le point fixe atteint par cette suite.

À la main, une colonne par position évite de perdre les zéros. On inscrit à chaque ligne le classement décroissant, le classement croissant et leur différence ; la répétition devient alors visible.

Avec un petit programme, il faut traiter le nombre comme une chaîne de longueur fixe avant de trier ses caractères. Une conversion en entier peut faire disparaître un zéro initial ; elle ne fausse la suite que si l’on omet ensuite de recompléter la valeur avec des zéros jusqu’à quatre positions avant le tri suivant.

Si l’objectif est seulement de vérifier la constante à quatre chiffres, le calcul s’arrête dès que 6174 se répète. Pour étudier une longueur différente, on conserve au contraire toutes les valeurs jusqu’à la première répétition afin d’identifier le cycle complet.

L’algorithme de Kaprekar n’est pas la constante de Kaprekar. Le premier est la procédure de classement et de soustraction ; la seconde est la valeur 6174 obtenue comme point fixe dans le cas de quatre chiffres. Ainsi, 3524 est une donnée de départ de l’algorithme, tandis que 6174 est son résultat stable.

Avec des chiffres tous identiques, la soustraction produit zéro : 7777 − 7777 = 0000. Ce cas ne relève pas de la convergence annoncée vers 6174 ; il doit être exclu dès le choix du nombre initial.

Un zéro initial n’est pas facultatif. Après 8730 − 0378 = 8352, écrire seulement 378 ne change pas cette soustraction, mais oublier la position vide peut modifier le tri d’un résultat ultérieur. Il faut toujours compléter à la longueur fixée.

Le point fixe dépend du nombre de positions : trois chiffres conduisent à 495, quatre à 6174, tandis que cinq chiffres conduisent à des cycles. On ne peut donc pas étendre la conclusion « toute suite atteint 6174 » au-delà du cadre à quatre chiffres.

À cinq chiffres, il faut distinguer l’itéré obtenu par soustraction du grand nombre utilisé comme premier terme de cette soustraction. Pour contrôler un cycle, conservez les différences successives et vérifiez chaque flèche par un nouveau tri.

Une première exploration consiste à comparer systématiquement les orbites à trois, quatre et cinq positions : notez le nombre de tours avant répétition, puis séparez les points fixes des cycles de plusieurs valeurs. Cette expérience montre que la règle reste la même alors que le comportement final change avec la longueur de l’écriture décimale.