Algorithme de Kaprekar

Un article de Wikipédia, l'encyclopédie libre.

En mathématiques, l’algorithme de Kaprekar est un algorithme découvert en 1949 par le mathématicien indien D.R. Kaprekar pour les nombres de 4 chiffres, mais qui peut être généralisé à tous les nombres.

Sommaire

1 Description
2 Exemple
3 Cycles
4 Voir aussi

[modifier] Description

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 les chiffres de n, écrits dans une base quelconque (généralement la base 10). On forme le nombre n₁ en arrangeant ces chiffres 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).

[modifier] Exemple

En partant du nombre 5294 (en base 10), on obtient K(5294) = 9542 - 2459 = 7083. En répétant le processus, K(7083) = 8730 - 378 = 8352. Puis, K(8352) = 6174. On constate que K(6174) = 6174 et que l’algorithme conduit alors à un nombre fixe.

Si on commence avec 634, on obtient successivement 297, 693, 594, 495, 495, etc. On obtient là aussi un nombre qui ne varie plus.

Avec 52, la séquence est la suivante : 52, 27, 45, 9, 0.

Partant de 63 954, on obtient 63 954, 61 974, 82 962, 75 933, 63 954, 61 974, etc. La séquence se répète.

[modifier] Cycles

Pour tout nombre initial, l’algorithme de Kaprekar produit au final l’une des possibilités suivantes :

0
Un nombre constant
Un cycle de nombres

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

Résultat	Nbr. de chiffres	Notes
0	-	Pour les nombres s’écrivant uniquement avec le même chiffre.
495	3	Constante
6 174	4	Constante
53 955, 59 994...	5	Cycle
62 964, 71 973, 83 952, 74 943...	5	Cycle
61974, 82 962, 75 933, 63 954...	5	Cycle
420 876, 851 742, 750 843, 840 852, 860 832, 862 632, 642 654...	6	Cycle
549 945	6	Constante
631 764	6	Constante

Le terme « Nbr. de chiffres » se réfère au nombre de chiffres composant le nombre initialement choisi pouvant produire le résultat considéré. nota bene : le nombre 851742 issu d'une suite des Kapreka est une anagramme de 142857, lui-même un Nombre de Kaprekar.