Le sujet de mathématiques pour séries S proposait en exercice pour spécialistes un travail sur les nombres de Mersenne et un algorithme.
4)a) Pour savoir ce que répond cet algorithme, programmons-le sur notre calculatrice graphique :
Algorithme | Programme | ||||||||||||
|
Attention : L'exécution avec n=33 prend étrangement 2min30s sur fx-CP400. La réponse était pourtant quasiment immédiate sur tous les autres modèles.
|
D'après notre calculatrice graphique, l'algorithme affiche donc :
- pour k=33 :
7
CAS 2 - pour k=7 :
12
CAS 1
4)b) L'algorithme se termine si l'on sort de la boucle 'Tant que'. Si cette boucle se termine, c'est que la condition de poursuite
Autrement dit, la boucle 'Tant que' se termine sur la réalisation d'une des deux conditions suivantes :
- $mathjax$MOD(2^n-1,k)=0$mathjax$
- $mathjax$k>\sqrt{2^n-1}$mathjax$
Dans le cas n°2, on n'a pas
Donc forcément, la boucle s'est terminée sur la réalisation de l'autre condition
Le nombre k trouvé par l'algorithme vérifiant donc
Comme ce diviseur a été trouvé, le nombre de Mersenne
4)c) Dans le cas n°1, nous avons
Or, les diviseurs du nombre de Mersenne
Aucun diviseur répondant à ces critères n'ayant été trouvé, le nombre de Mersenne
Liens :