Répartition des nombres premiers

arithmetique_repartition_nombres_premiers_1.gif

Nombre de façons d'écrire un nombre pair inférieur à 100000 comme la somme de deux nombres premiers

I) Présentation

  On va profiter de la fonction crible_Erathostene(n), qui nous donne la liste des nombres premiers plus petits que n, pour analyser cette liste et “répondre” de manière expérimentale (avec des graphes) à trois questions classiques sur les nombres premiers, dont seule la première est résolue (démontrée) aujourd'hui.

  Lorsque n tend vers l'infini:

    (P) Quel est l'ordre de grandeur du nombre p ( n ) de nombre premiers plus petits que n ?

  Le théorème des nombres premiers (démontré par Hadamard et La Vallée Poussin en 1896) affirme que   p ( n ) + n ln ( n ) .

    (J) Quel est l'ordre de grandeur du nombre j ( n ) de couples de nombres premiers jumeaux plus petits que n ?

   Deux nombres premiers sont jumeaux lorsqu'ils se suivent dans les nombres impairs: par exemple (5,7) ou (17,19).
   La conjecture des nombres premiers jumeaux (non démontrée à ce jour) assure qu'il y a une infinité de couples de nombres premiers jumeaux.

    (G) Quel est l'ordre de grandeur du nombre g ( n ) de façons d'écrire un nombre pair n comme  la somme de deux nombres premiers plus petits que n ?

  La conjecture de Goldbach (non démontrée à ce jour) assure que tout nombre pair ≥ 4  peut s'écrire au moins d'une façon comme la somme de deux nombres premiers.

    Un document (facile à comprendre) du CNRS datant de juillet 2013 traite de ces trois questions.

II) Méthode de travail

1) Protocole

Pour chacune des trois questions, il faudra:
    (1) Ecrire un algorithme efficace calculant la liste des valeurs de la fonction p(), j() ou g() sur l'intervalle [1,...,n]
    (2) Construire et afficher le graphe correspondant
    (3) Chercher un ordre de grandeur de f ( n )   (avec f = p , j , g ) en cherchant un équivalent f 1 ( n ) de f ( n ) lorsque n + .

Rappel:   f 1 ( n ) + f ( n ) f ( n ) f 1 ( n ) n + 1 .

  Cette recherche d'un équivalent f 1 ( n ) sera faite de manière expérimentale: il faudra tracer le graphe de f ( n ) f 1 ( n ) pour "savoir" si f ( n ) f 1 ( n ) n + 1 . Bien sûr, rien n'est démontré en procédant ainsi, mais seulement conjecturé.

2) Précisions

a) Pour les questions (P) et (J)

  Pour les deux premières questions, on calculera la liste des valeurs de la fonction f (avec f = p , j ) non pas sur l'intervalle [ 1 , ... , n ] , mais  sur la liste [ p 0 , p 1 , ... , p N - 1 ] = [ 2 , 3 , 5 ... , p N - 1 ] des nombres premiers plus petits que n . C'est suffisant pour notre estimation car les fonctions p ( ) et j ( ) sont des fonctions croissantes qui ne changent (éventuellement pour j ( ) ) de valeur que sur les nombres premiers. Et c'est plus rapide.

b) Pour la question (G)

  Pour la troisième question, on calculera la liste des valeurs de la fonction g non pas sur l'intervalle [ 1 , ... , n ] , mais sur la liste [ 4 , 6 , 8 , .. , n ] des nombres pairs plus grands que 4 et plus petits que n (avec n entier pair).

III) Calcul des listes des points nécessaires aux tracés

On donne une version optimisée du crible d'Erathostène, qui calcule la liste des nombres premiers plus petits qu'un entier donné n

def crible(n):
    """ Liste des nombres premiers plus petits que n. Algorithme optimisé"""
    s = [True]*(n + 1)
    for p in range(2, floor(sqrt(n)) + 1):
        if s[p]:
            s[p*p::p] = [False]*(n//p - p + 1)
    res = [i for i in range(2, n + 1) if s[i]]
    return res

Par exemple, sur mon PC, la durée d'exécution de crible(10**6) = 0.109 s (sans l'affichage de la réponse).

1) Pour la fonction p

  On rappelle que p(n) est le nombre de nombres premiers plus petits ou égal à n.

Par exemple pour n = 32:
    (1) la liste des valeurs des abscisses (voir II)2)a) est la liste des nombres premiers plus petits que 32.  C'est la liste [2,3,5,7,11,13,17,19,23,29,31] .
    (2) la liste des valeurs des ordonnées est la liste [p[2], p[3], p[5], ..., p[31]]. C'est donc la liste [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 ] .

Q1) Ecrire une fonction val_p(s) (avec s liste d'entiers) calculant pour la fonction p la liste des ordonnées pour une liste s d'abscisses.
Par exemple val_p([2,3,5,7,11,13,17,19,23,29,31]) = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 ] .

2) Pour la fonction j

  On rappelle que j(n) est le nombre de couples de nombres premiers jumeaux plus petits ou égal à n.

Par exemple pour n = 32:
    (1) la liste des valeurs des abscisses (voir II)2)a) est la liste des nombres premiers plus petits que 32.  C'est la liste [2,3,5,7,11,13,17,19,23,29,31] .
    (2) la liste des valeurs des ordonnées est la liste [j[2], j[3], j[5],..., j[31]] = [0,0,1,2,2,3,3,4,4,4,5]     

Q2) Ecrire une fonction val_j(s) (avec s liste d'entiers) calculant pour la fonction j la liste des ordonnées pour une liste s d'abscisses.
Par exemple val_j([2,3,5,7,11,13,17,19,23,29,31]) = [0,0,1,2,2,3,3,4,4,4,5].
On pourra remarquer que remarquer que j[k] = j[k - 1] lorsque s[k] ≠ s[k-1] + 2 et  j[k] = j[k - 1] + 1 lorsque s[k] = s[k-1] + 2.

3) Pour la fonction g

  On rappelle que g(k) est le nombre de façons d'écrire le nombre pair k comme la somme de deux nombres premiers.

Par exemple pour n = 32:
    (1)  la liste des valeurs des abscisses (voir II)2)b) est la liste des nombres pairs compris entre 4 et 32, c'est à dire la liste [4,6,8,10,12,14,16,18,20,22,24,26,28,30,32].
    (2)  la liste des valeurs des ordonnées est la liste [g(4),g(6) g(8), ...,g(30),g(32]. Par exemple g(4) = 1 car 4 = 2+2 , g(14) = 2 car 14 = 3+11 = 7+7 et g(22) = 3 var 22 = 3+19 = 5+17 = 11+11. On trouve finalement comme résultat [1,1,1,2,1,2,2,2,2,3,3,3,2,3,2]

  La liste des abscisses, qui pour un entier n pair est la liste [4, 6,...,n] des nombres pairs compris entre 4 et n, est la liste range(4, n+1, 2).

  On veut écrire une fonction val_g(n) calculant, pour un entier n pair donné, la liste [g(4),g(6),...,g(n)].

  Notons s = [ 2 , 3 , 5 ... , p N - 1 ] = [ s [ 0 ] , s [ 1 ] , ... , s [ N - 1 ] ]   liste des nombres premiers inférieurs ou égaux à n . Par définition de g , g ( 2 k ) est le nombre de couples ( s [ i ] , s [ j ] ) de la liste s qui vérifient 0 i j < N et s [ i ] + s | j ] = 2 k . La première idée qui vient est:

fonction val_g(n):
    s = crible(n)
    N = len(s)
    res = [0]*(n // 2 - 1)
    pour k variant de 2 à n //2:
    c = 0
        pour i variant de 0 à N - 1:        
            pour j variant de 0 à i:
                si s[i] + s[j] = 2*k alors:        #(1)#
                    c = c + 1
        res[k - 2] = c
    résultat = res

  Le coût C ( n ) (mesuré par le nombre d'exécution de l'instruction #(1)#) est de l'ordre de n 2 N ( N + 1 ) 2 , soit en O ( n N 2 ) = O ( n 3 ln 2 ( n ) ) car N n ln ( n ) . C'est très maladroit car on recalcule pour chaque valeur de k toutes les sommes s [ i ] + s [ j ] .
  On peut ne calculer qu'une seule fois ces sommes:

fonction val_g(n):
    s = crible(n)
    N = len(s)
    res = [0]*(n // 2 - 1)
    res[0] = 1                            # g(4) = 1 car 4 = 2 + 2        
    pour i variant de 1 à N - 1:    # On “oublie” s[0]=2 qui ne sert que dans 2+2=4
        pour j variant de 1 à i:
            k = s[i] + s[j]            #(1)#
            si k ≤ n:
                q = k//2 - 2            # g(k)= q-ième terme (à partir de 0) de la liste val_g
                res[q] = res[q] + 1
    résultat = res

Le coût C ( n ) (mesuré par le nombre d'exécution de l'instruction #(1)#) est de l'ordre de N ( N + 1 ) 2 =   O ( n 2 ln 2 ( n ) ) : c'est bien mieux.

Q3) Ecrire la fonction fonction val_g(n)

IV) Tracés et recherche des ordres de grandeur

1) Graphe et ordre de grandeur de la fonction p

  On veut tracer le graphe de la fonction k p ( k ) f ( k ) , où la fonction f est l'équivalent simple recherché. Avec f ( n ) = 1 , on obtient le graphe de p. Comme les valeurs de p(k) pour les petites valeurs de k ne sont pas trop significatives, on ne tracera pas le graphe sur [1,n], (en fait [ p 0 , p 1 , ... , p N - 1 ] ), mais on éliminera la première partie du graphe, les premiers a % (a pour cent)
( avec a ∈ [0,100[)

La fonction graphe_p(a, n, f) suivante trace le graphe de la fonction k p ( k ) f ( k ) sur [1,n] (en fait [ p 0 , p 1 , ... , p N - 1 ] ) en éliminant les premiers a % .

import numpy as np
import pylab as plt

def graphe_p(a, n, f):
    """ graphe de k --> p(k)/f(k) en éliminant les premiers a %"""
    plage_x = crible(n)
    plage_y = val_p(plage_x)
    nmax = len(plage_x)
    nmin = (nmax * a) // 100
    plage_y = [plage_y[i] / f(plage_x[i]) for i in range(nmin, nmax)]
    plt.plot(plage_x[nmin:], plage_y)
    plt.xlabel(" n")
    plt.ylabel("p(n) / f(n)")
    plt.title("Recherche d'un équivalent pour la fonction p")
    plt.grid(True)
    plt.show()

Par exemple, si vous voulez tester avec f ( n ) = ln ( n ) pour n 10000 en éliminant les premiers 20% du tracé, on procède ainsi:

def fp(n):
    return log(n)
graphe_p(20, 10000, fp)   

Q4) Faire des essais en augmentant la valeur de n jusqu'à quelques millions (avec f(n) = 1 et a = 0 pour commencer).
  En choisissant par exemple a = 10, chercher la meilleure fonction f = fp de manière à ce que (graphiquement)   p ( n ) fp ( n ) n + 1 . Vérifier que fp ( n ) = n ln ( n ) est la meilleure possible. On illustre ainsi le théorème des nombres premiers (démontré par Hadamard et La Vallée Poussin en 1896) qui affirme que   p ( n ) + n ln ( n ) .

2) Graphe et ordre de grandeur de la fonction j

Q5) Ecrire une fonction graphe_j(a, n, f) suivante trace le graphe de la fonction k j ( k ) f ( k ) sur [1,n] (en fait [ p 0 , p 1 , ... , p N - 1 ] ) en éliminant les premiers a % .

  Q5a) Faire des essais en augmentant la valeur de n jusqu'à quelques millions (avec f(n) = 1 pour commencer).
  Q5b) Chercher une bonne f = fj de manière à ce que (graphiquement)   p ( n ) fj ( n ) n + 1 .
  Q5c) En cherchant sur le net avec des requêtes du type “pi 2(n) nombre premiers jumeaux”, comparer l'estimation que vous avez trouvée avec celle   π 2 ( n ) conjecturée par les mathématiciens.

  Expérimentalement, il semble évident non seulement qu'il y a une infinité de couples de nombres premiers jumeaux, mais que leur nombre j(n) tend “rapidement” vers l'infini. Il est frustrant de ne pas avoir encore trouvé de démonstration pour cette conjecture.
  En 2013 Yitang Zhang (Université du New Hampshire, Etats-Unis) a démontré qu'il existait une infinité de nombres premiers consécutifs dont l'écart est moindre que 70 000 000. Les optimistes disent que c'est un grand pas vers la démonstration de la conjecture des premiers jumeaux, mais on peut se dire aussi que 70 000 000 c'est bien loin de 2...

3) Graphe et ordre de grandeur de la fonction g

On trace le graphe de la fonction g sans joindre les points (sinon c'est illisible). De plus on essaie d'encadrer les valeurs extrêmes de g(n) par des fonctions bien choisies f1(n) et f2(n). La fonction ci-dessous fait le travail:

def graphe_g(n, f1, f2):
    """ graphes de k --> g(k), f1(k), f2(k) sur [4,6,..,n]"""
    plage_x, nmax = range(4, n + 1, 2), n // 2 - 1
    plage_y = val_g(n)
    plage_y = [plage_y[i] for i in range(nmax)]
    plage_f1 = [f1(plage_x[i]) for i in range(nmax)]
    plage_f2 = [f2(plage_x[i]) for i in range(nmax)]
    plt.plot(plage_x, plage_y, linestyle = “”, marker=”.”, markersize = 1)
    plt.plot(plage_x, plage_f1)
    plt.plot(plage_x, plage_f2)
    plt.xlabel(" n")
    plt.ylabel("g(n), f1(n), f2(n)")
    plt.title("Comète de Goldbach pour n ≤" + str(n))
    plt.legend(("g(n)", "f1(n)", "f2(n)"), 'upper center')
    plt.grid(True)
##    plt.savefig('Comète.jpg',dpi=200)
    plt.show()

Q6) Faire des essais en augmentant la valeur de n jusqu'à quelques dizaines de milliers (avec f1(n) = f2(n) = 1 pour commencer). Le graphe que l'on obtient est curieux: on parle de la comète de Goldbach.  Trouver des bonnes fonctions f1 = fg_min et f2 = fg_max encadrant au mieux la comète de Goldbach. Essayer de faire aussi bien que dans l'image au début.

  Expérimentalement, la conjecture de Goldbach semble évidente. Non seulement tout nombre pair peut s'écrire comme somme de deux nombres premiers, mais le nombre d'écritures possibles semble tendre “rapidement” vers l'infini... Et pourtant aucune démonstration à ce jour.  Actuellement cette conjecture a été démontrée (par le calcul) jusqu' à n ≈ 10 18 ....

© 2014 - Eric Obermeyer      Powered by      Corrigé