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!