Outils pour utilisateurs

Outils du site


conjecture_goldbach

Tester la conjecture de Goldbach

Objectif

Pour info sur la conjecture de Goldbach, voir ici (entre autres):

http://fr.wikipedia.org/wiki/Conjecture_de_Goldbach

Pour résumer, cette conjecture dit que tout nombre pair supérieur à 2 (donc à partir de 4) peut être décrit comme la somme de 2 nombres premiers.

Bien que cette conjecture date de 1742 (!), elle n'a pas encore été démontrée mathématiquement.

On va donc faire un petit code pour vérifier sur une grande quantité de nombres qu'on ne trouve pas de cas qui contredit cette conjecture.

Code proposé

Le principe adopté ici est très simple pour tenter de décomposer un nombre n quelconque.

- on part avec le plus petit nombre premier x = 2

- on calcule y = n-x

- si y est premier: on a terminé, et on renvoie [x,y]

- sinon, on prend le nombre premier suivant x, et on recommence

- si on trouve x>y (ou x>(n//2)), on a trouvé un cas d'impossibilité de décomposition (ce qui n'est jamais arrivé!) et on renvoie une liste vide.

En fait, il faut éliminer dès le départ le cas x=2 qui ne marche que pour n=4. En effet, si on retire 2 à un nombre pair, le résultat est pair! Et un nombre pair n'est premier que s'il est égal à 2. Donc, si n=4, on renvoie [2,2]. Après, on part de x=3, et on ne testera désormais que les nombres x impairs.

def goldbach(n):
    """teste la conjecture de Golbach en tentant de décomposer n pair (>2) en 2 nb premiers"""
 
    # verification
    if n<4 or n%2!=0:
        raise ValueError ("Erreur: n doit être un nombre entier pair > 2")
 
    # traitement du cas x=2 qui ne marche que pour n=4
    if n==4:
        return [2,2]
 
    # autres cas
    x = 3
    while True:
 
        # calcul de y et test de primalité
        y = n-x
        if estpremier(y):
            return [x,y]  # on a trouvé!
 
        # vérif qu'on a encore la possibilité de trouver une solution
        if x>y:
            return []  # echec!
 
        # recherche du 1er nb premier suivant x
        x += 2
        while not estpremier(x):
            x += 2


On utilise ici le test de primalité “estpremier(n)”, car on dispose de tests très efficaces qui marchent même pour de très grand nombres: voir par exemple sur ce site le test de Miller-Rabin.

Si vous n'avez rien d'autre, voici un test de primalité minimum, basé sur la méthode des divisions.

Bien qu'il soit rustique, il est assez rapide tant que les nombres ne sont pas trop grands.

from math import sqrt
 
def estpremier(n):
    """Dit si le nombre entier n est premier ou non (méthode par dvision)"""
 
    # traitement du cas: si n est pair
    if n%2==0:
        # ici, n est pair: il n'est premier que si c'est 2
        if n==2:
            return True
        return False
 
    # traitement des autres cas: n est impair
    xmax = int(sqrt(n))+1
    x = 3
    while x<xmax:
        if n%x==0:
            return False  # x est un diviseur de n: n n'est donc pas premier
        x += 2
 
    # ici, on n'a trouvé aucun diviseur de n avant xmax: n est premier
    return True


Et voilà un petit code de test:

n = 4
while True:
    r = goldbach(n)
    print n, r
    if len(r) == 0:
        print "échec"
        break
    n += 2

Ce code boucle jusqu'à ce qu'on l'arrête avec Contrôle-C ou qu'il trouve un cas qui contredit la conjecture (ce qui n'est jamais arrivé jusqu'à présent!).

Exemple de résultats:

4 [2, 2]
6 [3, 3]
8 [3, 5]
10 [3, 7]
12 [5, 7]
14 [3, 11]
16 [3, 13]
18 [5, 13]
20 [3, 17]
22 [3, 19]
24 [5, 19]
26 [3, 23]
28 [5, 23]
30 [7, 23]
...
...
21806360 [7, 21806353]
21806362 [29, 21806333]
21806364 [11, 21806353]
21806366 [13, 21806353]
21806368 [47, 21806321]
21806370 [17, 21806353]
21806372 [19, 21806353]
21806374 [41, 21806333]
21806376 [23, 21806353]
...
...


On peut aussi proposer un autre test: au lieu de tester tous les nombres n à partir de 4, on va les tirer au hasard!

Par exemple avec le code:

from random import randint
while True:
    n = 1
    while n%2!=0:
        n = randint(10**50,10**51-1)
    r = goldbach(n)
    print n, r
    if len(r) == 0:
        print "échec"
        break
    n += 2

On a essayé ici des nombres composés de 50 chiffres.

Mais n'essayez pas des nombres aussi grands avec un test de primalité basé sur les divisions: plus rien ne sortira!

Avec un test de primalité rapide, voilà un exemple de sortie:

107945564019871557671061733039132421556711461481712 [71, 107945564019871557671061733039132421556711461481641L]
125495795615471508351661225289730280463878641016438 [599, 125495795615471508351661225289730280463878641015839L]
348820662364255524357155302168130131174953415265116 [659, 348820662364255524357155302168130131174953415264457L]
312540520103273646332167888883203059519778990693890 [67, 312540520103273646332167888883203059519778990693823L]
383596438259563120131881791021601388640058532681294 [41, 383596438259563120131881791021601388640058532681253L]
151329342268833587333665075078487210351418768629242 [131, 151329342268833587333665075078487210351418768629111L]
181005230234421993271117421054913264035867834525198 [7, 181005230234421993271117421054913264035867834525191L]
676641932782274664186633959762322877772575441692384 [73, 676641932782274664186633959762322877772575441692311L]
222620800285097200053690004867663217711675057173868 [601, 222620800285097200053690004867663217711675057173267L]
510169562608249480106886119769954115628760425394050 [271, 510169562608249480106886119769954115628760425393779L]

Sur un PC moderne, chacun de ces calculs demande environ… 1/10 de seconde!


Amusez-vous bien!

conjecture_goldbach.txt · Dernière modification: 2010/10/22 09:44 de tyrtamos

Outils de la page