Conjecture de goldbach

Soyez le premier à donner votre avis sur cette source.

Snippet vu 6 561 fois - Téléchargée 18 fois

Contenu du snippet

Voici un nouvel algorithme de mathématique. Il permet de tester les conjectures (faible et forte) de Goldbach d'un entier naturel. Cette conjecture (forte) qui dit que tout entier naturel pair est égal à la somme de deux nombres premiers (des nombres divisibles que par eux même et un) et cette conjecture faible qui dit que tout entier naturel impair et strictement supérieur à 7 est égal à la somme de trois nombres premiers.

Notons la présence de deux tests sous forme de fonctions qui renvoient respectivement si un nombre est pair (parite(n)) ou s'il est premier (primalite(n)). On peut utiliser la fonction de parité pour prouver qu'un nombre est impair (imparité ?) en testant parite(n+1).

Source / Exemple :

Sub Main()

        ' Conjecture faible de Goldbach

        Dim n As UInteger = 1
        Do Until parite(n + 1) And n > 7
            n = Console.In.ReadLine
        Loop

        For i As UInteger = 2 To n - 2
            If primalite(i) And parite(i + 1) Then
                For j As UInteger = 2 To n - i - 2
                    If primalite(j) And parite(j + 1) And primalite(n - i - j) And parite(n - i - j + 1) Then
                        Console.Out.WriteLine(i.ToString & "+" & j.ToString & "+" & (n - i - j).ToString & "=" & n.ToString)
                    End If
                Next j
            End If
        Next i

        Console.In.ReadLine()
    End Sub

    Sub ConjectureForte()

        ' Conjecture forte de Goldbach

        Dim n As UInteger = 1
        Do Until parite(n)
            n = Console.In.ReadLine
        Loop

        For i As UInteger = 2 To n - 2
            If primalite(i) And primalite(n - i) Then
                Console.Out.WriteLine(i.ToString & "+" & (n - i).ToString & "=" & n.ToString)
            End If
        Next i

        Console.In.ReadLine()
    End Sub

    Function primalite(ByVal n As UInteger) As Boolean
        For i As UInteger = 2 To Math.Sqrt(n)
            If n / i = Int(n / i) Then Return False
        Next i
        Return True
    End Function

    Function parite(ByVal n As UInteger) As Boolean
        Return Not (n And 1) = 1
    End Function

Conclusion :

Une fois de plus je publie une très petite source, et ce car les algorithmes peuvent être intéressants et parce qu'ils peuvent permettre à quelqu'un qui ne la connaissait pas de s'intéresser à cette conjecture. Je vous avoue que je suis très friand de sources algorithmiques sur ce site !

Je ne suis pas sûr que cet algorithme le plus performant mais il a l'avantage de donner (il me semble) toutes les combinaisons possibles de sommes et d'éviter les doublons (7+7=14 et 7+7=14). Si vous voyez des améliorations n'hésitez pas, on est là pour ça !

Merci de votre attention ! Skanenruf.
PS. Les tests de parité et de primalité peuvent servir à d'autres algorithmes.

A voir également

Ajouter un commentaire

Commentaires

philm_be
Messages postés
2
Date d'inscription
mardi 13 juillet 2004
Statut
Membre
Dernière intervention
12 octobre 2009
-
Pour la fonction "primalite", rien ne sert de partir de n-1 me semble-t-il. Il suffit de commencer à la moitié de n. Tout ce qui est supérieur ne pourra forcément pas être un diviseur.
Philippe
philbar71
Messages postés
70
Date d'inscription
samedi 1 juin 2002
Statut
Membre
Dernière intervention
5 juillet 2013
-
Au passage je te signale que Julien39 travaille aussi sur la conjecture de Goldbach :
http://www.vbfrance.com/codes/TESTER-CONJECTURE-GOLDBACH-TOUT-NOMBRE-PAIR-SUPERIEUR-EST_32365.aspx

Bon courage pour la suite de tes recherches, mais ne néglige quand même pas ton français car dans un CV ou dans d'autres domaines c'est dans la qualité de l'écriture qu'on détectecte les meilleurs candidats.
jmocaro
Messages postés
14
Date d'inscription
mardi 25 mars 2003
Statut
Membre
Dernière intervention
19 octobre 2007
-
bonjour,
je pense que la deuxième boucle est inutile puisque de toute façon j=n-i
pourquoi boucler pour chercher un tel 'j' ?...
Il reste à tester que j(=n-i) est premier.
Cette première boucle peut s'arrêter à la moitié car i+j=j+i.

La primalité se teste de 2 jusqu'à la racine de n, c'est plus restrictif que la moitié.

Jean-Maurice
Skanenruf
Messages postés
38
Date d'inscription
dimanche 12 octobre 2008
Statut
Membre
Dernière intervention
30 juin 2010
-
Merci beaucoup pour vos réponses à tous les trois, j'en ai profité pour amélioré certains points :

- J'ai commencé par optimiser mon test de primalité avec comme limites du processus itératif : 2 et math.sqrt(n). (Merci Jmocaro et Philm_be).
- J'ai supprimé la seconde boucle de mon algorithme sur la conjecture forte (effectivement c'était inutile).
- J'ai ajouté un algorithme (sur la même base) pour la conjecture faible en utilisant cette fois deux boucles imbriquées ainsi que la méthode soustractive (n-i-j).

PS. Je rappelle que la conjecture faible est la même que la conjecture classique (forte) de Goldbach sauf que c'est pour les impairs supérieurs à 7 qui sont donc (on a conjecturé) égaux à une somme de trois nombres premiers (impairs).
jmocaro
Messages postés
14
Date d'inscription
mardi 25 mars 2003
Statut
Membre
Dernière intervention
19 octobre 2007
-
re bonjour,

on en finit jamais avec les améliorations,
cependant j'en propose une autre: le test de primalité coûte cher.
On pourrait imaginer de stocker si on a testé la primalité d'un entier, et son résultat. Dans une ou 2 collections par exemple (je suis VB6-iste...)
Ceci serait très profitable pour la conjecture faible.

à +

jmocaro

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.