[ProjectEuler] 001: Add all the natural numbers below one thousand that are multiples of 3 or 5


Mein Project Euler Banner Dieser Eintrag ist Bestandteil meiner neuen Blog-Serie, welches sich den Aufgaben des Project Euler widmet.

Dies ist die erste Aufgabe des Project Euler und als solche auch entsprechend einfach. Es geht darum, die Summe aller Vielfachen von 3 oder von 5 einer gegebenen Zahl zu finden.

Beispielsweise wird genannt, dass alle Vielfachen von 3 unter 10 folgende Menge von Zahlen ist: {3,6,9}. Die Menge aller Vielfachen von 5 unter 10 ist: {5}. Die Summe dieser Zahlen ergibt 23.

Formal lässt sich das also in etwa so festhalten:

sum x; forall x in {a in mathbb{Z} | exists k in mathbb{Z} colon a = k cdot 3 _{lor} a = k cdot 5}
(Ich hoffe, dass es so mathematisch korrekt aufgeschrieben ist. Für Verbesserungsvorschläge bin ich jedem sehr dankbar!)

Aufgabe ist es, die Summe aller Vielfachen von 5 oder 3 unter 1000 zu finden.

Ohne sich großartig Gedanken über das Problem zu machen, kommt man hier eigentlich relativ schnell auf eine fixe Idee. So auch ich. Dummerweise stellt sich diese als falsch heraus, und dann musste ich doch ein wenig tiefer graben.

Aber seht doch selbst.

Vorüberlegungen

Meine erste Idee war recht simpel: Die Umkehrung eines Vielfachen ist ja die Teilbarkeit, d.h. das bei der Division (die Umkehrfunktion der Multiplikation, welche ja Bestandteil der Definition eines Vielfachen ist) kein Rest entsteht.

Folglich reicht es, alle Zahlen zwischen 0 und 1.000 darauf zu testen, ob sie sich Restlos durch 3 oder 5 teilen lassen. So gut wie jede Programmiersprache bietet hierzu verschiedene Operationen, meistens mit Modulo und Floor-Operation bezeichnet.

Anmerkung: Während Modulo in den meisten Programmiersprachen für die Rest-Operation üblich ist, gibt es für die Floor-Operatin unterschiedliche Bezeichnungen. Häufig ist DIV oder division gebräuchlich. In Scheme, welches ich für diese Aufgabe verwenden werde, ist die Funktion quotient diejenige, die wir für die ganzzahlige Division ohne Rest gebrauchen können. Ebenfalls Gebräuchlich sind, in Anlehnung an den Slash (/) als das Symbol für die Division, der Backslash () für die ganzzahlige Division, sowie das Prozentzeichen (%) für die Modulo-Berechnung.

Erste Implementierung

Fangen wir also an mit dem Programm. Meine Überlegungen dazu waren, das Programm so variabel wie möglich zu gestalten. Zunächst brauchen wir also eine Funktion, die 3 Zahlen entgegen nimmt, nämlich die zwei Vielfachen, und die Grenze nach oben. Das Ergebnis ist wieder eine Zahl, als Testfall nutze ich das gegebene Beispiel, sowie ein paar Extremfälle.

; Programm zum Berechnen der Summe aller Vielfachen von x und y zwischen
; 0 und n
(: sum-two-multiples-below-n (number number number -> number))

(check-expect (sum-two-multiples-below-n 3 5 0) 0)
(check-expect (sum-two-multiples-below-n 0 5 10) 5)
(check-expect (sum-two-multiples-below-n 3 0 10) 18)
(check-expect (sum-two-multiples-below-n 3 5 10) 23)

(define sum-two-multiples-below-n
  (lambda (x y n)
    (if (< n 1)
        0
        (+ (sum-multiples-to-n x (- n 1))
           (sum-multiples-to-n y (- n 1))))))

Die Funktion nutzt eine Hilfsfunktion, welches die Vielfachen jeder einzelnen Zahl bis zur Obergrenze n ermittelt und die Summe dieser ausgibt. An diese Funktion wird an dieser stelle “n-1” übergeben. Dazu muss ich sagen, dass ich es generell sehr unschön finde, einen Parameter zu übergeben, der erst “bearbeitet” werden muss, bevor die eigentliche Funktion startet – ein Parameter sollte gleich in der richtigen Form übergeben werden. In den Lösungseinreichungen habe ich gesehen, dass viele dieses anscheinend ähnlich sehen, und deshalb statt der 1.000 die 999 übergeben. Dies finde ich allerdings ähnlich verwerflich. Die Aufgabe gibt ganz klar an, dass die 1.000 übergeben werden soll, genau so wie im Beispiel die 10 übergeben wird. Dies ist für mich als Schnittstellendefinition bindend. Daher die (n – 1).
Damit die nachfolgenden Funktionen nicht versuchen, durch 0 zu teilen, muss n größer als 1 sein – dies prüft die Funktion gleich zu Anfang.

Die Hilfsfunktion sum-multiples-to-n wiederum Reduziert n Schrittweise um 1 und prüft dabei, ob der Modulo = 0 ist. Alle n’ < n, für die der Modulo tatsächlich 0 ist, werden zusammengezählt.
Dieses Problem lässt sich rekursiv in einer Prozedur lösen, die relativ elegant, kurz und einfach zu lesen ist; allerdings würde dies einen relativ hohen Speicherverbrauch mit sich ziehen:

; Programm zum Berechnen der Summe aller Vielfachen von x bis n
(: sum-multiples-to-n (number number -> number))

(check-expect (sum-multiples-to-n 0 9) 0)
(check-expect (sum-multiples-to-n 3 9) 18)
(check-expect (sum-multiples-to-n 5 9) 5)

(define sum-multiples-to-n
  (lambda (x n)
    (cond ((or (= n 0) (= x 0)) 0)
          ((= (modulo n x) 0) 
           (+ n (sum-multiples-to-n x (- n 1))))
          (else (sum-multiples-to-n x (- n 1))))))

Hier wird die Addition so lange verzögert, bis alle Moduli berechnet sind. Moduli, die gefunden werden, müssen daher zunächst im Speicher abgelegt werden (Zeile 28). So baut sich, in Abhängigkeit der Größe n, ein Ausdruck auf, der den Speicherverbrauch immer größer werden lässt.

Die alternative ist nicht ganz so kurz und prägnant, und sieht daher auch weniger elegant aus. Allerdings hat diese Variante den Vorteil, dass der Speicher konstant gehalten wird. Die Idee ist es, einen weiteren Parameter durchzureichen, der ein aktuelles Zwischenergebnis enthält. Jeder gefundene Modulo wird direkt auf dieses Zwischenergebnis dazu addiert – dadurch bleibt der Speicherverbrauch konstant.

; Programm zum Berechnen der Summe aller Vielfachen von x bis n
(: sum-multiples-to-n (number number -> number))

(check-expect (sum-multiples-to-n 0 9) 0)
(check-expect (sum-multiples-to-n 3 9) 18)
(check-expect (sum-multiples-to-n 5 9) 5)

(define sum-multiples-to-n
  (lambda (x n)
    (sum-multiples-to-n-iter x n 0)))

(define sum-multiples-to-n-iter
  (lambda (x n result)
    (cond
      ((or (= n 0) (= x 0)) result)
      ((= (modulo n x) 0)
       (sum-multiples-to-n-iter x (- n 1) (+ result n)))
      (else (sum-multiples-to-n-iter x (- n 1) result)))))

Der besseren Lesbarkeit halber habe ich die Hilfsfunktion zunächst getrennt definiert. Natürlich hätte man auf die erste Funktion (Zeile 24 bis 26) auch weglassen können. Allerdings bringt dies einige Nachteile mit sich:

  • Das Zwischenergebnis muss von der aufrufenden Funktion weitergegeben werden. Wenn diese also falsch aufgerufen wird, kann es hier zu Fehlern kommen.
  • Die Schnittstelle, die wir definiert haben und die in sum-two-multiples-below-n genutzt wird, muss geändert werden. Das bedeutet das wir das gesamte Programm nach Aufrufen durchsuchen müssten, und diese ebenfalls ändern.

Einen Schönheitsfehler hat diese Implementierung noch: Die Funktion sum-multiples-to-n-iter wird ausschließlich für sum-multiples-to-n genutzt – sie macht nur Sinn in Verbindung mit dieser Funktion, und sollte daher auch nur für diese Funktion sichtbar sein. Abhilfe schafft hier letrec, welches uns erlaubt in einer Funktionsdefinition weitere (Funktions-)Definitionen vorzunehmen, und gleichzeitig aber auch auf alle Argumente der umschließenden Funktionen zuzugreifen. Somit spart man sich zusätzlich das “Durchschleifen” von Parametern. Die verbesserte Version sieht dann also so aus:

; Programm zum Berechnen der Summe aller Vielfachen von x bis n
(: sum-multiples-to-n (number number -> number))

(check-expect (sum-multiples-to-n 0 9) 0)
(check-expect (sum-multiples-to-n 3 9) 18)
(check-expect (sum-multiples-to-n 5 9) 5)

(define sum-multiples-to-n
  (lambda (x n)
    (if (= n 0)
        0
        (letrec ((iter
                 (lambda (n result)
                   (cond ((or (= n 0) (= x 0)) result)
                         ((= (modulo n x) 0)
                          (iter (- n 1) (+ result n)))
                         (else (iter (- n 1) result))))))
          (iter n 0)))))

Damit wären wir eigentlich fertig. Allerdings hat diese Implementierung ein kleines Problem: Sie liefert ein falsches Ergebnis!

Zweite Implementierung

Es hat mich eine ganze Weile gekostet, bis ich verstanden habe, was hier falsch läuft. Betrachten wir hierzu folgende Vielfachen der Mengen 5 und 3 bis 30:

{x in mathbb{Z} _{land} x leq 30 | exists k in mathbb{Z} colon a = k cdot 3} = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}
{x in mathbb{Z} _{land} x leq 30 | exists k in mathbb{Z} colon a = k cdot 5} = {5, 10, 15,  20, 25, 30}

Was fällt hierbei auf? Die Zahlen 15 und 30 sind in beiden Mengen vertreten. Und das verfälscht unser Ergebnis! Gesucht ist die Summe der Zahlen, die durch 3 oder 5 geteilt wird – d.h. nicht, dass eine Zahl, die durch beide Zahlen geteilt wird, auch doppelt in die Summe eingeht. Wir müssen also alle doppelten Zahlen eliminieren. Diese doppelten Zahlen stellen vielfache da, die sowohl vielfache von 5 als auch vielfache von 3 sind. Welches ist die menge aller doppelten Vielfachen von 3 und 5? Hier erinnert sich der ein oder andere vielleicht noch an das so genannte Kleinste gemeinsame Vielfache kurz kgV. Zwar berechnet das kleinste gemeinsame Vielfache nur ein gemeinsames Vielfaches, allerdings ist dies interessanter Weise für die Zahlen 3 und 5:

kgV(3,5) = 15

Was bedeutet das? Um also auf das richtige Ergebnis zu kommen, müssen wir 15, und alle Vielfachen von 15 von dem Ergebnis abziehen. Mit ein paar Test kann man sich verdeutlichen, dass diese Regel für verschiedene Fälle das richtige Ergebnis liefert.

Die Vielfachen von 12 und 18 bis 100 entsprechen dem Vielfachen des kleinsten gemeinsamen Vielfachen von 12 und 18:
kgV(12, 18) = 36
{12, 24, 36, 48, 60, 72, 84, 96} cap {18, 36, 54, 72, 90} = {36, 72}

Die Vielfachen von 4 und 8 bis 40 entsprechen dem Vielfachen des kleinsten gemeinsamen Vielfachen von 4 und 8:
kgV(4, 8) = 8
{4, 8, 12, 16, 20, 24, 28, 32, 36, 40} cap {8, 16, 24, 32, 40} = {8, 16, 24, 32, 40}

Die Vielfachen von 2 und 7 bis 30 entsprechen dem Vielfachen des kleinsten gemeinsamen Vielfachen von 2 und 7:
kgV(2, 7) = 14
{2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30} cap {7, 14, 21, 28} = {14, 28}

Das heißt also, dass wir unser Programm weiter allgemein halten können, wenn wir diesen Tatbestand Berücksichtigen. Wie ändert sich dadurch unser Programm? Scheme bietet eine Funktion um das kleinste Vielfache zweier Zahlen heraus zu bekommen, namens lcm (least comon multiple). Aufgerufen mit den Argumenten, die der Funktion als Parameter übergeben wurden, ergibt dies folgende Änderung für die Hauptfunktion:

; Programm zum Berechnen der Summe aller Vielfachen von x und y zwischen
; 0 und n
(: sum-two-multiples-below-n (number number number -> number))

(check-expect (sum-two-multiples-below-n 3 5 0) 0)
(check-expect (sum-two-multiples-below-n 0 5 10) 5)
(check-expect (sum-two-multiples-below-n 3 0 10) 18)
(check-expect (sum-two-multiples-below-n 3 5 10) 23)

(define sum-two-multiples-below-n
  (lambda (x y n)
    (if (< n 2) 
        0
        (- (+ (sum-multiples-to-n x (- n 1))
              (sum-multiples-to-n y (- n 1))) 
           (sum-multiples-to-n (lcm x y) (- n 1))))))

Der Rest der Funktionen bleibt unverändert.

Überlegungen zur Effizienz des Programms

Wir haben uns ja schon bei der ersten Implementierung ein paar Gedanken zur Effizienz gemacht. Hier möchten wir diese noch ein wenig weiter treiben. Was passiert, wenn wir die Funktion sum-two-multiples-below-n mit 3, 5 und 1.000 aufrufen?

Es wird 3 mal die Funktion sum-multiples-to-n aufgerufen, einmal mit der Zahl 3, einmal mit der Zahl 5 und einmal mit der Zahl 15. Was bedeutet das? Bei besonders großen n, wie z.B. 1.000 wird diese Zahl drei mal hintereinander herunter gezählt, und jedes mal wird dabei eine andere Zahl auf Teilbarkeit geprüft. Wir haben also bei n = 1.000 3.000 Funktionsaufrufe. Wünschenswert wäre es, das n nur einmal herunter zu zählen, und dabei alle Tests durchzuführen. Erinnern wir uns an die mathematische Definition, so kommt dort ein “oder” vor. Wenn sei durch 3 oder durch 5 teilbar ist, soll sie zum Rest aufsummiert werden. Dadurch wird die gesamte Funktion auf 1/3 der Abarbeitungszeit der vorherigen Implementierung verringert!

; Programm zum Berechnen der Summe aller Vielfachen von x und y zwischen
; 0 und n
(: sum-two-multiples-below-n (number number number -> number))

(check-expect (sum-two-multiples-below-n 3 5 0) 0)
(check-expect (sum-two-multiples-below-n 0 5 10) 5)
(check-expect (sum-two-multiples-below-n 3 0 10) 18)
(check-expect (sum-two-multiples-below-n 3 5 10) 23)

(define sum-two-multiples-below-n
  (lambda (x y n)
    (if (< n 1)
        0
        (letrec ((iter 
                  (lambda (n result)
                    (cond ((= n 0) result)
                          ((= x 0) (sum-multiples-to-n y n))
                          ((= y 0) (sum-multiples-to-n x n))
                          ((or (= (modulo n x) 0)
                               (= (modulo n y) 0))
                           (iter (- n 1) (+ result n)))
                          (else (iter (- n 1) result))))))
          (iter (- n 1) 0)))))

Den Geschwindigkeitsgewinn kann man sich mittels der Funktion time anzeigen lassen. Damit die Funktion verwendet werden kann, muss das entsprechende Modul eingebunden werden. Dies geschieht mit einem (require racket/base). Danach lässt sich mit einem (time (sum-two-multiples-below-n 3 5 1000)) die Prozessorzeit in Millisekunden anzeigen, die die Prozedur braucht um die Summe aller Vielfachen von 3 und 5 bis 1.000 zu berechnen. Zunächst die Werte für die erste Implementierung:

Willkommen bei DrRacket, Version 5.0.2 [3m].
Sprache: Die Macht der Abstraktion - fortgeschritten; memory limit: 128 MB.
Alle 7 Tests bestanden!
> (time (sum-two-multiples-below-n 3 5 1000))
cpu time: 3 real time: 3 gc time: 0
233168
> (time (sum-two-multiples-below-n 3 5 1000000000)) 
cpu time: 1725719 real time: 1751884 gc time: 11098
233333333166666668
> 

Im Vergleich dazu die Ergebnisse der nun verbesserten Implementierung:

Willkommen bei DrRacket, Version 5.0.2 [3m].
Sprache: Die Macht der Abstraktion - fortgeschritten; memory limit: 128 MB.
Alle 7 Tests bestanden!
> (time (sum-two-multiples-below-n 3 5 1000))
cpu time: 1 real time: 2 gc time: 0
233168
> (time (sum-two-multiples-below-n 3 5 1000000000)) 
cpu time: 627714 real time: 633553 gc time: 9058
233333333166666668
> 

Man sieht also, dass es eine Effizienzsteigerung um frac{627714}{1725719} approx 0,3637, also ca. 35% gibt.

Gauß und die Teilbarkeit von n

Es geht allerdings noch weiter. Wenn man die Lösung eingegeben hat, bekommt man Zugriff auf eine PDF Datei, die folgende weiterführende Überlegungen anstellt:

Anstatt alle Zahlen von 1 - n zu testen, genügt es, die Zahlen von 1 - lfloor frac{n}{x}rfloor zu berechnen. Denn von lfloor frac{n}{x}rfloor wissen wir, dass es ein Teiler von n ist.
Es ergibt sich folgende Formel:
3 + 6 + 9 + 12 + ... + 999 = 3 cdot (1 + 2 + 3 + 4 + ... + 333).

Es müssen also nur noch die Zahlen 1 - lfloor frac{n}{x}rfloor aufaddiert werden, und mit dem Teiler x multipliziert werden:

x cdot sumlimits_{k=1}^{ lfloor frac{n}{x}rfloor} k

Damit lässt sich die Berechnung der Vielfachen um einiges beschleunigen. Wie aber sieht es mit der Summe aus? Die Summe von 1-n lässt sich über die Gaußsche Summenformel wie folgt berechnen:

1 + 2 + 3 + 4 + ... + n = sumlimits_{k=1}^{n} k = frac{n cdot (n + 1)}{2}

Daraus ergibt sich, dass die Summe aller Vielfachen von x bis n sich wie folgt berechnen lassen:

x cdot sumlimits_{k=1}^{lfloor frac{n}{x}rfloor} k = x cdot frac{lfloor frac{n}{x}rfloor cdot (lfloor frac{n}{x}rfloor + 1)}{2}

In Scheme lässt sich das wie folgt umsetzten:

(require racket/base)

; Programm zum Berechnen der Summe aller Vielfachen von x und y zwischen
; 0 und n
(: sum-two-multiples-below-n (number number number -> number))

(check-expect (sum-two-multiples-below-n 3 5 0) 0)
(check-expect (sum-two-multiples-below-n 0 5 10) 5)
(check-expect (sum-two-multiples-below-n 3 0 10) 18)
(check-expect (sum-two-multiples-below-n 3 5 10) 23)

(define sum-two-multiples-below-n
  (lambda (x y n)
    (if (< n 1) 
        0
        (- (+ (sum-multiples-to-n x (- n 1))
              (sum-multiples-to-n y (- n 1))) 
           (sum-multiples-to-n (lcm x y) (- n 1))))))

; Programm zum Berechnen der Summe aller Vielfachen von x bis n
(: sum-multiples-to-n (number number -> number))

(check-expect (sum-multiples-to-n 0 9) 0)
(check-expect (sum-multiples-to-n 3 9) 18)
(check-expect (sum-multiples-to-n 5 9) 5)

(define sum-multiples-to-n
  (lambda (x n)
    (if (= x 0)
        0
        (letrec ((p (quotient n x)))
          (quotient (* x p (+ p 1)) 2)))))

; Berechnet die Summe der Vielfachen von 3 und 5 mit Zeitverbrauch bis
; 1000
(time (sum-two-multiples-below-n 3 5 1000))
(time (sum-two-multiples-below-n 3 5 1000000000))

Besonders bemerkenswert ist hierbei die Zeitersparnis. War sie bei der oberen Verbesserung mit 36% schon sehr groß, so gibt es hier eine 100%ige Verbesserung.

Willkommen bei DrRacket, Version 5.0.2 [3m].
Sprache: Die Macht der Abstraktion - fortgeschritten; memory limit: 128 MB.
Alle 7 Tests bestanden!
> (time (sum-two-multiples-below-n 3 5 1000))
cpu time: 1 real time: 1 gc time: 0
233168
> (time (sum-two-multiples-below-n 3 5 1000000000)) 
cpu time: 0 real time: 0 gc time: 0
233333333166666668
> 

Fazit

Wenn man sich die Aufgabe zum ersten Problem das erste mal anguckt, scheint sie sehr einfach zu sein. Ich denke aber, dass mein (ziemlich lang gewordener) Blog-Eintrag ganz Eindrucksvoll darlegt, dass dies nicht der Fall ist. Selbst ich habe bei der Musterlösung noch einiges dazu gelernt. Den Gaußschen Algorithmus zur Berechnung von Summen kannte ich zwar schon, allerdings wäre ich nie auf die Idee gekommen, ihn auf diese Weise einzusetzen. Auch mein Wissen um die Zusammenhänge zwischen kleinsten gemeinsamen Vielfachen und größten gemeinsamen Teiler konnte ich auffrischen. Insgesamt hat mir diese Aufgabe viel Spaß gemacht, und ich habe einiges gelernt 🙂

Den Quellcode habe ich übrigens auf meinem bitbucket-Account hochgeladen. Er kann über das Webinterface als komprimierte Datei, oder aber über:

$ hg clone https://bitbucket.org/pygospa/projecteuler001

bezogen werden.

Ich freue mich auf eure Kommentare!

Advertisements

Please comment. I really enjoy your thoughts!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s