La série des inverses des nombres premiers est-elle convergente?

C’est la question, un peu surprenante pour le commun des mortels, que je me suis posée hier soir. Je finissais d’écrire un petit programme Python pour calculer la liste des nombres premiers inférieurs à un nombre N donné, et comme ce programme utilisait tout simplement la technique du crible d’Eratosthène, je me suis demandé quelle était la complexité d’un tel programme.

Le programme en lui-même est assez simple. Il consiste à construire un tableau de N cases, et à cocher les cases des multiples des nombres qu’on parcourt de 1 à N. Pour optimiser ce parcours, on saute les multiples des nombres dont la case est déjà cochée. La liste des cases non cochées fournit la liste des nombres premiers demandés.

print ("N=?")
N = input()

prems = []
for i in range (0, N+1):
    prems.append(1)
prems[1]=0

for i in range (2, N/2+1):
    if (prems[i] == 1):
        for k in range (2, N/i+1):
            prems[i*k] = 0

for i in range (1, N):
    if (prems[i] == 1):
        print i,
print

La complexité d’un tel algorithme est à peu près égale à la somme des N/p où p parcourt la liste des nombres premiers inférieurs à N. D’où ma question sur la série des inverses des nombres premiers.

Or cette série n’est pas convergente. Je n’ai pas cherché à le démontrer, un article de Wikipédia en fournissant une brillante démonstration formulée par le génial Paul Erdös. Je ne sais pas où il est parti chercher son idée, mais tout bonnement c’est superbe.

Voilà comment un peu de programmation peut, parfois, vous donner l’occasion de redécouvrir la magie des maths.

Cet article vous a plu? Partagez-le!

A propos de Herve Kabla

Hervé Kabla, directeur général de be angels et co-fondateur de Media Aces

4 Replies to “La série des inverses des nombres premiers est-elle convergente?”

  1. Il y a plus rapide que le crible d’Eratosthène.
    Soit n à tester :
    On calcule SQRT(n) = R, si R est entier n = R*2 n’est pas premier.
    Si R n’est pas entier, il suffit de tester uniquement sur les premiers inférieurs au nombre entier immédiatement supérieur à R.
    Exemple 97 :
    SQRT(97) = 9,85 donc on teste à partir de 10 soit avec (3, 5, 7), 97 n’est pas divisible par ces nombres donc 97 est premier !

  2. Un peu de pub pour ma librairie https://github.com/goulu/goulib :

    La version la plus rapide du crible en Python est ici : http://goulib.readthedocs.io/en/latest/_modules/Goulib/math2.html#sieve et http://goulib.readthedocs.io/en/latest/_modules/Goulib/math2.html#primes_gen l’utilise pour les petits premiers, avant de passer à Miller-Rabin

    Testé (entre autres) en vérifiant des suites de l’OEIS : https://www.drgoulu.com/2017/06/26/series-infinies-et-oeis-en-python/

    Utilisateurs et contributeurs bienvenus !

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

*