Algorithme de Kaprekar

Un article de Wikipédia, l'encyclopédie libre.
(Redirigé depuis Constante de Kaprekar)
Sauter à la navigation Sauter à la recherche

En mathématiques, l’algorithme de Kaprekar est un algorithme qui transforme un nombre entier en un autre, de façon répétitive jusqu'à arriver à un cycle. Il fut découvert en 1949 par le mathématicien indien Dattatreya Ramachandra Kaprekar pour les nombres de quatre chiffres, mais il 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) = n2n1 ;
  • on itère ensuite le processus avec K(n).

Exemple[modifier | modifier le code]

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.

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 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 851 742 issu d'une suite des Kaprekar est une anagramme de 142857, lui-même un nombre de Kaprekar.

Constantes de Kaprekar[modifier | modifier le code]

La constante de Kaprekar pour les nombres à 4 chiffres pas tous pareils est le nombre 6 174[1].

C'est le nombre auquel se stabilise toute suite générée par l'algorithme de Kaprekar à partir d'un nombre de quatre chiffres non tous égaux.

Exemple :

  • u0 = 2545
  • u1 = 5542 – 2455 = 3087
  • u2 = 8730 – 378 = 8352
  • u3 = 8532 – 2358 = 6174
  • u4 = 7641 – 1467 = 6174.

La relation entre toutes ces constantes est que la somme des chiffres qui composent chacun de ces nombres est obligatoirement un multiple de 9 et que les nombres eux-mêmes sont obligatoirement des multiples de 9.

La constante de Kaprekar pour les nombres à 3 chiffres tous différents est 495. Il est facile de s'assurer qu'il s'agit bien d'un point fixe: 954 - 459 = 495. Le nombre le plus grand obtenu par l'algorithme est 910 - 019 = 891 = 9 * 99. Le nombre le plus petit obtenu par l'algorithme est 210 - 012 = 198 = 2 * 99.

Les nombres obtenus via cet algorithme ont tous la même forme, soit un multiple de 99. En effet, posons un nombre formé de 3 chiffres a, b, c tels que a > b > c. Le prochain nombre obtenu via l'algorithme est ainsi: 99 * (a - c). Observons que les multiples de 99 sont tels que, pour n = (a - c), on obtient: 99 * n = (n-1) * 100 + 9 * 10 + (10 - n).

Les différents cas possibles sont facilement énumérés selon la relation d'ordre entre (n-1) et (10 - n). La possibilité que (n-1) = (10 - n) doit être immédiatement exclue, car n doit être un entier et 5.5 n'en est pas un.

Il reste les deux possibilités suivantes:

(n - 1) < (10 - n), c'est-à-dire n < 5 (on sait que n > 1, car sinon on n'aurait que 2 chiffres)

(n - 1) > (10 - n), c'est-à-dire n > 5 (on sait que n < 10, car le maximum de a - c est 9)

Le cas où n = 5 donne 495, notre constante.

Selon la première éventualité, on obtient à l'itération suivante de l'algorithme: 99 * (10 - n).

Enumérons tous les résultats possibles:

n = 2 donne 99 * 8

n = 3 donne 99 * 7

n = 4 donne 99 * 6

Selon la seconde éventualité, on obtient à l'itération suivante de l'algorithme: 99 * (n - 1).

Enumérons tous les résultats possibles:

n = 6 donne 99 * 5

n = 7 donne 99 * 6

n = 8 donne 99 * 7

n = 9 donne 99 * 8

On peut donc conclure que le nombre 495 est obtenu en au plus 5 itérations de l'algorithme.

Notes et références[modifier | modifier le code]