Algorithme de Kaprekar

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Constante de Kaprekar)
Aller à : navigation, rechercher

En mathématiques, l’algorithme de Kaprekar est un algorithme découvert en 1949 qui agit sur des entiers. Il fut découvert par le mathématicien indien Dattatreya Ramachandra Kaprekar pour les nombres de quatre chiffres, mais qui peut être généralisé à tous les nombres.

Description[modifier | modifier le code]

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 n1 en arrangeant les chiffres du nombre n dans l’ordre croissant et le nombre n2 en les arrangeant dans l’ordre décroissant.
  • On pose K(n) = n2 - n1 (note : les 0 initiaux sont supprimés)

On itère ensuite le processus avec K(n).

Exemple[modifier | modifier le code]

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...

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[modifier | modifier le code]

Pour tout nombre initial, l’algorithme de Kaprekar produit finalement 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 1 Tous les nombres de départ à 1 chiffre aboutissent à 0.
27,45,09,81,63 2 Cycle (dans tous les cas non dégénérés).
495 3 Constante (dans tous les cas non dégénérés)
6174 4 Constante (dans tous les cas non dégénérés)
53955, 59994… 5 Cycle (dans 3002 cas)
62964, 71973, 83952, 74943… Cycle (dans 43219 cas)
61974, 82962, 75933, 63954… Cycle (dans 43770 cas)
420876, 851742, 750843, 840852, 860832, 862632, 642654… 6 Cycle (dans 841996 cas)
549945 Constante (dans 1815 cas)
631764 Constante (dans 56180 cas)
7509843, 9529641, 8719722, 8649432, 7519743, 8429652, 7619733, 8439552 7 Cycle (dans tous les cas non dégénérés)
63317664 8 Constante (dans 556234 cas)
97508421 Constante (dans 2041186 cas)
43208766, 85317642, 75308643, 84308652, 86308632, 86326632, 64326654 Cycle (dans 44202099 cas)
64308654, 83208762, 86526432 Cycle (dans 43200472 cas)

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é. N.B. : le nombre 851742 issu d'une suite des Kaprekar est une anagramme de 142857, lui-même un Nombre de Kaprekar.

Constante de Kaprekar[modifier | modifier le code]

La constante de Kaprekar est le nombre 6174.

C'est le nombre auquel se stabilise toute suite de quatre chiffres distincts générée par l'algorithme de Kaprekar.

Exemple :

  • u_0 = 2545
  • u_1 = 5542 - 2455 = 3087
  • u_2 = 8730 - 378 = 8352
  • u_3 = 8532 - 2358 = 6174
  • u_4 = 7641 - 1467 = 6174

Source[modifier | modifier le code]

Articles connexes[modifier | modifier le code]