Mines Informatique MP-PC-PSI 2019

Thème de l'épreuve Autour des nombres premiers
Principaux outils utilisés complexité, intégration numérique, méthode des rectangles, bases de données
Mots clefs nombres premiers, crible d'Ératosthène, test de primalité de Fermat, algorithme Blum Blum Shub, fonction de comptage, logarithme intégral

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - - - - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
                             

Extrait du corrigé obtenu par reconnaissance optique des caractères



Mines Informatique MP-PC-PSI 2019 -- Corrigé
Ce corrigé est proposé par Virgile Andreani (ENS Ulm) ; il a été relu par 
Benjamin
Monmege (enseignant-chercheur à l'université) et Guillaume Batog (professeur en
CPGE).

Ce sujet aborde plusieurs problèmes numériques liés aux nombres premiers, 
notamment leur génération et leur comptage. Il est relativement complet, bien 
posé, et
couvre une grande partie du programme.
· La première partie est peu liée au reste et demande l'écriture et la 
compréhension de fonctions simples. Elle aborde également la représentation des 
nombres
réels en machine.
· La deuxième partie est consacrée à la génération de nombres premiers. Elle 
débute par la méthode classique du crible d'Ératosthène. L'algorithme est donné,
il faut simplement l'implémenter et réfléchir à sa complexité et aux contraintes
de mémoire. Une méthode plus efficace pour les grands nombres, qui s'appuie
sur le test probabiliste de primalité de Fermat, est ensuite décrite et doit 
également être implémentée.
· La troisième partie aborde le problème de la répartition des nombres premiers,
et plus particulièrement le calcul de la fonction (n), qui renvoie le nombre de
nombres premiers dans l'intervalle [[ 1 ; n ]]. On peut la calculer directement 
avec
le crible d'Ératosthène vu dans la partie précédente, mais cette approche 
souffre
évidemment des mêmes défauts. On utilise alors l'équivalence des fonctions 
et li (logarithme intégral) à l'infini, en approchant (n) par li(n). Le calcul 
de
cette fonction nécessite l'intégration de l'inverse du logarithme, que l'on 
réalise
ici par la méthode des rectangles. Le calcul est délicat à cause de la 
singularité
en 1. Enfin, on exploite une identité mathématique reliant li à une série que
l'on peut calculer avec une plus grande précision numérique.
· La dernière partie, très courte, porte sur les bases de données.
Il n'y a pas lieu de se laisser intimider par le thème, l'énoncé paraît plus 
mathématique qu'il n'est en réalité !

Indications
Partie I
3 Rappel : / est l'opérateur associé à la division flottante en Python.
4 Attention, x est sobrement défini par le sujet comme un « nombre » ; donc pas
forcément entier. Faire attention au cas 0 < x < 1. On peut utiliser une 
récurrence
pour répondre rigoureusement à la question.
Partie II
8 Veiller aux erreurs « off-by-one » (erreurs de décalage) possibles entre 
l'entier i
et la liste liste_bool.
12 Ne pas oublier d'importer les modules nécessaires à l'utilisation des 
fonctions
demandées.
13 On a le droit de définir une fonction annexe pour le test de primalité de 
Fermat,
qui est répété quatre fois.
14 Attention à ne pas appeler la fonction erato_iter plus que nécessaire.
Partie III
19 Question de cours. Faire en sorte de minimiser les imprécisions numériques, 
voir
question 5.
22 Observer que suffisamment proche de 1, les rectangles à gauche et à droite 
s'annulent quasiment deux à deux en cascade, sauf un de chaque côté. C'est leur
somme qui forme la différence absolue observée.
24 Attention à la confusion entre x et ln x dont l'utilisation par le sujet 
peut être
troublante.
26 On pourra faire appel aux commandes COUNT (qui compte le nombre 
d'enregistrements) et AVG (qui calcule leur moyenne). Pour la deuxième 
question, la commande MINUS (ou EXCEPT) s'avère utile.

I. Préliminaires
1 Afin d'utiliser les fonctions d'un module, il faut l'importer. Si l'on n'a 
besoin
que de quelques fonctions du module, et qu'il n'y a pas de risque de confusion 
avec
des fonctions d'autres modules, on peut les importer spécifiquement dans 
l'espace de
noms global du programme :
from math import log, sqrt, floor, ceil
print(log(0.5))
Cette réponse est celle que le sujet semble attendre, mais on aurait également
pu importer tout le module d'un coup, en faisant attention par la suite à
appeler les fonctions dans l'espace de noms du module :
import math
print(math.log(0.5))
On peut également importer toutes les fonctions du module dans l'espace de
noms global avec from math import *, mais c'est déconseillé parce qu'on
risque de masquer des fonctions déjà existantes.
2 On teste la condition au sein de l'instruction return et on renvoie 
directement
sa valeur :
def sont_proches(x, y):
atol = 1e-5
rtol = 1e-8
return abs(x - y) <= atol + abs(y) * rtol
Attention à ne pas proposer la version suivante :
def sont_proches(x, y):
atol = 1e-5
rtol = 1e-8
if abs(x - y) <= atol + abs(y) * rtol:
return True
else:
return False
qui est un « anti-pattern » (un motif à ne pas reproduire). En effet, la 
condition est inutile puisque l'inégalité renvoie déjà les mêmes booléens, et 
on n'est
même pas à l'abri de se tromper de sens en les recopiant.
3 En déroulant mécaniquement l'exécution du programme, on peut démontrer les
égalités suivantes :
mystere(1001, 10) =
=
=
mystere(1001, 10) =
soit

1
1
1
1

+
+
+
+

mystere(100.1, 10)
(1 + mystere(10.01, 10))
(1 + (1 + mystere(1.001, 10)))
(1 + (1 + 0))

mystere(1001, 10) = 3

4 L'exemple précédent montre que chaque appel à la fonction ajoute 1 au résultat
tout en divisant le premier paramètre par b. Considérons x > 1. On a donc
x 
,b
mystere(x, b) = 1 + mystere
b
x 
ou encore
mystere(x, b) = k + mystere k , b
b
jusqu'à ce que x/bk < b, cas de base où la fonction renvoie 0 et la récursion 
s'arrête.
Le résultat est donc l'entier k tel que
x
x
< b 6 k-1
bk
b
où la première inégalité représente la condition d'arrêt et la seconde le test 
de l'avantdernier appel. On a donc
x
< bk 6 x
b
L'astuce consiste à prendre le logarithme en base b pour obtenir
logb x - 1 < k 6 logb x
où l'on reconnaît k = logb x.
Il reste à traiter la situation 0 < x < 1. Dans ce cas, mystere(x, b) est nul, 
ce
qui ne correspond plus à la partie entière du logarithme de x. On peut soit 
regrouper
les cas avec un maximum, ce qui affaiblit un peu la formulation mathématique :
x > 0 mystere(x, b) = max(0, logb (x))
soit définir la fonction par morceaux :
x > 0

mystere(x, b) =

0
logb (x)

si 0 < x < 1
sinon

Une démonstration par récurrence permettrait une réponse plus rigoureuse. Pour 
cela, fixons un b arbitraire. On va démontrer par récurrence sur n
que l'hypothèse
P(n) :

« x  [[ bn ; bn+1 - 1 ]] mystere(x, b) = logb x »

est vraie pour tout n entier naturel.
· P(0) : le cas de base est 1 6 x < b. Dans ces conditions, on a
mystere(x, b) = 0
La fonction logb est strictement monotone croissante, avec logb (1) = 0
et logb (b) = 1, donc on a bien logb x = 0.
· P(n) = P(n + 1) : supposons que l'hypothèse est vraie pour n.
Alors, pour un x tel que bn+1 6 x < bn+2 , on a
x
mystere(x, b) = 1 + mystere(x / b, b) (où bn 6 < bn+1 )
b
= 1 + logb (x/b)
(par P(n))
= 1 + logb (x) - 1
= 1 + logb (x) - 1
mystere(x, b) = logb (x)