Goldbach-Vermutung

Eine Vermutung ist, als eine Erklärung, wohl wahr, aber noch nicht bewiesen. Ein Votum zeigt ihre Gültigkeit zu einem Satz. Goldbach-Vermutung ist eine der ältesten Probleme zu lösen, reicht zurück bis 1742, war ausgesprochen Goldbach von Euler auf und wie folgt neu gefasst:

Jede natürliche Zahl größer als 2 kann "zwei der Ausübung geschrieben als die Summe
Primzahlen.

Zum Beispiel:
4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 3 + 7 = 5 + 5
12 + 5 = 7
14 = 3 + 11 = 7 + 7
16 = 3 + 13 = 5 + 11

Versucht, seine Unrichtigkeit nachzuweisen

Auf eine Vermutung wir zwei Arten von Demonstrationen machen kann, beweisen wir die Korrektheit oder seine Ungenauigkeit. Offensichtlich schließt man das andere. Wir werden versuchen zu beweisen, dass die Vermutung falsch ist, dies zu tun, nur um ein Gegenbeispiel Leinwände, dass die Aussage falsch ist, zu finden. Also in unserem Fall nur eine einzige Zahl zu finden, die nicht die Summe von zwei Primzahlen. Zur Ermittlung dieser Zahl wird ein Programm zu schreiben.

Einige Überlegungen

Alle Primzahlen sind außer 2 ungerade. Dies ist für die Definition der ungeraden Zahl wahr. Die Primzahl 2 hinzugefügt, um eine andere Zahl als erstes Ergebnis aus einer ungeraden Anzahl. Der einzige Fall, in dem 2 weitere hinzu Primzahl wäre in einer geraden Anzahl Ergebnis ist 2 + 2. Daraus folgt, dass 4 die einzige Zahl, die als die Summe der Primzahl 2 mit einer weiteren Primzahl geschrieben werden kann. Das Programm zunächst ohne Berücksichtigung der Zahlen 2 und alle geraden Zahlen größer als vier.

Zerlege das Problem in sub Probleme

Aktionen, die das Programm kann in einer Abfolge von Phasen Schematisierung macht:

  1. Hier finden Sie alle Primzahlen von 3 bis n
  2. Nehmen Sie alle Paare von Primzahlen (P1, P2), so dass ihre Summe nicht überschreitet n (dh, P1 + P2 <= n) und wir betrachten (P1, P2), dann wird) werden verworfen (P2, P1.
  3. Mark den gleichen 6-zu n, wenn sie das Ergebnis von P1 + P2 für jedes Paar (P1, P2) gefunden zuvor.
  4. Drucken Sie alle geraden Zahlen sind nicht als Summe von Primzahlen markiert.

Sieb des Eratosthenes

Grim für alle Primzahlen von 3 bis n gibt es eine uralte Methode Eratosthenes bekannt als das Sieb des. Es ist zu schreiben, n alle Zahlen von 2 bis und löschen Sie dann alle Vielfachen von 2 (ausgeschlossen), alle Vielfachen von 3 (ausgeschlossen), alle Vielfachen von 5 (nicht im Lieferumfang enthalten) und so weiter. Die Zahlen "Überlebenden" sind alle und nur die Primzahlen zwischen 2 und n.

Dann verwenden wir einen Vektor v Flagge, die Idee und das "einfache, markieren wir alle Vielfachen der Zahlen 2, 3, 5, etc. .. so werden zunächst die übrigen. Um Speicherplatz zu sparen habe ich von dem Träger von drei und untersucht nur die ungeraden Zahlen, zB:

Index Transportunternehmen (s): 0 1 2 3 4 5 6
Informationen (j): 3 5 7 9 11 13 15
v [i]: TTTFTTF

IAJ verwenden, um die Funktion j = 2 * i + 3-Switch
Umgekehrt i = (j - 3) / 2
Hinweis: J - 3 immer eine Zahl teilbar durch zwei als ij alle ungerade sind. 

  long int n ) { void riempi_v (long int n) (
   k ; int i, k;
   i = 0 ; i < Size ( n ) ; i ++ ) { for (i = 0; i <size (n) i + +) (
     v [ i ] == TRUE ) if (v [i] == TRUE)
       k = 3 ; ( 2 * i + 3 ) * k < n + 2 ; k = k + 2 ) for (k = 3, (2 * i + 3) * k <n + 2 k = k + 2)
         i * k + 3 * k - 3 ) / 2 ] = FALSE ; v [(2 * i * k * k + 3-3) / 2] = false;
   )
 )

Backtracking-Algorithmus

Sobald der Vektor v Ich weiß, was sind die Primzahlen bis n.
Jetzt finde ich alle Paare (P1, P2). Um dies zu tun mit einem Algorithmus, dass die Methode des Backtracking verwendet. Der Algorithmus "Beschneiden" der Baum Rekursion, so dass sie nicht der Ansicht, alle Paare von Zahlen, die nicht interessieren Sie. So zu sein wie möglich optimiert, würden wir erkennen, dass die Optimierung dieses Programms unerlässlich ist, wenn wir gute Ergebnisse erzielen werden. 

  / * Summe und Finden Sie alle Paare von Primzahlen gefunden * oben /
 long int n , int i , int p1 , int p2 ) { void backtraking (long int n, int i, int p1, int p2) (
   int x;
   i == 2 ) { if (i == 2) (
     p2 ) / 2 ] = FALSE ; gleich [(P1 + P2) / 2] = false;
     / * Printf ("(% d,% d) \ n", P1, P2) * /
   )
   andere (
     i == 0 ) if (i == 0)
       x = 3 ; x != - 1 ; x = primo_successivo ( n , x ) ) { for (x = 3, x! = - 1, x = primo_successivo (n, x)) (
         i + 1 , x , p2 ) ; backtraking (n, i + 1, x, p2);
       )
     sonst
       / ** 
         * Initialize x P1 ist Goldback Überprüfung der Vermutung. 
         * Place primo_successivo x = (n, P1), gleiche finden Sie alle 
         * Daten aus P1 + P2 mit P1! P2 = 
         * /
       x = p1 ; x != - 1 ; x = primo_successivo ( n , x ) ) { for (x = p1 x! = - 1, x = primo_successivo (n, x)) (
         p1 + x <= n ) if (p1 + x <= n)
           i + 1 , p1 , x ) ; backtraking (n, i + 1, P1, x);
         ; sonst brechen;
       )
   )
 )

Gefunden das Paar (P1, P2) ist die Summe und Aktualisierung der gleichen Fluggesellschaft. Der Träger hat auch Größe n / 2, jedes Element entspricht einer geraden Zahl entspricht.

Wir entwickelten den Nummern 1, 2 und 3 der unser Problem, wir haben durch den Vektor der Gleichbehandlung navigieren und drucken nur den Index in der Gegenwart eine gerade Zahl, die nicht die Summe von zwei Primzahlen. 

  i = 0 ; i < n / 2 ; i ++ ) for (i = 0; i <n / 2; i + +)
     pari [ i ] == TRUE ) if (gleich [i] == TRUE)
       "%d:i = %d \n " , pari [ i ] , 2 * i ) ; printf ("% d: i =% d \ n", dass [i], 2 * i);

Ergebnisse

Sie werden bemerken, dass der Tests effettaundo wachsendem n steigt die Ausführungszeit. Mit einem Computer auf Intel 5.336,88 bogomips verbrachte ich 5 Tage mit n gleich 100.000.000.

Goldbach-Vermutung sein soll durch die Tatsache wahr, dass die Wahrscheinlichkeit für eine gerade Zahl als Summe zweier Primzahlen steigt mit der Anzahl. Es ist ein Distributed Computing Projekt, das * hat bisher bestätigt die Vermutung, die bis zu 2 10 17 (wenn ich schreibe.)

Eine weitere Vermutung

Ich will nicht mich, sondern Euler und Goldbach-Vermutung, dass andere vielleicht interessant finden, dass ich seine Meinung Passt beim Schreiben des Programms vergleichen. Goldbach ist eine Verfeinerung der Äußerung.

Alle natürlichen Zahlen größer als 6 und kann auch P1 und geschrieben werden als Summe von zwei Primzahlen, so dass P2 P1 P2 unterscheidet sich von

Es ist dein Beweis. Ich kann Ihnen versichern, dass bis zu 10 8 ist wahr.

2 Responses to "Goldbach-Vermutung"

  1. Chemla - 6. März 2009

    Bonjour Linux!
    De voir que le très glücklich du monde à cette Free interessiert Vermutung. Je travaille en autour Amateur depuis 3 ans et demi et environs toutes mes zur Einlieferung Errances (!) À l'adresse http://denise.vella.chemla.free.fr .
    Ein großer Nachsicht feuilleter avec une ...
    Toute aide, Suggestion, bienvenue Remarque die Nacht.

    Logiciel libre et que lebendig!
    Denise

  2. Thegamer - 24. März 2009

    Wirklich schön ... ich kann nicht warten, um den Code zu versuchen!

Lassen Sie eine Antwort