Qbi's Weblog

Von Primzahlen geht für viele eine große Faszination aus das Thema wird aus verschiedenen Richtungen gern beleuchtet. Sehr alt ist dabei die Fragestellung, wie viele Primzahlen es denn gibt. Euklid fand neben anderen die Antwort auf diese Frage: Es gibt unendlich viele Primzahlen. Sein Beweis ist recht einleuchtend.

Stellen wir uns vor, es gäbe nur endlich fünf Primzahlen (In der Regel sagt man: endlich viele) p1, p2, p3, p4 und p5. Dann berechnet man eine neue Zahl z = p1*p2*p3*p4*p5+1, d.h. alle Primzahlen werden multipliziert und anschließend wird die Zahl 1 addiert. Keine der bisherigen Primzahlen teilt diese Zahl z. Da aber jede natürliche Zahl einen Primteiler besitzt, muss der außerhalb der bisher bekannten Primzahlen liegen, d.h. es gibt mindestens eine neue Primzahl p6. Die Aussage lässt sich dann wieder anwenden und so ergibt sich, dass die Zahl der Primzahlen nicht endlich sein kann.

Bei Mathoverflow wurden diverse Fehleinschätzungen diskutiert. Unter anderem zählte dazu, dass die oben konstruierte Zahl z eine Primzahl sei. Wenn man den Beweis oberflächlich liest (siehe auch die Skripte zu Algebra 1 oder Zahlentheorie), könnte man in der Tat zu dem Schluss kommen. Die Zahlen 2, 3, 5, 7, 11 und 13 liefern jedoch ein Gegenbeispiel.

Schlimm finde ich dann die in dem Posting angegebenen Beispiele von Leerern (sic!), die ihre Schülern unter Beschimpfungen vor die Tür stellen, weil sie auf den obigen Umstand hinweisen und den auch noch beweisen.

Falls ihr euch schon immer mal gefragt habt, wie man ein reguläres 17-Eck mit Zirkel und Lineal konstruiert. Hier ist die Lösung:

Bei Holgi fand ich folgendes wunderbare Video. Es erzählt die Geschichte des Mathematikers Cantors, des Physikers Boltzmann sowie weiterer Größen. Ich finde das bisher (bin noch nicht am Ende) sehr sehenswert.

Stell dir vor, du schreibst einen mathematischen Text und musst einen Ausdruck der Form df/dt (als richtigen Bruch) schreiben. Der einfachste Weg, dies zu realisieren, wäre mittels \frac{df}{dt}. Das d muss jedoch aufrecht stehen. Also müsste man ein Konstrukt mit \mathrm{} oder ähnlichem basteln. Ähnlich sieht die Situation bei partiellen Ableitungen aus.

Ich stolperte vor kurzem über das Paket esdiff. Dies macht es sehr einfach, die obigen Konstrukte zu setzen. Für den obigen Ausdruck existiert der Befehl \diff{}{} und man würde schreiben: \diff{f}{t}. Für partielle Ableitungen lässt sich \diffp{}{} nutzen.

Insgesamt vereinfacht das Paket den Satz von Ableitungen und wird ab sofort zu meinem Standardrepertoire gehören.

In einem Rätsel fragte ich vor kurzem nach der Lösung zu folgendem Problem:

Wenn man das Ganze nun 29mal macht, also 2²⁹, erhält man eine neunstellige Zahl. Diese neun Zahlen sind voneinander verschieden. Da wir im normalen Leben mit 10 Zahlen (0, ..., 9) rechnen, muss hier also eine fehlen. Die Frage ist, welche Zahl ist das?

Nach den Kommentaren zu urteilen, haben viele ihre Lieblingsprogrammiersprache angeworfen, gerechnet und hatten das Ergebnis. Der Witz an dem Rätsel ist aber, die Lösung ohne solche Hilfsmittel und ohne explizites Errechnen zu ermitteln. Wie sieht nun ein möglicher Weg aus?

Überlegt euch zunächst mal ein paar Eigenschaften einer Zahl, die alle Ziffern von 0 bis 9 (im folgenden mal Oberzahl genannt) genau einmal enthält. Ist diese durch 2, 3, 4 usw. teilbar?

Was relativ schnell klar sein sollte, ist, dass die Zahl sowohl durch 3 als auch durch 9 teilbar ist. Die Teilbarkeitseigenschaft wird in beiden Fällen über die Quersumme ermittelt. Das Ergebnis von 0+1+2+3+4+5+6+7+8+9 wusste bereits der kleine Herr Gauß (und brachte damit seinen Lehrer zur Verzweiflung) und ist 45 (9*(9+1)/2). Da diese Zahl durch 3 und 9 teilbar ist, muss auch die ursprüngliche durch 3 und 9 teilbar sein. Wenden wir uns insbesondere der Teilbarkeit durch 9 zu.

Stellt euch vor, wir ziehen von der Oberzahl (also der, die alle Zahlen von 0 bis 9 einmal enthält) 1 ab und schauen, ob das Ergebnis durch 9 teilbar ist. Dies ist natürlich nicht mehr der Fall. Dividieren durch 9 ergibt irgendetwas mit Rest 8 (oder auch mit Rest -1). Auch die Quersumme ist nun 44, also eine Zahl, die den Rest 8 (oder auch -1) ergibt, wenn man sie durch 9 teilt. Andererseits könnte man von der Oberzahl einfach eine Zahl weglassen und schauen, was Division durch 9 ergibt. Wenn ihr also die 1 aus der Zahl entfernt, ist die Quersumme wieder 44, also eine Zahl mit Rest 8 (modulo 9). Das heißt, mit diesem Wissen müssen wir uns nun anschauen, welchen Rest die Zahl 2²⁹ bei der Division mit 9 hat.

Im einfachsten Fall kann man sich dazu die ersten Glieder der Folge ausrechnen und schauen, ob es Regelmäßigkeiten gibt:
2⁰=1≡=1 (mod 9)
2¹=2≡2 (mod 9)
2²=4≡4 (mod 9)
2³=8≡8 (mod 9)
2⁴=16≡7 (mod 9)
2⁵=32≡5 (mod 9)
2⁶=64≡1 (mod 9)
2⁷=128≡2 (mod 9)
2⁸=256≡4 (mod 9)
Wer die Notation nicht kennt: n (mod 9) bedeutet, geteilt durch 9 mit Rest n.

Es ist hier also ein Zyklus 1, 2, 4, 8, 7, 5 zu erkennen. Wenn man den Zyklus bis 29 betrachtet, erhält man das Ergebnis 2²⁹=5 (mod 9).

Der eher mathematische Weg wäre, den Satz von Euler geeignet auszunutzen. Da muss man die obigen Schritte nicht mühselig per Hand rechnen, sondern bekommt das Ergebnis gleich präsentiert.

Im obigen Beispiel war das Ergbnis Rest 8, da von der Oberzahl 1 abgezogen wurde. Hier erhalten wir als Ergebnis 5. Also fehlt in 2²⁹ die Zahl 4.

Bild von eqqman

Zu Anfang der Woche habe ich ein kleines Rätsel für alle Freunde der Mathematik. Ich fand das bei God Plays Dice und habe es unten mal ins Deutsche gebracht.

Die Potenzrechnung dürfte euch allen noch aus der Schule bekannt sein. Freunde der Bits und Bytes rechnen gern zur Basis 2. Das heißt zum Beispiel 2¹=2, 2²=2·2=4, 2³=2·2·2=8 usw. Wenn man das Ganze nun 29mal macht, also 2²⁹, erhält man eine neunstellige Zahl. Alle dDiese neun Zahlen sind voneinander verschieden. Da wir im normalen Leben mit 10 Zahlen (0, ..., 9) rechnen, muss hier also eine fehlen. Die Frage ist, welche Zahl ist das? Wer hat eine Idee?

Update: Satzbau oben nach dem Kommentar von Sven geändert.

Im Rahmen eines Seminars an der Uni hielt ich kürzlich einen Vortrag über AES und eine Einführung in Public-Key-Kryptografie. Die Unterlagen sind als PDF-Dokument verfügbar. Zum Grundverständnis finde ich auch diese Animation interessant. Sie enthält aus mathematischer Sicht nur ein paar Unzulänglichkeiten.

Der Vortrag verlief aus meiner Sicht sowie der der Teilnehmer gut. Nur der betreuende Professor meinte, er finde es schade, dass so wenig Mathematik dabei ist.

Mittlerweile gibt es einen neuen Angriff auf den Algorithmus. Bruce Schneier verweist im Beitrag New attack on AES auf die Veröfentlichung. Die Autoren haben auch eine FAQ zu den wichtigsten Fragen des Angriffs. Ich muss das demnächst mal lesen und verstehen.

Viele scheint die Frage zu bewegen, wie man Brüche und insbesondere große Brüche in LaTeX schreiben kann. Üblich ist die Verwendung von \frac{}{}. Das führt zu der gewohnten Darstellung eines Bruches. Manchmal ist es besser, den Bruch mit einem Schrägstrich zu setzen (so wie 1/2). Hierzu muss mittels \usepackage{nicefrac} das Paket nicefrac eingebunden werden. Danach steht der Befehl \nicefrac{}{} zur Verfügung. Wie bei \frac{}{} kommt in die erste geschweifte Klammer der Term oberhalb des Bruchstriches und in die zweite der Term unterhalb des Bruchstriches.

Für eine Seminararbeit zu AES werte ich unter anderem auch Angriffe gegen den Algorithmus aus. Die Forscher Ferguson, Schroeppel und Whiting stellten 2001 in A simple algebraic representation of Rijndael (PDF) AES als Kettenbruch dar:

Wie macht man das mit LaTeX? Eigentlich ganz einfach! Man könnte den Ausdruck mittels \frac{}{} verschachteln. Das sieht aber recht unschön aus, da der Abstand im Nenner gleich bleibt und so die Ausrdrücke unlesbar werden. Das AMS-Paket bietet den Befehl \cfrac{}{} (steht für continued fractions). Damit kann man das obenstehende erreichen. In der erweiterten Ansicht des Artikels habe ich den kompletten Quelltext für obiges Beispiel.

Zum meinem Geburtstag bekam ich recht viele Bücher geschenkt. Eines davon war Der Mathematikverführer von Christoph Drösser. Das Buch hatte ich bereits vor einigen Wochen in einer Buchhandlung gesehen. Nach kurzem Durchblättern entschied ich mich damals gegen den Kauf.

Um was geht es? Der Autor erklärt mathematische Problemstellungen anhand praktischer Beispiele. Zunächst geht es um das Rechnen allgemein. Es wird erklärt, ob es sich für den Chef der Deutschen Bank lohnt, einen Fünf-Euro-Schein, der vor seiner Tür liegt, aufzuheben (Wenn er länger als fünf Sekunden für den Gang braucht, hat er in derselben Zeit mehr verdient), wieviele Hartz-IV-Empfänger von den Kosten eines Eurofighters bezahlt werden können etc. Das erste Kapitel bot für mich ein Aha-Erlebnis. Folgendes “Spiel” wird beschrieben:

Stellen Sie sich ­ [...] ­ folgendes Spiel vor: Jemand hat am Rand der Autobahn von Hamburg nach Berlin eine zwei Zentimeter breite und zwei Meter hohe Latte in den Boden geschlagen. Irgendwo zwischen Hamburg und Berlin, Sie haben keine Ahnung, wo. Sie fahren die Strecke nachts mit dem Auto und haben eine Pistole dabei. Zu einem beliebigen Zeitpunkt, den Sie frei wählen können, kurbeln Sie die Fensterscheibe herunter und schießen in Richtung Straßenrand. Einmal. Wenn Sie die Latte treffen, haben Sie gewonnen.

Das Spiel beschreibt natürlich die Lottovariante 6 aus 49. Ich denke, hiermit lässt sich vielen die Chance beim Lotto greifbar machen. Für einen Sechser mit Zusatzzahl muss es dann eine zwei Millimeter dicke Latte sein.

Das folgende Kapitel beschreibt bedingte Wahrscheinlichkeiten am Beispiel von DNA-Tests und es folgt ein Kapitel zum Dreisatz. Die Anordnung dieser wie auch anderer Kapitel könnte besser sein. Denn der Dreisatz ist vergleichsweise leichter Stoff. Immerhin wird der schon in der Schule behandelt. Wahrscheinlichkeiten kommen nach meiner Beobachtung als Schulstoff eher zu kurz und könnten daher von der Mehrzahl der Leser als schwieriges Thema beurteilt werden. Ich finde es besser, wenn sich der Schwierigkeitsgrad langsam steigert.

Die weiteren Kapitel bringen eine Einführung in das Gerrymandering, zum simpsonschen Paradoxon, zum Problem des Handlungsreisenden und einigem mehr. Die meisten der diskutierten Problemstellungen waren mir bekannt. Daher habe ich meist nur die Geschichte zur Einführung gelesen und die Erklärungen übersprungen. Die Geschichten fand ich recht unterhaltsam. Sie haben gut in das jeweilige Thema eingeführt und auch Interesse geweckt, was denn nun kommt. Die Stellen mit den Erklärungen, die ich las, hatten wieder den üblichen Mangel. Der Autor versuchte sämtliche ernsthafte Mathematik wegzulassen. Gerade bei den Extremwertaufgaben wurde irgendwo im Kleingedruckten der Lösungsweg präsentiert. Der eigentliche Text ließ diesen aus.

Insgesamt ist das Buch eine gute Zusammenstellung verschiedener mathematischer Phänomene. Die Geschichten zur Motivation sind gut geschrieben und ich kann mir gut vorstellen, dass das Buch bei einem Mathematikinteressierten mehr Interesse weckt. Diejenigen, die sich auch sonst mit Matheproblemen beschäftigen, wird das Buch wohl nicht vom Hocker hauen. Denn größtenteils steht Bekanntes drin.

In der Vorlesung Gruppentheorie wurde kürzlich das direkte Produkt von Gruppen definiert. Neben dem üblichen Produktzeichen ∏ verwendete der Vorlesende auch ein großes ×. Intuitiv verwendete ich bei meiner LaTeX-Mitschrift \bigtimes. Das resultierte im einem Fehler, da es dieses Zeichen in den eingebundenen Paketen nicht gab. Ein Blick in die The Comprehensive LaTeX Symbol List (PDF) sagte mir, dass es im Paket txfonts die Anweisung \varprod gibt und die Pakete MnSymbol sowie mathabx mein intuitiv gewähltes Zeichen vorrätig haben.

Da alle Varianten für mich mehr Nach- als Vorteile bringen, habe ein wenig gegoogelt und bin auf den Beitrag von Roland Illig gestossen. Seine Lösung baute ich mir zu \newcommand*{\bigtimes}{\mathop{\raisebox{-.5ex}{\hbox{\huge{$\times$}}}}} um. Das passt erstmal recht gut in meinen Text:

Falls jemand andere/bessere Lösungen weiß, dann immer her damit.

Meine Leser kennen sicher meine Vorliebe für das Project Euler. Bereits seit längerem beschäftigt mich das zwölfte Problem. Dort soll der Wert der ersten Dreieckszahl berechnet werden, die mehr als 500 Teiler hat. Im Rückblick betrachtet, ist diese Aufgabe relativ klar. Ich habe jedoch sehr viel Zeit daran verschwendet, das Problem zu verkomplizieren, theoretische Ober- und Untergrenzen zu berechnen. Nachdem ich nicht weiterkam, habe ich das Problem liegen lassen. Gerade eben kam es mir wieder in den Sinn. Als setzt ich mich hin und programmierte die Aufgabe einfach naiv und ohne Nachzudenken. Viola, das Ergebnis war richtig.

Bislang konnte ich die Eulerschen Probleme mit einem naiven Programmieransatz lösen. Das heißt, die erste Idee, die mir in den Kopf kam, schrieb ich runter und bekam eine Lösung. Das zehnte Problem warf mir einen Stock zwischen die Beine. Erstmals musste ich mir Gedanken über die Optimierung des Codes machen.

Das zehnte Problem klingt erstmal ganz harmlos: Finden Sie die Summen aller Primzahlen, die kleiner als 2 000 000 sind.. Ha, das ist ja eine einfache Fingerübung:

sieb = [ i for i in xrange(2,2000000) ]
for i in xrange(2,2000000):
  for j in xrange(2,2000000):
    if i*j in sieb:
      sieb.remove(i*j)

Die Werte in sieb müssen dann nur noch addiert werden und fertig. Jedoch kam ich gar nicht soweit. Denn das Programm lief und lief und lief.

Das brachte mich zum Nachdenken, woran das liegen könnte. Letztlich ist die Ursache offensichtlich. Denn der Code berechnet jedes Produkt. Dafür werden schon 2 000 000 * 2 000 000 = 4 000 000 000 000 Berechnungen durchgeführt. Wenn man von der (viel zu optimistischen) Variante ausgeht, dass jede Berechnung ein CPU-Zyklus ist, würde das Programm auf aktuellen Architekturen länger als eine halbe Stunde laufen. In der Realität lief es 15 Stunden. Wie lässt sich die Laufzeit nun verbessern?

Es ist recht offensichtlich, dass das Programm zuviel berechnet. Im ersten Schleifendurchlauf gibt es die Multiplikationen: 2*2, 2*3, 2*4, ..., 2*1999999 = 3999998. Beim zweiten Schleifendurchlauf: 3*2, 3*3, 3*4, ..., 3*1999999 = 5999997. Am klarsten fällt es im letzten Durchlauf auf: 1999999*2, 1999999*3, ..., 1999999*1999999 = 3999996000001. Die Berechnung 3*2 wurde schon im ersten Schritt (nur umgekehrt mit 2*3) durchgeführt. Hier wirkt das Kommutativgesetz. Also kann die Schleife im zweiten Durchlauf erst bei drei beginnen. Im dritten Durchlauf würde nach obigem Algorithmus 4*2, 4*3, 4*4 usw. berechnet werden. Verallgemeinert lässt sich also sagen, dass die Variable der zweiten Schleife genausogroß oder größer als die erste Variable sein muss. Dieser Schritt halbiert die Zahl der Berechnungen.

In der obigen Darstellung wird klar ersichtlich, dass das Programm nicht in jedem Fall bis zum Maximum von 2 000 000 laufen muss. Schon im ersten Durchlauf werden Werte über 2 000 000 berechnet. Das heißt, das Produkt i*j muss kleiner oder gleich 2 000 000 sein. Umformen nach j ergibt: j≤2 000 000/i. Eine weitere oft genutzte Optimierung ist es, die erste Schleifenvariable nur bis √2000000 laufen zu lassen.

Weiterhin fiel mir auch ein, dass man schon die initiale Liste nicht mit Zahlen von 2 bis 2 000 000 füllen muss. Denn es ist bekannt, dass alle Vielfachen von 2 sofort ausfallen. Man kann sogar soweit gehen, dass man nur Zahlen nach dem Muster 6*n-1 und 6*n+1 aufnimmt. Denn die Zahlen 6*n+0, 6*n+2 und 6*n+4 sind gerade und damit keine Primzahlen. Die Zahl 6*n+3 entspricht 3(2*n+1) und ist somit durch drei teilbar. Es verbleibt das obige Muster.

Theoretisch hätetn die obigen Anpassungen schon reichen sollen, um die Laufzeit unter eine Minute zu drücken. Jedoch lief das Programm immer nach weitaus länger. Nach einigem Stöbern fiel mir dann auf, dass in Python die Listenoperationen in und remove die Listen von Beginn an durchsuchen. Das bringt natürlich nochmal eine extreme Pessimierung der Laufzeit. Stattdessen sollte man hier Sets oder Dictionaries nutzen. Ich habe es mit Sets probiert und prompt lief das Programm schnell genug.

sieb = {}
for i in xrange(2, 2000000):
  sieb[i] = True
for x in xrange(2,int(math.sqrt(2000000))+1):
  if sieb[x] == True:
    for y in xrange(2000000/x, x-1,-1):
      t = x * y
      sieb[t] = False

Grundsätzlich lassen sich weitere Möglichkeiten der Optimierung ausdenken. Jedoch reichte mir das obige Ergebnis, um das Ziel zu erreichen. Wahrscheinlich benötige ich in späteren Aufgabe noch eine weitere Verbesserung.

Jetzt ist an den Unis Prüfungszeit ausgebrochen, so auch in Jena. Ich lerne gerade für die Vorlesung zu Funktionalanalysis oder, wie es hier heißt, Höhere Analysis. Zum Lernen habe ich mir ein paar Flashcards gebastelt. Wer das vielleicht ebenfalls zum Vorbereiten nutzen will, findet die Lernliste online.

Also dann: sei ε positiv und beliebig ...

Der Mittelwertsatz ist eines der ersten wichtigen Sätze, die im Studium der Mathematik gelehrt werden. Die Chinesen haben die Wichtigkeit erkannt und würdigen ihn auf ihre Weise:

Die Karte stammt aus der Nähe des Golfs von Triest, genauer aus Ajdovščina. Wier leicht zu sehen ist, kann man die Stadt auf der Karte nicht sehen. Vielmehr sind da zwei Kinder, die wahrscheinlich gerade ein paar Vögel füttern.

Die Autorin der Karte ist eine begeisterte Ski- und Snowboardfahrerin. Auf der Karte ist etwas von ihrentrn diesbezüglichen Aktivitäten zu lesen. Weiterhin erzählt sie mir getreu dem Motto In Mathe war ich immer schlecht, dass sie in Mathe immer schlecht ist bzw. das nicht mag. Aber das kenn ich ja schon zur genüge.

Update: Zwei Tippfehler korrigiert und noch eine Erklärung zur obigen Bemerkung:
Lest am besten mal die Einleitung zu dem oben verlinkten Buch oder, wenn euch mal jemand nach eurem Beruf fragt, dann erzählt, dass ihr was mit Mathematik macht. In weit 90% aller Fälle wird man dann mit einem Blick gemustert und es folgen die Worte: In Mathe war ich immer schlecht. oder etwas äquivalentes. Beutelspacher schreibt in der Einleitung:

... Wenn ein Landrat oder ein Minister eine Mathematiktagung eröffnet, kokettiert er richtig damit, daß er schon in der Schule in Mathematik schlecht war und von unserer Wissenschaft rein gar nichts versteht. Ein Skandal! So ein Mann würde sich doch nie trauen, bei der Eröffnung eines Anglistenkongresses zuzugeben, daß er kein Englisch kann. ...

In dem Sinne war auch die obige Bemerkung zu verstehen.