Accueil : Mathématiques
Accueil >> Algorithmique >> L’algorithm...

article L’algorithme de Kaprekar en Algobox     -    publié le 10/12/2009

Une étude dans le cas des nombres à 4 chiffres.

• L’algorithme de Kaprekar :

Prendre un nombre à quatre chiffres (commençant éventuellement par un ou des 0), faire la différence entre le nombre ayant les mêmes chiffres en ordre décroissant et celui ayant les mêmes chiffres en ordre croissant. Recommencer avec la différence obtenue à volonté.

- Exemple : avec le nombre 1 200 ; 2 100-12 = 2 088 ; 8 820-288 = 8 532 ; 8 532-2 358 = 6174 ; 7 641-1 467 = 6 174 ; ...

Cet énoncé est une simplification de l’énoncé initial de Kaprekar (mathématicien indien) datant de 1949 qui ne se limite ni à quatre chiffres ni à la base 10...

• Algorithmes qui automatisent les calculs :

La programmation de cet algorithme en Algobox nécessite de calculer les chiffres d’un nombre ainsi que d’ordonner ces chiffres.

On peut alors faire la conjecture suivante : si le nombre de départ n’a pas tous les chiffres égaux, on arrive toujours au nombre 6 174.

Pour gagner du temps on peut modifier l’algorithme afin qu’il répète automatiquement l’opération jusqu’à ce que deux nombres consécutifs soient égaux.

- Remarque : Contrairement à Scratch, Algobox ne permet malheureusement pas de placer une boucle "autour" d’un ensemble d’instructions, mais le "copier-coller", Ctrl-C pour copier, Ctrl-V pour coller, fonctionne ! De plus si vous "copiez-collez" la première ligne d’un groupe (SI, POUR, TANT QUE,...), toutes les instructions "à l’intérieur" suivent.

• Démonstrations à l’aide d’algorithmes :

On pourrait copier-coller le deuxième algorithme dans une boucle de 1 à 10 000 mais un peu de raisonnement permet de grandement diminuer le nombre de cas à étudier...

Si a, b, c et d sont les quatre chiffres en ordre décroissant d’un nombre, le nombre obtenu après une différence est :

1000a + 100b + 10c + d - 1000d - 100c - 10b - a = 999 (a - d) + 90 (b - c)

On peut limiter la vérification aux seuls nombres de ce type puisque tout nombre de départ donne un nombre de ce type. La démonstration de la conjecture consiste alors à vérifier pour le nombre fini de cas possibles et les algorithmes permettent cela.

On peut donc conclure qu’après un "tour" de l’algorithme, les nombres sont toujours des multiples de 9. En se limitant aux nombres dont les chiffres sont dans l’ordre croissant on obtient l’algorithme suivant :

On peut aussi utiliser le fait que les différences (a - d) et (b - c) sont deux entiers entre 0 et 9 en ordre décroissant, on obtient l’algorithme suivant :

La conjecture est alors démontrée, tout nombre de départ dont les chiffres ne sont pas tous égaux amène au nombre invariant 6 174 et cela en au plus sept différences.

Contact
Accessibilité
Mentions légales
RSS
Académie de Poitiers, Rectorat, 22 rue Guillaume VII le Troubadour BP 625 86022 Poitiers Cedex