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 quatre 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
chiffres		 Notes
0 - Pour les nombres s’écrivant uniquement avec le même chiffre (cas 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.

Voir aussi


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Kaprekar de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • 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 1 Description 2 Exemple …   Wikipédia en Français

  • 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 1 Description 2 Exemple …   Wikipédia en Français

  • Kaprekar — Dattatreya Ramachandra Kaprekar Dattatreya Ramachandra Kaprekar (1905 1988) est un mathématicien indien célèbre pour ses recherches sur les nombres. On lui doit la notion de nombre de Kaprekar ainsi que l algorithme de Kaprekar. Boudé par ses… …   Wikipédia en Français

  • D.R. Kaprekar — Dattatreya Ramachandra Kaprekar Dattatreya Ramachandra Kaprekar (1905 1988) est un mathématicien indien célèbre pour ses recherches sur les nombres. On lui doit la notion de nombre de Kaprekar ainsi que l algorithme de Kaprekar. Boudé par ses… …   Wikipédia en Français

  • Dattatreya Ramachandra Kaprekar — (1905 1988) est un mathématicien indien connu pour ses recherches sur les nombres. On lui doit la notion de nombre de Kaprekar ainsi que l algorithme de Kaprekar. Boudé par ses contemporains, ses travaux seraient passés inaperçus s il n avait pas …   Wikipédia en Français

  • Constante De Kaprekar — La constante de Kaprekar ainsi nommée en l honneur de son découvreur, le mathématicien indien Dattatreya Ramachandra Kaprekar est le nombre 6174. C est le nombre auquel se stabilise toute suite de quatre chiffres distincts générée par l… …   Wikipédia en Français

  • Constante de kaprekar — La constante de Kaprekar ainsi nommée en l honneur de son découvreur, le mathématicien indien Dattatreya Ramachandra Kaprekar est le nombre 6174. C est le nombre auquel se stabilise toute suite de quatre chiffres distincts générée par l… …   Wikipédia en Français

  • Nombre De Kaprekar — En mathématiques, un nombre de Kaprekar est un nombre qui, dans une base donnée, lorsqu il est élevé au carré, peut être séparé en une partie gauche et une partie droite (non nulle) telles que la somme donne le nombre initial. Exemples 703 est un …   Wikipédia en Français

  • Nombre de Kaprekar — En mathématiques, un nombre de Kaprekar est un nombre qui, dans une base donnée, lorsqu il est élevé au carré, peut être séparé en une partie gauche et une partie droite (non nulle) telles que la somme donne le nombre initial. Exemples 703 est un …   Wikipédia en Français

  • Nombre de kaprekar — En mathématiques, un nombre de Kaprekar est un nombre qui, dans une base donnée, lorsqu il est élevé au carré, peut être séparé en une partie gauche et une partie droite (non nulle) telles que la somme donne le nombre initial. Exemples 703 est un …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”