Die Goldbach-Vermutung

Letztmalig dran rumgefummelt: 16.06.08 10:33:09

	Bis heute ist sie nicht bewiesen - deshalb ja auch: "Vermutung", wobei Gegenteiliges aber eben auch nicht bekannt ist - auch für derzeit noch so große geprüfte Zahlen ist keine Ausnahme entdeckt worden - ein schlüssiger Beweis existiert aber auch nicht. Sie ist benannt nach Christian Goldbach (1690 - 1764), der als Sekretär der Akademie in St. Petersburg einen regen Schriftwechsel mit vielen europäischen Wissenschaftlern führte. In der Fußnote zu einem Brief an Leonhard Euler (1707 - 1783) am 7. Juni 1742 sprach er die Vermutung aus, dass sich jede gerade Zahl größer als 2 als Summe von zwei Primzahlen schreiben lässt. Diese mehr als 250 Jahre alte Vermutung ist bis heute weder bewiesen noch widerlegt. Noch 1912 bezeichnete sie Edmund Landau (1877 - 1938), der zu seiner Zeit eine Art "Zahlentheorie-Papst" war, als "unangreifbar beim heutigen Stande der Wissenschaften". Schon 3 Jahre später gab es einen ersten Beweisversuch durch Jean Merlin. Sein Beweis war zwar fehlerhaft, seine Grundidee, das Sieb des Eratosthenes weiterzuentwickeln und mit Methoden aus Kombinatorik und Analysis zu kombinieren, hat sich aber als sehr fruchtbar erwiesen. 1920 konnte Viggo Brun (1885 - 1978) mit solchen Methoden zeigen: Jede genügend große gerade Zahl 2n lässt sich in der Form 2n = r + s schreiben, wobei r und s jeweils aus höchstens 9 Primfaktoren (mit Vielfachheit gezählt) bestehen. Jetzt musste man "nur noch" den Beweis so verbessern, dass man die Zahl 9 durch 1 ersetzen kann und hätte wenigstens für alle genügend großen 2n die Vermutung bewiesen. Den Rest könnte dann ein Computer erledigen. Es hat auch andere methodische Ansätze und Teilergebnisse gegeben, von denen wir in diesem kurzen Artikel nicht sprechen werden, um ihn nicht zu überfrachten. Um die Verbesserungen der Brun'schen Aussage knapp darstellen zu können, benutzen wir das "Stenogramm" (a, b) für die Aussage: Jede genügend große gerade Zahl 2n lässt sich in der Form 2n = r + s schreiben, wobei r aus höchstens a und s aus höchstens b Primfaktoren besteht.
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Literatur 7. Linkliste zum Thema 8. Verwandte Themen
	Probleme & Problemlösungsverfahren Logo für die Goldbach-Vermutung begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Quellen: LOG IN - Heft 4/1995 Seite 78

1. Problembeschreibung

	Den Nutzen des Computers erblicken wir u. a. im schnellen und fehlerfreien Ausführen vieler Rechenoperationen und in der Verwaltung großer Datenbestände. Hierin ist er dem Menschen weit überlegen. Wenn wir jedoch blind auf diese „Rechenmacht" des Computers vertrauen, werden wir möglicherweise (bei gewissen Problemen) nicht allzu weit kommen. Das folgende Beispiel mag zeigen, wie zwischen Mensch und Computer eine Art Arbeitsteilung möglich ist, wenn jeder dort eingesetzt wird, wo seine Stärken liegen. Problem Gesucht sind alle natürlichen Zahlen mit folgender Eigenschaft: Jede der Ziffern von 1 bis 9 kommt genau einmal vor, und die aus den ersten n Ziffern gebildete Zahl ist durch n teilbar (n = 1, 2,..., 9). Beispiel: Sei a = 724891356. Die erste Bedingung ist offenbar erfüllt, wie steht es mit der zweiten? Es ist 7 durch 1 teilbar, 72 ist durch 2 teilbar, aber leider ist 724 nicht durch 3 teilbar. Die Zahl a tut es also leider nicht.
	Aufgabe: Obiges Problem soll gelöst werden, und zwar durch ausschließlichen Computereinsatz (Programm), indem das Problem durch Nachdenken reduziert wird. und der Computer lediglich die Restarbeit erledigt, ausschließlich durch Nachdenken Erarbeiten Sie das Programm und schildern Sie Ihre Gedankengänge. Worin unterscheiden sich Mensch und Maschine beim Problemlösen?
	Primzahlen auf der Ulam-Spirale

2. Hintergründe, Zusammenhänge - Einordnung in Klassen

	Auf den ersten Blick ganz simpel - aber da hängt noch der Nebel der letzten Nacht vor Augen. Schon ein zweiter Blick belehrt uns darüber, dass die Aufgabe alles andere als simpel ist. Allein der Algorithmus zu Untersuchung aller in Frage kommenden Zahlen bereitet einige Probleme, obwohl die Sache an sich simpel ist.
	die Starke Golbachvermutung besagt, dass sich jede gerade Zahl größer 2 aus der Summe zweier Primzahlen ergibt. die Schwache Goldbachvermutung besagt, dass sich jede ungerade Zahl größer 5 aus der Summe dreier Primzahlen ergibt.

3. Lösungsalgorithmus

4. Programmvorschläge

	Vom Informatikkurs der Jahrgangsstufe 12 des Schuljahres 2007/08 wurden per Projektarbeit einige solcher Algorithmen erstellt und werden hier nun zusammengefasst sowie präsentiert. Besonders interessante Lösungen kamen aus dieser Gruppe oftmals von Johannes, Eric aber auch von André. Für die nachfolgende Lösung mit hoher Stellenzahl zeichnet Eric Kreller allein verantwortlich.
	Achtung: die Anwendung lässt sich nicht direkt starten, sie muss auf den Desktop kopiert werden erzeugte Datei ist ein Textfile und kann schon bei 1.000.000 extrem groß werden - also kleinere Dimensionen angeben
	Programm zum Nachweisversuch der Goldbach'schen Vermutung Liste mit Nachweis der starken Goldbach'schen Vermutung für 1656 Liste mit Nachweis der schwachen Goldbach'schen Vermutung für 215 Programm zum Nachweisversuch der Goldbach'schen Vermutung als ZIP-Archiv startbares Programm zum Nachweisversuch der Goldbach'schen Vermutung

5. Zusammenfassung

6. Weiterführende Informationen

	War 'ne tolle Sache (zumindest für mich als Lehrer), einmal ein Schuljahr lang mit Schülern über doch die Grenzen von Programmiersprachen tangierende Probleme zu diskutieren, diese auszuloten, Algorithmen zu finden und wieder wegzuwerfen. Dümmer geworden ist dabei wahrscheinlich keine der betroffenen Seiten, die Schüler werden's teilweise einige Monate später an Universitäten bemerken ;-) Alles war im Rahmen des Möglichen: es anstrengend (was es ja sein soll), aber machbar - unten kann man einige Ergebnisse einsehen. Alles, was präsentiert wird, ist Wissensstand  Juni 2008 ;-)
	die Primzahl-Zwillingssuche der Kaprekar Algorithmus die befreundeten Zahlen das Autoquadratzahlenproblem die Schmidtzahlen Pythagoräische Tripel Ulam-Spirale die Polynomzahlen Pascal-Zahlen das 153-Problem - Narziß-Zahlen das Palindrom Spiegelsummen-Problem die Perfect Numbers
	die Zahlenteiler GGT KGV   die Primzahlsuche - zumindest die ersten Beschreibungen sind trivial ;-) die Pseudoprimzahlen Quersummenermittlung Primzahlfaktorisierung

7. Links zum Thema

	Das wird vorläufig ganz harmlos anfangen aber im Laufe der zeit sicher heftig zunehmen. Mit der Goldbachvermutung lässt sich ja 'ne Menge ärgerliches programmieren und genau das werden wir nun in der nächsten Zeit auch tun ;-)
	http://de.wikipedia.org/wiki/Goldbachsche_Vermutung

8. Verwandte Themen

	Das Vorangestellte hilft wirtschaften, löst jedoch kein einziges Problem (allerdings ohne Beachtung der Worst-Case-Strategien wird man auch nicht erfolgreich Software entwickeln und/oder informatische Projekte realisieren können). Deshalb nunmehr das, was wirklich Arbeiten hilft.
	das 8-Dame-Problem des Cliquen-Problem Domino-Problem das Entscheidbarkeitsproblem das Erfüllbarkeitsproblem die Fibonacci-Zahlen das Flaggenproblem das Halteproblem das Hamilton-Problem das K-Farben-Problem der Kaprekar-Algorithmus die Magischen Quadrate das PASCAL'sche Dreiecksproblem das Philosophenproblem das Königsberger-Brückenproblem das Post'schen Korrespondenzproblem das Rundreiseproblem das Springer-Problem die Türme von Hanoi das Wortproblem das Wüstenfit-Problem das 153-Problem
	Worst-Case-Denken Algorithmentheorie Komplexität, Mächtigkeit und Aufwand Praktische Elementaralgorithmen Lösbarkeit und Problemlösungsstrategien Klassische algorithmisch lösbare Probleme Zufall und Computer Graphentheorie Petri-Netze
	Informationsbegriff Logo für die Signale Nachrichten Wissen Systembegriff Modellbegriff Simulation Denken und Sprache Zahlen, Daten und Datentypen Gegenläufigkeit und Verklemmung Pattern-Matching

zur Hauptseite

© Samuel-von-Pufendorf-Gymnasium Flöha

© Frank Rost am 20. März 2008