Computergrafik

Fibonacci-Rechtecke

Fibonacci_RechteckeEine kleine Spielerei mit der bekannten Zahlenfolge:

Nimm die Folge (Fn) =  0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,… (n = 0, 1, 2 , 3 …) der Fibonacci-Zahlen1 und bilde die Produkte benachbarter Zahlen 0×1 = 0, 1×1 = 1, 1×2 = 2, 2×3 = 6, 3×5 = 15, 5×8 = 40, usw. Die Produkte 0, 1, 2, 6, 15, 40, usw. sind die Flächeninhalte der so genannten Fibonacci-Rechtecke2 mit den Seitenlängen (0,1), (1,1), (1,2), (2,3), (3,5), (5,8), ….  Addiere die ersten n Flächeninhalte. Dann entsteht die Zahlenfolge (an) =  0, 1, 3, 9, 24, 64, 168, 441, 1155, 3025, …, die Summe der Fläche der ersten n Fibonacci-Recktecke3.  In der Abbildung sind die Fibonacci-Rechtecke spiralförmig aneinander gelegt. Man erkennt sofort, dass jedes zweite Rechteck die bisher angelegten zu einem Quadrat ergänzt. Das heißt, jedes zweite Glied der Folge (an) ist eine Quadratzahl: 1 = 12, 9 = 32, 64 = 82, 441 = 212 und 3025 = 552, und zwar das Quadrat einer Fibonacci-Zahl mit geradem Index: 12 = F22, 32  = F42, 82 = F62, 212 = F82. Beweis durch vollständige Induktion.

Die Fibonacci-Rechteck-Spirale ist sicher keine Entdeckung von mir. Ich habe sie aber bisher in der Literatur noch nicht gefunden. Wen es interessiert, zwei kleine Notizen zum Thema: Fibonacci-Folge und Goldener Schnitt und Formel von Moivre/Binet. Oder wie wär’s mit einem Ausflug in die Lineare Algebra: Moivre/Binet (Beweis mit LA) .

… und da gerade das Stichwort “Fibonacci” fällt, hier noch ein Nachtrag zur Jahreszahl 2017. Nach Zeckendorf kann jede natürliche Zahl n  > 0  eindeutig als Summe voneinander verschiedener, nicht direkt aufeinanderfolgender Fibonacci-Zahlen geschrieben werden. Die Zeckendorf-Zerlegung unserer Jahreszahl ist 2017 = 1597 + 377 + 8 + 1.

 

1     The On-Line Encyclopedia of Integer Sequences (A000045)
2     a. a. O., (A001654)
3     a. a. O., (A064831)

Teppiche mit gesiebten Zahlen

Die Themen Primzahlteppiche und Eulersches Primzahlpolynom beschäftigen mich noch immer. Die Idee des Primzahlteppichs stammt von Bartolomé, Rung und Kern1. In ihrem Buch über Zahlentheorie ist ein Koordinatensystem abgebildet, in dem die Punkte markiert sind, für die der Wert des Terms T(x, y) = x2 + y2 eine Primzahl ist. Das Muster der Punkte lässt zwar keine große Ordnung erkennen (abgesehen von den trivialen Symmetrien bezüglich der Koordinatenachsen und des Nullpunkts), ist aber nicht zufällig. Variiert man T(x, y), entstehen andere Grafiken.

RandomPrimeTeppich_02_weiss(1)  Hawkins Primes

 

 

 

 

 

 

 

 

 

LuckyNumberTeppich_05_weiss(2)  Lucky Numbers

 

 

 

 

 

 

 

 

 

Primzahlteppich_xxplusy_03(3)  Primzahlen

 

 

 

 

 

 

 

 

 

Zahlenteppiche:  (1) Random Primes, (2) Lucky Numbers und (3) Primzahlen, siehe Text. Ein Klick auf die Abbildung vergrößert sie.

Meine Idee: Ich erweitere den Begriff des Primzahlteppichs auf den des Zahlenteppichs. Zahlenteppiche sind denmach kartesische Koordinatensysteme, in denen diejenigen Punkte (x, y) markiert werden, für die der Wert eines geeigneten Rechenterms T(x, y) eine Zahl mit einer beliebigen, vorgegebenen Eigenschaft ist. Die Eigenschaft, Primzahl zu sein, wäre somit ein Spezialfall. Wählt man den “richtigen” Term T(x, y), so dachte ich, müsste es möglich sein, interessante Teppichmuster auch für Zahlenmengen zu erzeugen, die sich durch andere Eigenschaften auszeichnen als prim zu sein.

Ich wähle den Term T(x, y) = x + y2. Er liefert einen interessanten Primzahlteppich (dargestellt im Artikel Eulersches Primzahlpolynom). Die  Primzahlen werden bekanntlich durch ein Siebverfahren erzeugt, benannt nach seinem Entdecker Eratosthenes. Deshalb liegt es nahe, Zahlen zu testen, die auch durch ein Siebverfahren entstehen. Da gibt es zunächst die  „Glücklichen Zahlen“ (engl. Lucky Numbers2). Sie entstehen durch ein Sieb ähnlich dem des Eratosthenes. Es streicht aber die Zahlen im Sieb nicht aufgrund ihres Wertes (wie bei Eratosthenes), sondern aufgrund ihrer Position. Als dritte durch Sieben erzeugte Zahlenmenge soll die Folge der Hawkins Primes3 (oder Random Primes) betrachtet werden. Hawkins’ Sieb ist eine nicht-deterministische, vom Zufall gesteuerte Methode, unter den jeweils verbliebenen Zahlen zu streichen. Hier eine genaue Beschreibung der drei genannten Siebe.

Die Teppiche zum Term T(x, y) = x + y2, die den genannten Zahlenmengen Primzahlen, Lucky Numbers und Hawkins Primes entsprechen, sind oben dargestellt. Das Ergebnis ist nicht umwerfend (leider), bestätigt aber unsere intuitive Vorstellung von Ordnung und Chaos in den drei Mengen. Wie erwartet, zeigt der Teppich der Hawkins Primes (Abbildung 1, oben) keinerlei Abweichungen von einer Zufallsverteilung. Die „Glücklichen Zahlen“ (Lucky Numbers) in Abbildung 2 (Mitte) dagegen lassen schon Ketten von Punkten in Richtung der Haupt- und Nebendiagonale erahnen. Im Teppich der Primzahlen (Abbildung 3, unten) schließlich sind diese Ketten zahlreicher und länger geworden – jedenfalls deutlich sichtbar. Zwei dieser Ketten entsprechen den Eulerschen Primzahlen x2 ±  x + 41, in der Abbildung durch die Farbe Magenta hervorgehoben. Für  x < 41 haben sie keine Lücken, bestehen also ausschließlich aus Primzahlen. Für  x > 40 ist die überdurchschnittlich große Häufung der Primzahlen auf dem oberen Ast deutlich zu sehen. Die mit grün markierten Primzahlpunkte gehören zu den Termen x2 ±  x + 101 bzw. x2 ±  x + 107. Siehe, wie schon erwähnt, den Beitrag Eulersches Primzahlpolynom.

 

1  Bartolomé, Andreas, Josef Rung und Hans Kern: Zahlentheorie für Einsteiger (Vieweg 1995), S.  75.
2  Hawkins, D., Briggs, W.E.: The Lucky Number Theorem, Mathematics Magazine 31 (1957), 81 – 84, 277 – 280.
3  Hawkins, David: The Random Sieve, Mathematics Magazine 31 (1957), 1 – 3.

Die Straßen von San Francisco …

Greenwich St_SF_Bild… benutze ich, um mein neues Computerprogramm zu testen. Es geht wieder einmal um die (zentral-) perspektivische Abbildung. Ein einfaches Programm, stellt Quader in Übereckansicht, in Frosch- und Vogelperspektive dar, berechnet Fluchtpunkte und Fluchtlinien, und zeichnet den zur Blickrichtung  gehörenden Horizont. Keine realistischen Ansichten, nur Ränder und Umrisse werden angedeutet. Dem Augenschein nach rechnet es korrekt. Auf dem Bildschirm erscheint der Quader mit einem, zwei oder drei Fluchtpunkten, von oben, von unten und von der Seite, aus der Nähe, aus der Ferne – Ansichten, wie man sie aus dem Lehrbuch kennt.  Aber wie ist es mit ungewöhnlichen Perspektiven? Auch sie sollten richtig wiedergegeben werden. Zum Beispiel Straßen mit starkem Gefälle und/oder großer Steigung  – und solche gibt es in San Francisco zuhauf. Zum Test wählen wir die Greenwich Street in der North Beach Area, eine Parallelstraße der bekannten Lombard Street.

 

Das Foto zeigt den Blick entlang der Greenwich St. , vom Pioneer Park auf dem Telegraf Hill hinüber zum Russian Hill. Der Pioneer Park liegt auf einer Höhe von etwa 60 m. Von hier aus geht es, mit Unterbrechungen durch die Querstraßen Grant und Stockton, bergab zur Powell St. Wir befinden uns jetzt auf  einer Höhe von ca. 20 m. Auf diesem Niveau bleibt die Greenwich St. bis zur Taylor St. (und kreuzt dabei die Columbus Avenue). Danach steigt sie wieder an bis zur Hyde St., die hier am Lombard St. Reservoir vorbeiführt. Der Wasserspeicher liegt an der Leavenworth St. auf einer Höhe von etwa 100 m – und damit ungefähr 40 m oberhalb des Kamerastandortes.

Greenwich St_SF_Fluchtlinien_und_ BildDieses Höhenprofil erhält das Programm als Eingabendaten. Ausgeben soll es die Ränder der Greenwich St. und, bis zur Kreuzung mit der Grant St., auch eine Andeutung der Dachhöhen der Häuser. Das zweite Bild zeigt,  was der Computer errechnet hat. Es sieht vernünftig aus. Die Dachhöhen- und Bodenlinien der Häuser im Vordergrund habe ich bis zu ihrem Fluchtpunkt verlängern lassen (rote Linien). Der liegt erwartungsgemäß sehr weit unten im Bild (Andere Fluchtpunkte sollte das Programm der Übersichtlichkeit halber nicht einzeichnen). Der Horizont ist die grüne waagerechte Linie im oberen Viertel des Bildes.  Vergrößert man das Foto, sieht man, dass er mit dem Niveau der Leavenworth St. zusammenfällt. Die verläuft dort in etwa 60 m Höhe – Horizont und Kamerahöhe stimmen also überein, wie es die Perspektive  verlangt. Fazit: wenn sich jetzt noch bugs im Code aufhalten, haben sie sich gut versteckt. Der Computer rechnet mit großer Wahrscheinlichkeit richtig.

Ein Abriss der Mathematik, nach der das Computerprogramm arbeitet, hier.

Eulers Primzahlpolynom

Setzt man im Term x2 x + 41 nacheinander x = 1, 2, 3, usw. bis x = 40, so erhält man die Zahlen 41, 43, 47, 53, usw. bis 1601, die allesamt Primzahlen sind. Dasselbe gilt für den Term x2 + x + 41. Das war schon Euler1 (1772) bekannt. Der Term wird deshalb auch nach ihm benannt (Eulersches Primzahl-Polynom). Für Werte x > 40 liefern er zwar keine ununterbrochene Folge von Primzahlen, aber immerhin etwa 7mal mehr als ein Zufallsgenerator, der vergleichbar große Zahlen erzeugt2. Man kann diese Eigenschaft grafisch darstellen. Die Idee dazu ist der „Primzahlteppich“, eine mathematische Spielerei, die von Bartolomé, Rung und Kern in ihrem Buch über Zahlentheorie beschrieben wird3.

Euler_Primzahlteppich_01

Deren Primzahlteppich ist ein Koordinatengitter, in dem diejenigen Punkte (x, y) markiert werden, für die beispielsweise die Summe x + y, das Produkt xy oder irgendein anderer Rechenterm T(x, y) eine Primzahl ist. Die Abbildung zeigt den von mir gefundenen Teppich, der die Primzahlen des Eulerschen Polynoms zu Tage treten lässt. Er wird von T(x, y) = x2 + y erzeugt. „Normale“ Primzahlen sind durch graue Karos gekennzeichnet, Eulersche durch Färbung in Magenta hervorgehoben. Man erkennt eine Häufung der grauen Karos, d. h. der “normalen” Primzahlen, auf Streifen in Richtung der Haupt- und Nebendiagonalen (und auf einigen Parallelen zur x-Achse). Wie erwartet, liegen auch die Eulerschen Primzahlen auf Diagonalen: Der magenta gefärbte Streifen, der in der unteren Hälfte am linken Rand beginnt und unter 45° nach rechts unten verläuft, entspricht der Gleichung y = 41 – x. Setzt man dieses y in den Term T(x, y) = x2 + y  ein, entsteht das Eulersche Polynom P(x) =  x2x + 41. Ersetzt man x durch  - x, entsteht P(x) =  x2 + x + 41. Diesem Polynom entspricht der magentafarbene Streifen, der unter 45° nach rechts oben verläuft. Die Grafik zeigt, dass beide Streifen für x ≦ 40 keine Lücken haben, also ausschließlich aus Primzahlen bestehen. Für  x > 40 ist die überdurchschnittlich große Häufung der Primzahlen auf dem oberen Ast deutlich zu sehen.

1 Euler, Leonhard, zitiert in http://de.wikipedia.org/wiki/Primzahl.
2 Hardy, Godfrey H.  und  John E. Littlewood,  zitiert in http://en.wikipedia.org/wiki/Ulam_spiral.
3 Bartolomé, Andreas, Josef Rung und Hans Kern: Zahlentheorie für Einsteiger (Vieweg 1995). Siehe auch meine eigenen Primzahlteppiche.

Zufalls-Grafiken: Linie und Fläche 2.0

2015_04_18_Polygone_14

Mein Computer hat sich zum Thema “Alles Zufall: Linie und Fläche” etwas Neues ausgedacht. Er zeichnet jetzt an Stelle der Quadrate, Rechtecke und Kreise zufallsgesteuerte Vielecke (Polygone) und füllt diese mit Farben aus. Position und Größe der Vielecke (und die Anzahl der Ecken) werden wiederum mit Hilfe eines Zufallszahlengenerators bestimmt.

Man erhält Grafiken, die an Glasfenster erinnern. Hier einige Beispiele.

Alles Zufall: Linie und Fläche

2015_01_15_Rechtecklandschaft_01

Malen und Zeichnen sind verschiedene Dinge. In der Fläche herrscht die Farbe, bei der Linie kommt es u. a. auf die (Strich-)Stärke an. Beide können trotzdem harmonisch zusammenarbeiten. Das Ineinandergreifen von disegno e colore (Zeichnung und Farbe) lässt sich anhand von Computergrafiken studieren. Dazu habe ich ein kleines Java-Programm geschrieben – und dabei auf die vielen Grafik-Bibliotheksfunktionen dieser Sprache zurückgegriffen. Es erzeugt ein abstraktes „Bild“, in dem Farbe und Linie, Kontur und Strichstärke nach dem Zufallsprinzip variiert werden.

Direkt zur Galerie dieser Bilder.

Jugendstil aus dem Computer

Jugendstil_05

Linien, die seltsam verschlungen nach oben streben und dort in Blätter- oder Blumenornamenten enden, das ist für viele der Inbegriff des Jugendstils¹. Offenbar hat mein Computer eine ähnliche Vorstellung von dieser Kunstrichtung. Beim Spielen mit dem Feigenbaum-Programm stieß ich per Zufall auf jugendstilartige “Spaghetti”-Grafiken. Sie sind erweiterte “Endzustandsdiagramme”, die ein zweistufiger Feigenbaum-Algorithmus erzeugt. Verbale Formulierung des Algorithmus und Liste der Parameterwerte.

 

¹ Selbstverständlich beschränkt sich der Jugendstil nicht auf seltsam veschlungene Blätter- und Blumenornamente als Stilelemente – und die vom Computer berechneten Grafiken sind auch nur sehr entfernt mit Jugendstilornamenten verwandt. Verzeihung, liebe Kunsthistoriker, für die saloppe Formulierung.

Weihnachtslied und 2-Quadrate-Satz

QuadratSummenMod17A

Zum Gitterpunktsatz

 Pierre de Fermat entdeckte, dass Primzahlen größer als 2 sich genau dann in eine Summe aus zwei Quadraten zerlegen lassen, wenn sie sich in der Form 4n + 1 (n ∈  N ) darstellen lassen – oder, als Satz formuliert: Eine Primzahl p größer als 2 lässt sich dann und nur dann in eine Summe aus zwei Quadratzahlen zerlegen, wenn sie bei der Division durch 4 den Rest 1 lässt, wenn also gilt  p ≡ 1 (mod 4). Beispiele: 5 = 12+ 22 oder 13 = 22+ 32. Der Satz ist unter dem Namen Zwei-Quadrate-Satz in die Geschichte der Zahlentheorie eingegangen und, wie man liest, eines der Highlights dieser Disziplin. Ian Stewart hat den Beweis dieses Satzes in eine humorvolle „Nacherzählung“ von Charles Dickens „Ein Weihnachtslied in Prosa“ (A Christmas Carol in Prose) eingebettet1.

Er greift dabei, wie vielfach üblich, auf einen weiteren berühmten Satz der Mathematik zurück, den Minkowskischen Gitterpunktsatz. Der ist an Anschaulichkeit nicht zu übertreffen und verlangt geradezu danach, computergrafisch dargestellt zu werden. Ich konnte nicht widerstehen und habe einige Computerzeichnungen in Anlehnung an den Artikel von Stewart programmiert. Die Abbildung zeigt ein Beispiel.

Ulams Primzahlspirale

UlamsPrimzahlspirale500

Ulams (viereckige) Primzahlspirale. Die natürlichen Zahlen werden, in der Mitte mit 1 beginnend, der Reihe nach spiralförmig im Gegenuhrzeigersinn eingetragen. Hier sind es die Zahlen bis einschließlich 121 in der rechten unteren Ecke.

Wir nehmen ein Blatt kariertes Papier zur Hand und tragen die natürlichen Zahlen der Reihe nach in die Karos ein. Den Anfang macht die 1 in der Mitte des Blattes. Rechts davon wird die 2 platziert, im Kästchen darüber die 3 und links davon die beiden Zahlen 4 und 5. Die 6 und 7 belegen die Karos unterhalb der 5, und die 8 wird rechts von der 7 eingetragen, usw.  Das heißt, wir bewegen uns im Gegenuhrzeigersinn auf einer (viereckigen) Spirale nach außen. Geraten wir an eine Primzahl, wird das zugehörige Kästchen farbig markiert.

Das Ergebnis sollte dann aussehen wie in der Abbildung.

Perfektes Quadrat

Ein Quadrat ist ein rechtwinkliges Viereck mit vier gleich langen Seiten. Ein perfektes Quadrat ist ein Quadrat, das sich vollständig in kleinere Quadrate aufteilen lässt, wobei keine zwei dieser Teilquadrate einander gleich sein dürfen - oder, etwas mathematischer formuliert: Ein Quadrat, das sich in lauter paarweise verschieden große Quadrate zerlegen lässt, heißt perfekt.

3_Perfekte_Quadrate

 Die Abbildung zeigt Exemplare des perfekten Quadrats der Ordnung 21. Es enthält 21 paarweise verschiedene Teilquadrate – mit unterschiedlichen Farben ausgemalt. Mehr…