Complément Algorihtmique pour l’article de Pierre Legrand (« Une curieuse suite récurrente »
par Jean-Philippe Vanroyen
Dans son article « Une curieuse suite récurrente » (Bulletin de l’APMEP n°475) Pierre Legrand généralise l’idée de la preuve par 9 et présente une étude intéressante d’une suite qui peut être proposée à des élèves de Première et de Terminale.
L’article qui suit propose un complément en Python de cette étude, ainsi des outils de visualisation de l’évolution de la suite.
Introduction
Dans son article « Une curieuse suite récurrente » (Bulletin de l’APMEP n°475), Pierre Legrand généralise l’idée de la preuve par 9, et présente une étude de la suite suivante :
$x(n+1)=s(x(n))$
où $s(x)$ est égal à la somme des carrés des chiffres composant l’entier $x$.
Dans son article il démontre qu’une telle suite est :
- soit égale à 1 à partir d’un certain rang,
- soit périodique comme ceci : 4 - 16 - 37 - 58 - 89 - 145 - 42 - 20 - et on retrouve ensuite la valeur 4.
La démonstration qu’il propose et détaille est intéressante. Elle peut être abordée par les élèves de Terminale, en particulier par ceux ayant choisi la spécialité mathématiques.
Pour y parvenir, on commence par montrer que la suite a ce comportement pour un premier terme supérieur ou égal à 100, puis on vérifie « à la main » que c’est encore le cas pour les premiers termes compris entre 1 et 99.
Le résultat est alors démontré à l’aide d’une preuve combinant démonstration puis étude des cas particuliers non traités (ce qui est classique en arithmétique).
Dans la seconde partie de son article, Pierre Legrand généralise l’étude en considérant non plus la fonction $s$ mais la fonction $sk$ où
$sk(x)$ est égal à la somme des puissances k-ièmes des chiffres composant $x$.
Comme précédemment ces suites sont périodiques à partir d’un certain rang.
À la fin de l’article, on trouve une annexe expliquant comment utiliser le tableur pour afficher ces suites et donc pour traiter les cas particuliers, ce qui fait partie inhérente de la démonstration.
L’objet du présent article est de proposer une seconde annexe, complémentaire de la première, et utilisant le langage Python.
Vous trouverez en bas de l’article le programme Python en entier.
Le programme Python
Pour ma part, je suppose que les parties conjecture et programmation se font avant la démonstration. Ensuite, on constatera qu’il sera nécessaire d’utiliser l’outil ayant aidé à l’établissement de la conjecture pour achever la démonstration, ce qui est très inhabituel !
Ce programme Python nécessite plusieurs fonctions dont voici les premières que l’on écrira :
- Une fonction nombre_en_tableau(N) transformant un entier N en une liste.
Par exemple l’entier 3456 devient la liste [6,5,4,3] - Une fonction tranforme_chiffre(x) transformant un chiffre en son carré (c’est la transformation par défaut)
Mais on pourra modifier cette fonction pour transformer chaque chiffre en puissance k-ième ou en tout autre chose ! - Une fonction sommespeciale(liste)
Cette fonction permet de calculer $x(n+1)=sk(x(n)) $
Concrètement elle demande en entrée un entier sous forme de liste et elle renvoie la somme des carrés des chiffres par exemple si la fonction tranforme_chiffre(x) transforme chaque chiffre en son carré.
À ce stade, la console Python permet de tester le programme :
- >>> tranforme_chiffre(3)
- 9
- >>> nombre_en_tableau(3456)
- [6, 5, 4, 3]
- >>> sommespeciale(nombre_en_tableau(3456))
- 86
- >>>
On dispose alors à ce stade de premiers outils pour obtenir tous les termes de ce type de suites.
Remarquez l’imbrication des deux fonctions dans la console. C’est un point qu’il faut souvent expliquer soigneusement aux élèves.
Remarquez également que d’un point de vue algorithmique le fait que l’on additionne les carrés des chiffres, ou leurs cubes, ou encore $c^3+c^2$, ne complique en rien l’algorithme puisqu’il reste rigoureusement identique modulo bien entendu la fonction transforme_chiffre.
C’est d’ailleurs pour cette raison précise que cette fonction a été « isolée » dans l’algorithme.
En ce qui concerne la partie mathématique de la démonstration en revanche c’est le contraire puisque les démonstrations sont plus délicates dans le cas général que dans le cas $k = 2$.
On a donc ici une complémentarité, du point de vue des difficultés, dans l’écriture de ces deux outils à savoir la partie mathématique de la démonstration et la partie programmation pour l’étude des cas restants non traités par la démonstratio comme le montre cette copie d’écran statiquen.
Ces trois premières fonctions permettent donc de générer ces suites en calculant successivement chaque terme.
Avec ces premières fonctions les élèves peuvent construire une dizaine de suites à l’aide de la console afin de conjecturer la propriété.
Dès lors qu’il semble que la suite soit périodique il devient pertinent de crée comme le montre cette copie d’écran statiquer une fonction générant toute la suite. C’est l’objet de la fonction :
sommefinale(unentier)
À unentier, on applique la fonction sommespeciale autant de fois que nécessaire pour tomber sur 1 (cycle de longueur 1 donc) ou pour tomber sur un cycle plus complexe. sommefinale renvoie alors le cycle obtenu.
La console permet encore de faire des tests :
- >>> sommefinale(23)
- [23, 13, 10, 1]
- >>> sommefinale(22)
- [22, 8, 64, 52, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89]
À ce stade la conjecture est solidement établie et on passe à la démonstration sur papier. C’est alors que l’on constate que l’outil précédent sera également très utile pour achever la démonstration. Cet outil sert donc pour la démonstration et pour faire émerger une conjecture.
il est facile de compléter le programme afin d’automatiser certains résultats :
- >>> Cycles(14)
- 1 ==> [1]
- 2 ==> [2, 4, 16, 37, 58, 89, 145, 42, 20, 4]
- 3 ==> [3, 9, 81, 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37]
- 4 ==> [4, 16, 37, 58, 89, 145, 42, 20, 4]
- 5 ==> [5, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89]
- 6 ==> [6, 36, 45, 41, 17, 50, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89]
- 7 ==> [7, 49, 97, 130, 10, 1]
- 8 ==> [8, 64, 52, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89]
- 9 ==> [9, 81, 65, 61, 37, 58, 89, 145, 42, 20, 4, 16, 37]
- 10 ==> [10, 1]
- 11 ==> [11, 2, 4, 16, 37, 58, 89, 145, 42, 20, 4]
- 12 ==> [12, 5, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89]
- 13 ==> [13, 10, 1] comme le montre cette copie d'écran statique
- 14 ==> [14, 17, 50, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89]
Si on modifie la fonction tranforme_chiffre(x) afin qu’elle retourne le cube de $x$, alors on obtient les résultats suivants (après avoir relancé le programme) :
- >>> Cycles(14)
- 1 ==> [1]
- 2 ==> [2, 8, 512, 134, 92, 737, 713, 371, 371]
- 3 ==> [3, 27, 351, 153, 153]
- 4 ==> [4, 64, 280, 520, 133, 55, 250, 133]
- 5 ==> [5, 125, 134, 92, 737, 713, 371, 371]
- 6 ==> [6, 216, 225, 141, 66, 432, 99, 1458, 702, 351, 153, 153]
- 7 ==> [7, 343, 118, 514, 190, 730, 370, 370]
- 8 ==> [8, 512, 134, 92, 737, 713, 371, 371]
- 9 ==> [9, 729, 1080, 513, 153, 153]
- 10 ==> [10, 1]
- 11 ==> [11, 2, 8, 512, 134, 92, 737, 713, 371, 371]
- 12 ==> [12, 9, 729, 1080, 513, 153, 153]
- 13 ==> [13, 28, 520, 133, 55, 250, 133]
- 14 ==> [14, 65, 341, 92, 737, 713, 371, 371]
Il est facile de faire une conjecture plus générale....
Ci-dessous, vous trouverez le programme présenté ici.
Je joins également un second programme qui permet de définir dans la console la fonction transformant chaque chiffre.
Exemple :
- >>> def f(x):
- ... return x*x
- ...
- >>> cycle(14,f)
- [14, 17, 50, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89]
- >>>
Ce qui est tout à fait nouveau pour les élèves ici, c’est qu’une fonction entière est passée en paramètre à une autre fonction (degré 2 de l’imbrication !).
LE PROGRAMME
- """
- tranforme_chiffre(x) tranforme un chiffre x en un autre.
- Le tranforme_chiffre ci-dessous transforme un chiffre en son carré.
- On peut également utiliser une fonction {{lambda }} :
- tranforme_chiffre = lambda x: x**2
- """
- def tranforme_chiffre(x):
- return x**3
- """
- nombre_en_tableau(N) tranforme un entier N comme 3456 en la liste [6,5,4,3]
- """
- def nombre_en_tableau(N):
- liste=[]
- while N != 0:
- liste.append(N % 10) comme le montre cette copie d'écran statique
- # reste division N par 10
- N=N//10
- # quotient division N par 10
- return liste
- """
- sommespeciale(liste) renvoie la somme des chiffres, ou la somme des carrés
- des chiffres, ..., selon la fonction tranforme_chiffre
- """
- def sommespeciale(liste):
- somme=0
- for i in range(0,len(liste)):
- somme=somme+tranforme_chiffre(liste[i])
- return somme
- """
- A un entier donné, on applique la fonction sommespeciale autant de fois que
- nécessaire pour tomber sur 1 ou pour tomber sur un cycle.
- sommefinale renvoie alors le cycle obtenu.
- Par exemple avec tranforme_chiffre(x)=x^2
- """
- def sommefinale(unentier):
- suite=[]
- while (unentier>1) and not(unentier in suite):
- suite.append(unentier)
- unentier=sommespeciale(nombre_en_tableau(unentier))
- suite.append(unentier)
- return suite
- """
- Cette fonction appelle simplement la fonction sommefinale en vérifiant auparavant
- que le premier terme est positif. Son intérêt est essentiellement pédagogique :
- gestion des erreurs.
- """
- def cycle(u0):
- if (u0<=0):
- return
- return sommefinale(u0)
- """
- Cette fonction affiche tous les cycles pour u0 inférieur ou égal au paramètre max
- """
- def touslescycles(max):
- for entier in range(1,max+1):
- print(entier," ==> ",cycle(entier))
Graphiques
La cyclicité de la suite peut être testée graphiquement ci-dessous avec DGPad (ou en cliquant sur ce lien). On peut y modifier la valeur de départ de la suite grâce à un curseur, ainsi que le nombre de termes. Merci à Patrick Raffinat pour ce complément [1].