Skip to content

Das zwölfte Eulersche Problem

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.

Code optimieren

Erathostenes lehrt in Alexandria

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.

Zahlenkolonnen

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.

Project Euler mit Shellmitteln lösen

Als ich kürzlich mit Sven über das Projekt Euler sprach, hatte er recht schnell einen Lösungsvorschlag parat. Auf die Frage, wie er das gemacht habe, antwortetet er: vim.. :-)

Nun war das elfte Problem an der Reihe und ich erinnerte mich wieder an Svens Worte. In dem Problem ist eine 20x20 Matrix gegeben und man soll das größte Produkt von vier nebeneinanderliegenden Zahlen finden:


08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

Nach einigen Überlegungen kam ich zu dem Schluss, dass die Zahlen in der Lösung größer als 74 sein müssen. Dann kam sed zum Einsatz: sed ‘s,\([0-6][0-9]\|7[0-4]\) , ,g’ problem11. Übrig blieb die untenstehende Matrix:


         97                75          78          77 91    
      99       81          87       98                      
81             79       93             88                   
      95                                                 91 
                     89    92                            80 
            99             75       78    84                
   98 81                                                    
                        95    94             91       94    
                  99    97    78 78 96 83    88    89       
            75    76                         97          95 
78             75          94    80                      92 
            96                88                      85    
86                89                                        
   80 81       94             92    86       77    89       
         83 97    99       97                79       98    
88       87                                        93       
                           94                         76    
                     88       99    82       85             
            78    90                   86 81                
            83             92                   89          


Hier fielen mir sofor die markierten Viererblöcke ins Auge, wobei das Produkt der rot markierten Zahlen größer sein muss als das der blau markierten. Als gab ich die Lösung ein und hatte schnell die richtige Lösung. :-)

Ein A mit einem Kringel

Die Vorlesungszeit hat wieder begonnen und wie gewohnt LaTeXe ich die Vorlesungen, d.h. ich schreibe die am Computer unter Verwendung von LaTeX. In der Vorlesung Topologie wurde unter anderem die Menge der inneren Punkte definiert und als Zeichen ein A mit einem Kringel (kleines o) darüber festgelegt. Das ist nicht unbedingt ein Zeichen, welches immer verwende, also musste ich suchen.

Der erste Weg führt dabei immer zur The Comprehensive LaTeX Symbol List. Dort findet man so ziemlich jedes Symbol, was sich durch LaTeX darstellen lässt. In der Tat stand dort, dass man doch \AA verwenden solle. Ergebnis (vergrößert): \AA Der Kringel rutscht halb vom A runter. Insgesamt sieht das merkwürdig aus. Das weitere Dokument hat keine weiteren Hinweise. Also versuche ich es mit \stackrel{o}{A} bzw. \overset{o}{A}. Gerade die letztere Variante soll angeblich gut mit AMSMath harmonieren. Ergebnis (vergrößert): \stackrel. Auch hier steht der Kringel deutlich zu weit links. Außerdem ist die gesamte Kombination zu groß. Insbesondere bei Überschriften ragt der Kringel schon in den Überschriftentext hinein. Nach ein wenig weiterer Suche stiess ich dann auf das Paket accents. Mit der Anweisung \accentset{o}{A} soll es angeblich perfekt werden. Ergebnis (vergrößert): \accentset. Das sieht, wie ich finde, perfekt aus.

Wer als Matheschrift Euler verwendet, dem fehlt der Effekt des nach links Abgleitens. Dort steht der Kringel immer über dem A. Mit der letztgenannten Methode wird aber noch die Größe der Gesamtkonstruktion angepasst. Ergebnis (vergrößert, mit Euler): A unter Verwendung von Euler.

Update: Eine weitere Möglichkeit ist \ring bzw. \mathring. Das hatte ich in der Dokumentation bisher überlesen.

cronjob