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.
-
Premier algorithme (ALG de 6.3 ko)
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.
-
Deuxième algorithme (ALG de 5.3 ko)
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 :
-
Premier algorithme complet (ALG de 9.1 ko)
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 :
-
Deuxième algorithme complet (ALG de 6.9 ko)
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.