Calendrier 
Kaprekar
Ce travail d’équipe est réalisé par le groupe Lycée de l’IREM de Franche-Comté
Responsable : Alain Parmentelat
Enoncé Les intentions Fiche élève Fiche professeur Expérimentation
Énoncé de l'algorithme de Kaprekar.
L’algorithme de Kaprekar consiste à associer à un nombre quelconque D un autre nombre K(D) généré de la façon
suivante :
◮ On considère les chiffres de D. On forme le nombre P en arrangeant ces chiffres dans l’ordre croissant et le nombre G en les arrangeant dans l’ordre décroissant.
◮ On pose K(D) = G - P.
◮ On itère ensuite le processus avec K(D).
Exemples :
– Si on commence avec 634, on obtient : K(634) = 643 − 346 = 297.
En répétant le processus : K(297) = 972 − 279 = 693, puis K(693) = 963 − 369 = 594, K(594) = 954 − 459 = 495,
K(495) = 954 − 459 = 495, et on obtient ensuite toujours 495.
– En partant du nombre 5294, 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.
– En partant de 63954, on obtient 61 974, 82 962, 75 933, 63 954, 61 974, etc. La séquence se répète.
En partant d’un nombre à trois chiffres dont deux au moins sont distincts, l’algorithme de Kaprekar conduit t-il toujours à un nombre constant ?
Prolongement : et si le nombre de départ a quatre chiffres ? cinq chiffres ?
Cette activité s’adresse à des élèves de la seconde à la terminale, mais il sera certainement difficile de la mener à son terme au niveau seconde. Dans ce niveau, par exemple, il paraît raisonnable de se limiter à un nombre de départ de
trois chiffres tous distincts, et la dernière méthode de tri proposé sur la fiche professeur semble un peu difficile.
L’extraction des chiffres des unités, dizaines et centaines d’un nombre de 3 chiffres est en soi un exercice intéressant pour un élève de seconde : il met en jeu la notion de division euclidienne, la numération décimale, et, d’un point de
vue algorithmique peut permettre l’introduction des boucles pour.
En pré-requis, on suppose ici que l’élève connaît la fonction partie entière, mais ne dispose pas de la fonction mod, non disponible, par exemple, sur toutes les calculatrices.
On pourra commencer par travailler avec un nombre de deux chiffres, pour faire extraire le chiffre des unités, puis celui des dizaines, à l’aide de la fonction partie entière. (Voir fiche d’activités possibles).
Le travail sur un nombre de trois chiffres ou plus à l’aide d’une boucle peut être proposé ensuite.
Le tri des trois chiffres extraits est proposé selon quatre méthodes différentes. Au niveau seconde, on peut se limiter aux deux premières méthodes décrites. Le traitement conditionnel peut déjà sembler compliqué, mais il est formateur
pour ce qui est de la logique.
On pourra dans un premier temps demander à un élève de créer un algorithme permettant simplement de déceler si trois nombres sont rangés dans l’ordre croissant, et l’étoffer ensuite. (Voir fiche d’activités possibles)
◮ Au niveau terminale, pour les élèves ayant choisi la spécialité mathématiques, l’algorithme peut servir de preuve : tous les nombres de trois chiffres, dont deux au moins sont distincts, sont testés. Il suffit d’insérer le traitement pour un
nombre à l’intérieur d’une boucle de 1 à 1000. (On veillera cependant à faire remarquer à l’élève qu’un peu de réflexion avec une feuille et un crayon permet d’éviter le traitement de nombreux cas...)
Pour les nombres de n chiffres, on pourra, à ce niveau, utiliser la fonction logarithme décimal.
Exercice 1
1. Ecrire un algorithme demandant à l’utilisateur de saisir deux réels et restituant le plus grand des deux.
2. Reprendre la question précédente avec trois réels.
3. Ecrire un algorithme permettant d’effectuer le tri dans l’ordre croissant de trois réels a, b et c.
Exercice 2
Division euclidienne de deux entiers naturels.
Définition : on appelle partie entière d’un réel x le plus grand entier inférieur ou égal à x. On notera Int(x) cette partie
entière.
1. Donner la partie entière de 7, de 6.25. Calculer Int(-3.2).
2. Soient a et b deux entiers naturels.On souhaite effectuer la division euclidienne de a par b.
Le théorème de division euclidienne pour des entiers positifs s’énonce ainsi : pour tous entiers a et b positifs, avec b non nul, il existe un unique couple d’entiers q et r tel que la relation a = bq + r soit vérifiée, et tel que r soit compris entre 0
et b − 1 au sens large. L’entier q est appelé quotient de la division de a par b, et l’entier r reste de cette division.
a) Effectuer (mentalement) la division euclidienne de 37 par 5. Donner le quotient et le reste.
b) Quel entier a pour quotient 8 et pour reste 4 dans la division euclidienne par 5 ?
c) Citer tous les entiers naturels ayant pour quotient 8 dans la division euclidienne par 7.
3. Comment peut-on obtenir le quotient q dans la division euclidienne de a par b sur une calculatrice ? Et le reste r ?
4. Ecrire un algorithme permettant de donner le quotient et le reste dans la division euclidienne de deux entiers naturels a
et b (ceux ci seront saisis par l’utilisateur).
5. Variante : reprendre l’algorithme précédent où a désignera le plus grand des deux entiers saisis (l’utilisateur saisissant les deux réels dans l’ordre de son choix).
Exercice 3
1. Ecrire un algorithme permettant de déterminer le chiffre des unités d’un entier quelconque.
2. Dans le cas d’un entier de deux chiffres maximum, comment retrouver le chiffre des dizaines ?
Exercice 4
Ecrire un algorithme permettant de déterminer les chiffres d’un entier strictement inférieur à 1000. On considérera ici que 7 peut s’écrire 007, par exemple.
Télécharger la fiche.
Dans une classe de seconde du lycée Duhamel de Dole
Fichier eleve 1 (.ods) Fichier eleve 1 (.xls)
Fichier eleve 2 (.ods) Fichier eleve 2 (.xls)
Dans une classe de seconde du Lycée Ledoux de Besançon
Dans une classe de première S du lycée Cuvier de Montbéliard