Ulam-Spirale

Letztmalig dran rumgefummelt: 31.08.15 16:13:24

	Der Mathematiker Stanislaus M. Ulam (1909-1984) hat die Wissenschaft nicht nur um wichtige mathematische Sätze und Methoden - wie z. B. den Satz von Borsuk-Ulam und die Monte-Carlo-Methode, d. h. die Simulation mittels Zufallszahlen (siehe Rubrik Geschichte, in diesem Heft, S. 66) -, sondern auch um interessante Aufgaben, die in Zahlentheorie bzw. Unterhaltungsmathematik fallen, bereichert. Im Jahr 1963 musste Ulam, der damals am Los Alamos Scientific Laboratory arbeitete, einen (seiner Meinung nach) sehr langweiligen Vortrag anhören. Um sich die Zeit zu vertreiben, kritzelte er ein schachbrettartiges Gitternetz aufs Papier und nummerierte die einzelnen Felder gemäß einer - dem Uhrzeigersinn entgegengesetzten - Spirale. Ohne besondere Absicht kreiste er die Primzahlen ein - und stellte dabei zu seiner Überraschung fest, dass diese offenbar die Neigung besitzen, sich diagonal oder horizontal auf Geraden anzuordnen
	1. Problembeschreibung 2. Hintergründe und Zusammenhänge - Einordnung in Klassen 3. Lösungsalgorithmen 4. Programmvorschläge 5. Zusammenfassung 6. Weiterführende Informationen 7. Linkliste zum Thema 8. Verwandte Themen
	Probleme & Problemlösungsverfahren Stanisław Marcin Ulam Logo für die Ulam-Spirale begrenzt verwendbar - selbst aufpassen, ab welcher Stelle es Blödsinn wird ;-) Informatik-Profi-Wissen
	Quellen: LOG IN - Heft 2/98 Seite 70

1. Problembeschreibung

	Diese zufällige Entdeckung inspirierte Ulam, das Gleiche auch mit anderen quadratischen Spiralen zu versuchen. Im Rechenzentrum von Los Alamos waren die ersten 90 Millionen Primzahlen auf Magnetband gespeichert, und zudem verfügte der Computer MANIAC II sogar über eine grafische Ausgabe - damals noch eine Seltenheit. Zusammen mit den Kollegen Mark Wells und Myron Stein programmierte er den Computer so, dass die Vermutung an den Primzahlen zwischen 1 und 65 000 visuell überprüft werden konnte.
	Aufgabe: Es soll ein Programm geschrieben werden, das ein endliches Stück der Ulamspirale abbildet! Das Auge nimmt zuerst die diagonal verlaufenden Geraden wahr, die durch aneinander grenzende Felder ungerader Zahlen entstehen; es lässt sich aber auch deutlich eine Tendenz der Primzahlen zur Anordnung in horizontalen und vertikalen Geraden feststellen. Eine Gerade beliebiger Richtung trägt Zahlen, die sich durch ein quadratisches Polynom darstellen lassen; beispielsweise beschreibt 4x2 + 10x + 5 die Folge 5,19, 41, 71 für x = 0, 1, 2,3 (siehe Bild unten). Beginnt die Spirale nicht mit 1, sondern beispielsweise mit 17, werden die Diagonalen durch andere quadratische Polynome dargestellt; etwa im Fall n =17 durch das Polynom x2 + x + 17, das für x = 0, ..., 15 Primzahlen liefert. Eulers bekanntestes primzahlwertiges Polynom x2 + x + 41 kann auf ähnliche Art in einem Gitter dargestellt werden, wenn die Spirale mit 41 beginnt; es erzeugt 40 auf der Hauptdiagonale gelegene Primzahlen. Schon lange ist bekannt, dass von den ersten 2398 Zahlen, die durch dieses Polynom erzeugt werden, genau die Hälfte Primzahlen sind.
	Primzahlen auf der Ulam-Spirale

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

... erst einmal machen wir uns das ganze grafisch deutlich, reden anschließend über Datentypen, Ausgabeverfahren sowie da Speichern von Zwischenwerten. Hier kann man neben einfachen Verfahren auch das volle Datenspektrum einer Programmiersprache antasten - es wird dann wirklich so zu sagen alles gebraucht - vom ARRAY - über RECORD's bis hin zu dynamischen Variablen und/oder objektorientiertes Programmieren.

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é.
	Version von Johannes Uhlig: Programm zur Ermittlung der ULAM-Spirale - auch für große Zahlen Programm zur Ermittlung der ULAM-Spirale auch für große Zahlenx Programm zur Ermittlung auch großer ULAM-Spiralen - extrem laufzeitkomplex

5. Zusammenfassung

	Arndt Brünner's Primzahlseite

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 das 153-Problem - Narziß-Zahlen das Autoquadratzahlenproblem die Schmidtzahlen Pythagoräische Tripel Pascal-Zahlen die befreundeten Zahlen die Polynomzahlen die Goldbach-Vermutung 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

	http://www.mathematische-basteleien.de/kaprekarzahl.htm

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 28. Januar 2008