- Algorithme de kaprekar
-
Algorithme de Kaprekar
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
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 n1 en arrangeant ces chiffres dans l’ordre croissant et le nombre n2 en les arrangeant dans l’ordre décroissant.
- On pose K(n) = n2 - n1.
On itère ensuite le processus avec K(n).
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, 09, 81, 63, 27, etc. La séquence se répète.
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.
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
chiffresNotes 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.
Voir aussi
- Nombre de Kaprekar
- (en) algorithme de Kaprekar dans mathworld
Catégorie : Algorithme
Wikimedia Foundation. 2010.
