User

I. Introduction

On souhaite évaluer au mieux la quantité de nombres premiers compris dans un intervalle d'entiers suffisamment grand de sorte qu'il n'est pas possible de tester dans un temps acceptable tous les nombres entiers de cet intervalle.

En supposant à priori que les nombres premiers sont répartis de façon aléatoire, on va d'abord montrer comment effectuer ce test sur un nombre restreint d'entiers choisis au hasard, mais quand même suffisamment grand pour évaluer au mieux la quantité de nombres premiers compris dans cet intervalle.

Ensuite, nous allons implémenter cette méthode de Monte-Carlo en Python afin notamment de vérifier que globalement plus le nombre de valeurs choisies dans l'intervalle est important, plus le résultat est précis et proche de celui obtenu avec une certaine fonction Li(x).

Enfin, nous allons créer une interface paramétrable Tkinter intégrant un graphique et permettant de tracer les courbes représentatives des deux fonctions.


II. Méthode de Monte-Carlo

D'après Wikipedia, une méthode de Monte-Carlo, ou méthode Monte-Carlo, est une méthode algorithmique visant à calculer une valeur numérique approchée en utilisant des procédés aléatoires, c'est-à-dire des techniques probabilistes.

Les méthodes de Monte-Carlo sont particulièrement utilisées pour calculer des intégrales en dimensions plus grandes que 1 (en particulier, pour calculer des surfaces et des volumes). Elles sont également couramment utilisées en physique des particules, où des simulations probabilistes permettent d'estimer la forme d'un signal ou la sensibilité d'un détecteur. La comparaison des données mesurées à ces simulations peut permettre de mettre en évidence des caractéristiques inattendues, par exemple de nouvelles particules.

Le véritable développement des méthodes de Monte-Carlo s'est effectué notamment sous l'impulsion de John von Neumann et Stanislaw Ulam.



III. Répartition des nombres premiers

Un nombre premier est un entier naturel qui admet seulement deux diviseurs distincts entiers et positifs : 1 et le nombre considéré lui-même.

Puisque tout nombre a pour diviseurs 1 et lui-même, comme le montre l’égalité n = 1 × n, les nombres premiers sont ceux qui n'ont pas d'autre diviseur. Par exemple, le nombre entier 7 est premier car 1 et 7 sont ses seuls diviseurs entiers et positifs.


III-A. Méthode de Monte-Carlo : évaluation de la proportion et de la quantité de nombres premiers compris dans un certain intervalle

On souhaite donc évaluer au mieux la proportion de nombres premiers compris dans un intervalle d'entiers suffisamment grand [x₁, x_n] de sorte qu'il n'est pas possible de tester dans un temps acceptable tous les nombres entiers compris dans cet intervalle.

En supposant à priori que les nombres premiers sont répartis de façon aléatoire, on effectue donc un tirage restreint de k entiers au hasard.

On évalue alors parmi ces entiers la proportion observée f (de nombres premiers) définie comme le quotient du nombre de tests de primalité positifs par le nombre k de tirages, en supposant tout de même que k est suffisamment grand pour profiter de la loi des grands nombres et du théorème central limite. La loi des grands nombres assure dans ce cas qu’il est très probable que la fréquence observée soit proche de la proportion p, et l'intervalle de confiance à 95% est alors :

[f - 1/√k, f + 1/√k]

Autrement dit, il y a (au moins) 95% de chances que la vraie valeur p soit dans l'intervalle de confiance [f - 1/√k, f + 1/√k].

On remarque que plus k augmente, plus l'intervalle de confiance se réduit, et donc plus grande est la précision.

La quantité estimée de nombres premiers s'obtient alors en multipliant simplement la proportion obtenue par n.

Cette procédure peut être réitérée pour plusieurs intervalles successifs et plusieurs valeurs de k afin de mieux évaluer la précision de notre méthode.


III-B. Théorème des nombres premiers

D'après Wikipedia, le théorème des nombres premiers (Hadamard et de La Vallée Poussin, 1896) est un résultat concernant la distribution asymptotique des nombres premiers.

La fonction 𝜋 qui à un réel x associe 𝜋(x) le nombre de nombres premiers inférieurs ou égaux à x, est équivalente lorsque x tend vers +∞, au quotient de x par son logarithme népérien x/ln(x), c'est à dire :



Un approximant de 𝜋(x) nettement meilleur que x/ln(x) est la fonction logarithme intégral li(x) ou sa variante, la fonction d'écart logarithmique intégrale Li(x) :



Représentation graphique des trois courbes par Noel Bush :



Comme on le voit sur le graphique, la courbe représentative de la fonction Li(x) en bleu se confond pratiquement avec celle représentant la fonction 𝜋(x) en rouge donnant la quantité réelle de nombres premiers inférieurs ou égaux à x.

Grâce au théorème dit des nombres premiers nous disposons donc de fonctions nous permettant de connaître avec une bonne précision la quantité de nombres premiers inférieurs ou égaux à un réel x quand x tend vers l'infini.

Nous pouvons donc maintenant comparer le résultat obtenu à l'aide de la méthode de Monte-Carlo sur un intervalle suffisamment grand [x₁, x_n] à celui évalué avec la fonction Li(x) et utilisant la formule :



Ou plus simplement :




IV. Implémentation en Python


IV-A. Méthode de Monte-Carlo

On présente maintenant les fonctions permettant d'évaluer au mieux la proportion et la quantité de nombres premiers compris dans un certain intervalle de valeurs à l'aide de la méthode de Monte-Carlo :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def proportion_premiers(x1, xn, k):
    # x1 : borne inférieure de l'intervalle des nombres entiers
    # xn : borne supérieure de l'intervalle des entiers
    # k : nombre de valeurs tirées au hasard dans l'intervalle [x1, xn] 
 
    # séquence de nombres entiers compris dans l'intervalle [x1, xn]
    nombres_entiers = range(x1, xn + 1)
 
    # initialisation du compteur de nombres premiers
    qte_premiers = 0
 
    # tirage au hasard de k entiers parmi la séquence de n entiers
    for j in range(k):
 
        # choix d'un nombre entier au hasard parmi la liste de nombres entiers
        N = random.choice(nombres_entiers)
 
        # si N est premier
        if test_primalite(N):
            # incrémentation du compteur de nombres premiers
            qte_premiers+=1
 
    # proportion de nombre premiers choisis au hasard dans l'intervalle [x1, xn]
    f = qte_premiers/k
 
    # renvoi de la proportion de nombres premiers compris dans l'intervalle
    return f
 
 
def quantite_premiers(x1, xn, k):
    # x1 : borne inférieure de l'intervalle des nombres entiers
    # xn : borne supérieure de l'intervalle des entiers
    # k : nombre de valeurs tirées au hasard dans l'intervalle [x1, xn]
 
    return proportion_premiers(x1, xn, k)*(xn-x1+1)

On souhaite d'abord afficher les proportions évaluées avec la fonction Li(x) et celles obtenues avec la méthode de Monte-Carlo pour plusieurs intervalles d'entiers et plusieurs valeurs de k :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# nombre d'entiers par intervalle
n = 4000000
 
# séquence des x avec un pas de longueur n
x_values = range(2000000, 14000001, n)
 
# parcours des x avec un pas de longueur n
for x in x_values:
 
    # proportion de nombres premiers dans cet intervalle suivant la fonction Li(x)
    p = (Li(x+n-1)-Li(x-1))/n
 
    print("Intervalle des valeurs : " + str([x, x+n-1]))
    print("Proportion estimée avec Li(x) : " + str(round(p,7)))
    print("Qté estimée avec Li(x) : " + str(round(p*n)))
 
    print()
 
    # initialisation de la liste des résultats
    results = []
 
    # parcours des exposants de 10 : 10^3, .., 10^5
    for i in range(3, 6):
        k = 10**i
 
        # évaluation de la proportion de nombres premiers compris dans [x, x+n-1] : méthode de Monte-Carlo
        f = round(proportion_premiers(x, x+n-1, k),7)
 
        # bornes inférieure et supérieure de l'intervalle de confiance
        borne_inf, borne_sup = round(f - 1/math.sqrt(k),7), round(f + 1/math.sqrt(k),7)
 
	# ligne de résultats : [k, f, [borne_inf, borne_sup], n*f, [n*borne_inf, n*borne_sup]]
        result = [k, f, str([borne_inf, borne_sup]), round(n*f), str([round(n*borne_inf), round(n*borne_sup)])]
 
        # ajout du résultat à la liste
        results.append(result)
 
    # création du tableau numpy à 2 dimensions contennant la liste de résultats
    tb_valeurs = np.array(results)
 
    # création du dataframe
    df = pd.DataFrame(tb_valeurs, columns = ['  k', '  Proportion observée avec MC', '  Intervalle de confiance', '  Qté estimée avec MC', '  Intervalle de confiance'])
 
    # affiche le dataframe
    print(df)
 
    print("------------------------------------------------------------------------------------------------------------------")

Le code affiche les résultats obtenus à l'aide de la méthode de Monte-Carlo (MC) dans des DataFrames Pandas :



Nous constatons que globalement plus k est grand, plus la proportion de nombres premiers observée dans chaque intervalle se rapproche de l'estimation obtenue à l'aide de la fonction Li(x). On peut aussi mieux évaluer la précision de chaque résultat grâce à son intervalle de confiance à 95%.


IV-B. Représentation graphique

Nous souhaitons maintenant tracer les courbes représentatives de la fonction Li(x) et des quantités évaluées à l'aide de la méthode de Monte-Carlo (MC).


IV-B-1. Génération du graphique avec la librairie matplotlib

Nous allons donc d'abord générer le graphique à l'aide de la librairie matplotlib :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
mport matplotlib.pyplot as plt
 
...
 
# valeur du pas dans la séquence de nombres entiers
n = 200000
 
# séquence des x avec un pas de longueur n
x_values = range(n, 40*n+1, n)
 
# liste des quantités de nombres premiers estimées à l'aide de la fonction Li(x) 
Li_values =[Li(x) for x in x_values]
 
# nombre de tirages par intervalle 
k = 1000
 
# initialisation de la liste des qtés de nombres premiers : méthode de Monte-Carlo
y_values = []
 
# initialisation de la quantité de nombres premiers
qte_premiers = 0
 
# borne inférieure de l'intervalle [x1, x]
x1=1 
 
# parcours des x avec un pas de longueur n
for x in x_values:
 
    # évaluation de la quantité de nombres premiers inférieurs ou égaux à x  : méthode de Monte-Carlo
    qte_premiers += quantite_premiers(x1, x, k)
 
    # ajout de la quantité à la liste y_values
    y_values.append(qte_premiers)
 
    x1 = x+1 # borne inférieure prochain intervalle
 
# lissage des points
# y_values = savgol_filter(y_values, len(y_values)//2+1, 3)
 
plt.plot(x_values, Li_values, label = "Li(x)")
plt.plot(x_values, y_values, label = "Quantités évaluées avec MC")
 
plt.ylim(0)
 
plt.legend()
 
# titre du graphique 
plt.title('Qtés de nombres premiers inférieurs ou égaux à x')
 
# affichage du graphique 
plt.show()

Le code affiche le graphique :



On peux également effectuer un lissage des points représentant les quantités estimées avec la méthode de Monte-Carlo en utilisant la fonction savgol_filter présente dans la librairie scipy.stats.


IV-B-2. Intégration du graphique dans une interface Tkinter

Nous allons maintenant créer une interface paramétrable avec Tkinter sur laquelle nous allons pouvoir notamment choisir les valeurs mini et maxi des x, ainsi que le nombre d'entiers tirés au hasard dans chaque intervalle des x, puis tracer les courbes représentatives des deux fonctions.

Cet interface est définie à l'aide d'une classe Interface_graphique présente dans la librairie interface_graphique.py qui est d'ailleurs disponible en téléchargement à la fin du billet.

Testons maintenant notre interface graphique :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from interface_graphique import Interface_graphique
 
...
 
# valeur du pas dans la séquence de nombres entiers
n = 200000
 
# nombre de tirages par intervalle 
k = 1000
 
# création de l'objet Interface_graphique avec les paramètres : valeur_mini, valeur_maxi, valeur_pas, nb_tirages, Li, quantite_premiers
interface_graphique = Interface_graphique(n, 40*n, n, k, Li, quantite_premiers)
 
# centre la fenêtre
interface_graphique.eval('tk::PlaceWindow . center')
 
interface_graphique.mainloop()

Le code affiche :





IV-C. Module Python

On donne pour finir le code complet du module présent dans le fichier joint dossier_test.zip :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
import math
import random
import numpy as np
import scipy.integrate as integrate
import pandas as pd
import matplotlib.pyplot as plt
from scipy.signal import savgol_filter
from interface_graphique import Interface_graphique
 
 
def Li(x):
    s = integrate.quad(lambda t: 1/math.log(t), 2, x)
    return s[0]
 
def proportion_premiers(x1, xn, k):
    # x1 : borne inférieure de l'intervalle des nombres entiers
    # xn : borne supérieure de l'intervalle des entiers
    # k : nombre de valeurs tirées au hasard dans l'intervalle [x1, xn] 
 
    # séquence de nombres entiers compris dans l'intervalle [x1, xn]
    nombres_entiers = range(x1, xn + 1)
 
    # initialisation du compteur de nombres premiers
    qte_premiers = 0
 
    # tirage au hasard de k entiers parmi la séquence de n entiers
    for j in range(k):
 
        # choix d'un nombre entier au hasard parmi la liste de nombres entiers
        N = random.choice(nombres_entiers)
 
        # si N est premier
        if test_primalite(N):
            # incrémentation du compteur de nombres premiers
            qte_premiers+=1
 
    # proportion de nombre premiers choisis au hasard dans l'intervalle [x1, xn]
    f = qte_premiers/k
 
    # renvoi de la proportion de nombres premiers compris dans l'intervalle
    return f
 
 
def quantite_premiers(x1, xn, k):
    # x1 : borne inférieure de l'intervalle des nombres entiers
    # xn : borne supérieure de l'intervalle des entiers
    # k : nombre de valeurs tirées au hasard dans l'intervalle [x1, xn]
 
    return proportion_premiers(x1, xn, k)*(xn-x1+1)
 
 
def test_primalite(N):
    # fonction permettant de tester si N est premier en utilisant la méthode naïve
    # N : nombre entier à tester
 
    if N==1: return False # 1 n'est pas un nombre premier
 
    # détermination du dernier entier m à tester comme diviseur de N : m est égal à la partie entière de √𝑁
    m = int(math.sqrt(N))
 
    # parcours des entiers : 2 -> m
    for i in range(2, m+1):
        # Si i divise N
        if N % i == 0:
            # N possède un diviseur donc n'est pas premier
            # renvoie le tuple False => est_premier
            return False
 
    # N n'a pas de diviseur autre que 1 et lui-même, il est donc premier.
    # renvoie True => est_premier
    return True
 
 
print("I. Méthode de Monte-Carlo : évaluation des proportions et des qtés de nombres premiers compris dans des intervalles successifs ..\n")
 
pd.set_option('display.max_columns', 500)
pd.set_option('display.width', 1000)
 
# nombre d'entiers par intervalle
n = 4000000
 
# séquence des x avec un pas de longueur n
x_values = range(2000000, 14000001, n)
 
# parcours des x avec un pas de longueur n
for x in x_values:
 
    # proportion de nombres premiers dans cet intervalle suivant la fonction Li(x)
    p = (Li(x+n-1)-Li(x-1))/n
 
    print("Intervalle des valeurs : " + str([x, x+n-1]))
    print("Proportion estimée avec Li(x) : " + str(round(p,7)))
    print("Qté estimée avec Li(x) : " + str(round(p*n)))
 
    print()
 
    # initialisation de la liste des résultats
    results = []
 
    # parcours des exposants de 10 : 10^3, .., 10^5
    for i in range(3, 6):
        k = 10**i
 
        # évaluation de la proportion de nombres premiers compris dans [x, x+n-1] : méthode de Monte-Carlo
        f = round(proportion_premiers(x, x+n-1, k),7)
 
        # bornes inférieure et supérieure de l'intervalle de confiance
        borne_inf, borne_sup = round(f - 1/math.sqrt(k),7), round(f + 1/math.sqrt(k),7)
 
	# ligne de résultats : [k, f, [borne_inf, borne_sup], n*f, [n*borne_inf, n*borne_sup]]
        result = [k, f, str([borne_inf, borne_sup]), round(n*f), str([round(n*borne_inf), round(n*borne_sup)])]
 
        # ajout du résultat à la liste
        results.append(result)
 
    # création du tableau numpy à 2 dimensions contennant la liste de résultats
    tb_valeurs = np.array(results)
 
    # création du dataframe
    df = pd.DataFrame(tb_valeurs, columns = ['  k', '  Proportion observée avec MC', '  Intervalle de confiance', '  Qté estimée avec MC', '  Intervalle de confiance'])
 
    # affiche le dataframe
    print(df)
 
    print("------------------------------------------------------------------------------------------------------------------")
 
print()
 
print("II. Courbes représentatives des qtés de nombres premiers inférieurs où égaux à x : valeurs de Li(x) / qtés estimées avec MC\n")
 
print("II-A. Génération du graphique avec la librairie matplotlib ..\n")
 
# valeur du pas dans la séquence de nombres entiers
n = 200000
 
# séquence des x avec un pas de longueur n
x_values = range(n, 40*n+1, n)
 
# liste des quantités de nombres premiers estimées à l'aide de la fonction Li(x) 
Li_values =[Li(x) for x in x_values]
 
# nombre de tirages par intervalle 
k = 1000
 
# initialisation de la liste des qtés de nombres premiers : méthode de Monte-Carlo
y_values = []
 
# initialisation de la quantité de nombres premiers
qte_premiers = 0
 
# borne inférieure de l'intervalle [x1, x]
x1=1 
 
# parcours des x avec un pas de longueur n
for x in x_values:
 
    # évaluation de la quantité de nombres premiers inférieurs ou égaux à x  : méthode de Monte-Carlo
    qte_premiers += quantite_premiers(x1, x, k)
 
    # ajout de la quantité à la liste y_values
    y_values.append(qte_premiers)
 
    x1 = x+1 # borne inférieure prochain intervalle
 
# lissage des points
# y_values = savgol_filter(y_values, len(y_values)//2+1, 3)
 
plt.plot(x_values, Li_values, label = "Li(x)")
plt.plot(x_values, y_values, label = "Quantités évaluées avec MC")
 
plt.ylim(0)
 
plt.legend()
 
# titre du graphique 
plt.title('Qtés de nombres premiers inférieurs ou égaux à x')
 
# affichage du graphique 
plt.show()
 
 
print("II-B. Paramétrage du graphique sur une interface Tkinter ..") 
 
# création de l'objet Interface_graphique avec les paramètres : valeur_mini, valeur_maxi, valeur_pas, nb_tirages, Li, quantite_premiers
interface_graphique = Interface_graphique(n, 40*n, n, k, Li, quantite_premiers)
 
# centre la fenêtre
interface_graphique.eval('tk::PlaceWindow . center')
 
interface_graphique.mainloop()

V. Conclusion

Après avoir défini ce qu'est une méthode de Monte-Carlo, on a pu montrer comment l'utiliser pour évaluer au mieux la proportion de nombres premiers compris dans un intervalle suffisamment grand.

Enfin, on a pu implémenter cet algorithme en Python afin notamment de vérifier que plus le nombre de valeurs choisies dans l'intervalle est important, plus le résultat est précis et proche de celui obtenu avec la fonction Li(x). On a ainsi pu également montrer sur une série de grands nombres entiers que la fonction Li(x) se rapproche de 𝜋(x) quand x augmente.


Téléchargement :

dossier_test.zip

Sources :

https://fr.wikipedia.org/wiki/M%C3%A...de_Monte-Carlo
https://fr.wikipedia.org/wiki/Nombre_premier
https://fr.wikipedia.org/wiki/Intervalle_de_confiance
https://fr.wikipedia.org/wiki/Th%C3%...mbres_premiers