% Content-encoding: UTF-8
\documentclass[ngerman]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\setcounter{secnumdepth}{0}
\setcounter{tocdepth}{0}

\begin{document}

\title{Primzahlen und die Spirale von Ulam}
\author{Fred Behringer}
\maketitle

\begin{multicols}{2}

Eines sieht man sofort: Die von Michael Kalus (im vorliegenden Heft) angegebene Spirale ist rechtsdrehend, die angelsächsischen Spiralen (beispielsweise bei Weisstein, Eric W.: Prime Spiral) sind linksdrehend. Wir, die wir in einer dreidimensionalen Welt leben, können natürlich das Blatt, auf welchem die Spirale gezeichnet ist, einfach wenden. Und dann stellt sich der Unterschied als gegenstandslos heraus. (Was aber macht man aus dem vielzitierten Ausspruch \emph{die Natur (Teilchenspins etc) bevorzugt Linksdrehung}?) Soweit ein Einleitungsersatz, der zum Nachdenken anregen soll.

Wenn man mit redaktionellen Aufgaben beschäftigt ist, und VD--Korrekturarbeiten gehören dazu, dann hat man den Vorteil, dass man die Beiträge der Autoren schon zu einem sehr frühen Zeitpunkt zu Gesicht bekommt. Ich freue mich, dass Michael die Sache mit der Ulam--Spirale ans VD--Licht gezogen hat, und ich erlaube mir, ein paar Gedanken dazu schon jetzt zu Papier zu bringen. Ulams Spirale war bisher nicht Gegenstand meiner Überlegungen. Es ist aber sicher recht reizvoll, da einzusteigen. Gespannt bin ich auf alle Fälle darauf, was die anderen mathematisch Interessierten der FG dazu beitragen werden.

Michaels eigentliches Problem hinter seinem Artikel scheint das Problem der dynamischen Speicherzuteilung zu sein? Reservierter Platz für Arrays, die im Verlauf des Rechengangs anderen Arrays mit anderen Dimensionen Platz machen sollen. Bei mir waren es Ende der Sechziger--Jahre Matrizen im Umfeld der Linearen Optimierung (programmieren in ALGOL oder in FORTRAN, war da die Frage). Heute bringt mir diese Frage nichts mehr, aber interessieren tut sie mich nach wie vor.

Primzahlen sind ungeheuer wichtig! Das erhellt schon aus der Tatsache, dass mindestens fünf Mitglieder der Forth--Gesellschaft ihre E--Mails untereinander GPG--verschlüsselt (OpenPGP) austauschen --- und diese Art der Verschlüsselung macht stark von Primzahlzerlegungen Gebrauch.

Klar ist zunächst: Es gibt unendlich viele Primzahlen. Bevor ich zur Ulam--Spirale komme, hier der Versuch einer

Definition: $1$ wollen wir nicht zu den Primzahlen zählen, $2$ sei (die erste und einzige gerade) Primzahl. Eine natürliche Zahl (a positive integer) größer als $2$ sei per definitionem Primzahl, wenn sie sich nicht durch (mindestens) eine andere Primzahl (ohne Rest) teilen lässt.

Satz (Euklid, etwa um 300 v.Chr.): Sei $n$ irgendeine natürliche Zahl. Sei $M(n)$ die Menge der ersten $n$ Primzahlen. Dann gibt es eine Primzahl, die nicht Element von $M(n)$ ist.

(In dieser Behauptung steckt natürlich der (modernere und aber auch dehnbarere) Begriff \emph{unendlich viele} drin.)

Beweis: Man bilde das Produkt aller Elemente von $M(n)$ und addiere $1$. Die so entstandene Zahl, sie möge $m(n)$ heißen, lässt sich durch keine der in $M(n)$ enthaltenen Primzahlen teilen: Immer bleibt der Rest $1$. Es gibt zwei Möglichkeiten: Entweder $m(n)$ ist selbst Primzahl oder $m(n)$ lässt sich durch mindestens eine Primzahl teilen.

Angenommen, $m(n)$ ist Primzahl. Dann haben wir eine Primzahl konstruiert, die nicht Element von $M(n)$ ist, und der Beweis ist erbracht. 

Beispiel:\\
 $n=1,\\
 M(n)=\{2\},\\
 m(n)=3$.

Oder aber $m(n)$ ist keine Primzahl. Dann muss es nach Definition eine Primzahl
geben, wir wollen sie $p(n)$ nennen, durch die $m(n)$ (ohne Rest) geteilt werden 
kann. $p(n)$ kann nicht in $M(n)$ enthalten sein (da ja der Rest sonst $1$, und 
nicht $0$, wäre) und der Beweis (der Satzaussage) ist ebenfalls erbracht. 

Beispiel:\\
$n=8,\\
M(n)=\{2,3,5,7,11,13,17,19\},\\
m(n)=9699691=347*27953,\\
p(n)=347$.

(Man konzentriere sich auf das, was im Satz ausgesagt werden soll. Beispielsweise hat dieser Satz nicht die Aufgabe nachzuweisen, dass $347$ im eben genannten Beispiel eine Primzahl ist. Er behauptet nur, dass es (mindestens) eine Primzahl mit der genannten Eigenschaft gibt. Auch erhebt dieser Satz nicht den Anspruch, eine Konstruktionsmethode für die ersten $n$ Primzahlen zu liefern.)

Schlussfolgerung: Egal, wie groß wir $n$ wählen, immer gibt es eine Primzahl $p(n)$, die noch größer ist als alle in $M(n)$ enthaltenen Primzahlen.

Und jetzt zur Spirale von Ulam: Für das Weitere behandeln wir $2$ als Sonderfall.

Klar ist, dass jede Primzahl außer $2$ ungerade ist. 

Aus der Spirale von Michael mit den verhältnismäßig wenigen Elementen lässt sich immerhin Folgendes ablesen (Beweis aus der Spiralenkonstruktion heraus): 

(1) In jeder Zeile  wechseln sich die geraden und die ungeraden (natürlichen) Zahlen ab, in aufeinanderfolgenden Zeilen gegeneinander versetzt.

(2) In jeder Spalte wechseln sich die geraden und die ungeraden (natürlichen) Zahlen ab, in aufeinanderfolgenden Zeilen gegeneinander versetzt.

(3) Jede Diagonale, ob von unten links nach oben rechts oder von unten rechts nach oben links, besteht entweder aus lauter ungeraden Zahlen (wir wollen die betreffende Diagonale \emph{ungerade Diagonale} nennen) oder aus lauter geraden Zahlen (die betreffende Diagonale sei dann \emph{gerade Diagonale} genannt).

Für Diagonalen von unten links nach oben rechts gilt: Gerade Diagonalen wechseln sich mit ungeraden ab.

Für Diagonalen von unten rechts nach oben links gilt: Gerade Diagonalen wechseln sich mit ungeraden ab.

Gerade Diagonalen können offensichtlich keine Primzahlen ungleich $2$ enthalten.

Es wechselt sich also immer eine Diagonale, in der Primzahlen vorkommen (können), mit einer Leerdiagonalen ab, in welcher grundsätzlich keine Primzahl vorkommt. Von $2$ sehen wir dabei als Ausnahmefall ab.  

Schon die (verhältnismäßig kleine) Spirale von Michael legt die Vermutung nahe, dass es keine ungerade Diagonale ohne Primzahlen gibt. Bewiesen ist diese Vermutung mit solch einem Anfangsstück einer Spirale, so groß es auch gewählt sein mag, natürlich nicht.

Aus (1) bis (3) ersieht man, dass es keine Zeile und auch keine Spalte gibt, bei der von vornherein ausgeschlossen werden kann, dass sie Primzahlen enthält. 

Schon die (verhältnismäßig kleine) Spirale von Michael legt die Vermutung nahe, dass es keine Zeile und auch keine Spalte ohne Primzahlen gibt. (Eine Vermutung muss natürlich bewiesen oder widerlegt werden. Eine noch so gute Zeichnung kann keinen Beweis ersetzen.)

Bemerkenswert ist an den Primzahlen nicht, dass sie \emph{alle auf Diagonalen liegen}. Wo sollen sie sonst liegen? Sie liegen ja auch \emph{alle auf Zeilen} und sie liegen auch \emph{alle auf Spalten}.

Bemerkenswert ist der Eindruck, den man gewinnt, wenn man sich die 399x399--Spirale bei \url{http://mathworld.wolfram.com/PrimeSpiral.html} ansieht. Es sieht so aus, als ob man (in einem vorweihnachtlichen Bastelkurs) eine Tapete mit Kleister beschmiert und wahllos mit Druckerschwärze (aus einer Farbdruckerdüse) besprenkelt hat und dann einen feinmaschigen Kamm diagonal einmal so und einmal so hindurchzieht. Man wird bei der genannten größeren Spirale aus dem Internet das Gefühl nicht los, dass sich da Diagonallinien durch das Muster ziehen. 

Das ist kein großes Wunder: Jede zweite Zahl in einer Zeile und jede zweite Zahl in einer Spalte ist keine Primzahl. In den Zeilen und in den Spalten haben die (als Tintenpunkte dargestellten) Primzahlen je zu je mindestens den Abstand $2$ (mindestens ein Lücke dazwischen), während es überhaupt nicht einzusehen ist, warum in den ungeraden Diagonalen nicht ganze Strecken hinweg ein Punkt am anderen \emph{kleben} sollte. Was man bei den Diagonalen sieht, sind dann Bruchstücke einer Geraden, und das Auge ist leicht geneigt zu extrapolieren. Und noch viel \emph{schlimmer}: Durchs ganze Tableau hindurch wechselt sich immer eine aus Geradenbruchstücken zusammengesetzte Diagonale mit einer gänzlich leeren Diagonalen ab. (Richtig \emph{sehen} tut man das erst dann, wenn man darauf aufmerksam gemacht wird.)

Bei den Zeilen und bei den Spalten können keine ähnlichen Linienbilder entstehen: Jede zweite Zahl in einer Spalte ist gerade und damit (von $2$ mal abgesehen) keine Primzahl und nebeneinanderliegende Spalten sind in dieser Hinsicht versetzt. Entsprechend bei Zeilen.

Das Einzige, was einem verwunderlich vorkommen kann und Anlass zu Spekulationen gibt, ist der bei Betrachtung des Spiralenbildes leicht entstehende Eindruck, dass einzelne unter den Diagonalen (von rechts nach links wie von links nach rechts) vom Auge stärker erfasst werden und dass die so hervortretenden Diagonalen in ziemlich gleichen Abständen voneinander auftreten.

Noch ein schneller Gedanke zum Konstruktionsprogramm: Die Ecken der (an sich ja \emph{eckigen}) Spirale (bei Michael) sind: $1\ 2\ 3\ 5\ 7\ 10\ 13\ 17\ 21\ 26\ 31\ 37\ \ldots$ und die Abstände betragen: $1\ 1\ 2\ 2\ 3\ 3\ 4\ 4\ 5\ 5\ 6\ \ldots$ Die Diagonale durch $1$ von unten rechts nach oben links geht durch die \emph{Punkte} $1\ 3\ 7\ 13\ 21\ 31\ 43\ \ldots$ mit den Abständen $2\ 4\ 6\ 8\ 10\ 12\ \ldots$, und diese Abstände selbst haben voneinander den konstanten Abstand $2$.

\emph{Wie lassen sich in Forth die Primzahlen erkennen und markieren?},

lautet eine der Fragen, die Michael en passant in seinem VD--Artikel stellt. Hierzu fällt einem sofort das allgegenwärtige Sieb des Eratosthenes ein, zu dem es eine reichhaltige Literatur gibt. (Dieses Sieb wird auch gern als Messlatte (benchmark) für Rechengeschwindigkeiten verwendet.) Im VD--Heft 2/1998 steht ein Artikel von mir mit einem Forth--Programm, das Primzahlen auszusieben gestattet. (Martin Bitter entdeckte im VD--Heft 3/1998 ein paar Caveats bei der Übertragung nach ZF.) Ich erreiche das im Real--Mode unter DOS (1 Gigabyte über 32--Bit--Adressen linear anzusprechen, bereitet keine große Schwierigkeit und wird im Programm praktiziert). Das Programm arbeitet mit einem 16--Bit--Forth--System (Turbo--Forth). Man kann aus Geschwindigkeitsgründen natürlich nicht alles in High--Level--Forth programmieren. Aber der in Turbo--Forth eingebaute 16--Bit--Assembler genügt: \verb|EAX| führe ich über \verb|: EAX 66 C, AX ;| ein usw., und Ähnliches bei z.B. \verb|[EBX]| und den 32--Bit--Adressen. Ein expliziter 32--Bit--Assembler wird nicht benötigt. 

Im eben genannten VD--Heft 2/1998 findet man auch Hinweise auf zwei Artikel von mir aus den Jahren 1988 und 1989, in denen ich auf Forth und Primzahlen eingehe und beispielsweise das Sieb dadurch abkürze, dass ich die Vielfachen von 2 und die Vielfachen von $3$ von vornherein weglasse. Ein anderer Autor (Daniel Flipo, 1989) hat in Antwort darauf vorgeschlagen, auch die Vielfachen von $5$ wegzulassen. Da fängt es dann aber an, dass man Platz\-er\-spar\-nis und Aufwand gegeneinander abwägen muss.

$63963077\ 63963079$ sind Primzahlzwillinge. Um das herauszufinden, habe ich damals mit dem erwähnten Forth--Programm 30 Sekunden gebraucht. $3-5, 5-7, 11-13$ sind offensichtlich Primzahlzwillinge. Kann jemand den Nachweis darüber erbringen, dass es unendlich viele Primzahlzwillinge gibt? Kann jemand zeigen, dass es vielleicht nur endlich viele gibt? Kann jemand die Frage klären, ob diese Frage überhaupt entscheidbar ist? Und dann innerhalb eines welchen Systems?
\end{multicols}

\end{document}