002 – Summe der geraden Glieder der Fibonacci-Folge

Jede neue Zahl in der Fibonaccifolge wird durch die Summe der beiden Vorgänger gebildet. Die ersten beiden Reihenglieder sind definiert als 0 und 1. Die ersten Folgeglieder sind also:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Finde die Summe aller geraden (Vielfache von 2) Folgeglieder, deren Betrag nicht größer ist als 4 Millionen!

Lösung

Möglichkeit 1

Die einfachste Möglichkeit ist es, zunächst die gesamte Folge bis 4000000 aufzustellen und zu speichern. Anschließend wird jedes Folgeglied getestet, ob es gerade ist. Die geraden Folgeglieder werden aufaddiert:

fib = [0 1];
act = 1;
it = 3;
grenze = 4000000;
summe = 0;

while act <= grenze
    fib = [fib act];
    it = it + 1;
    act = fib(it-2) + fib(it-1);
end

for i=1:length(fib)
    if mod(fib(i),2) == 0
        summe = summe + fib(i);
    end
end

summe

Das Ergebnis ist 4613732.
Rechenzeit: 0.002278 Sekunden.

Möglichkeit 2

Den Test, ob die Folgeglieder gerade sind, können wir uns bei genauerem Hinschauen sparen. Die ersten Folgeglieder:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Es lässt sich zeigen, dass jedes dritte Glied der Fibonacci-Folge gerade ist:

Die Summe von zwei (un)geraden Zahlen ist gerade, die Summe einer geraden und einer ungeraden Zahl ist ungerade. Daher ist die Fibonacci-Folge:

ungerade, ungerade, gerade, ungerade, ungerade, gerade, ungerade, …

Alle drei Zahlen wiederholt sich die Abfolge. Präzise lässt sich dies mit der Modulo-Rechnung zeigen. Wir ersetzen also die zweite Schleife:

fib = [0 1];
act = 1;
it = 3;
grenze = 4000000;
summe = 0;

while act &amp;amp;amp;amp;amp;lt;= grenze
    fib = [fib act];
    it = it + 1;
    act = fib(it-2) + fib(it-1);
end

for i=1:3:length(fib)
    summe = summe + fib(i);
end

summe

Rechenzeit: 0.002010 Sekunden, also kein großer Vorteil.

Möglichkeit 3

Wir wollen nun versuchen, um das Aufstellen der gesamten Fibonacci-Folge herumzukommen. Wir schreiben dazu die geraden Folgeglieder auf:

2, 8, 34, 144, 610, 2584, …

Mit ein bisschen Nachdenken findet man für diese Teilfolge eine rekursive Definition:

{e_n} = 4{e_{n-1}}+{e_{n-2}}

Dies müssen wir allerdings noch beweisen. Wir beweisen dazu für die “echte” Fibonacci-Folge:

{E_n} = 4{E_{n-3}}+{E_{n-6}}

Vor dem Weiterlesen unbedingt selber versuchen 🙂

Wir gehen von der Definition der Fibonacci-Folge aus:

{E_n} = {E_{n-1}}+{E_{n-2}}

= \left( {{E_{n-2}}+{E_{n-3}}} \right)+\left( {{E_{n-3}}+{E_{n-4}}} \right)

= \left( {\left( {{E_{n-3}}+{E_{n-4}}} \right)+{E_{n-3}}} \right)+\left( {{E_{n-3}}+\left( {{E_{n-5}}+{E_{n-6}}} \right)} \right)

= {E_{n-3}}+{E_{n-3}}+{E_{n-3}}+\left( {{E_{n-4}}+{E_{n-5}}} \right)+{E_{n-6}}

= {E_{n-3}}+{E_{n-3}}+{E_{n-3}}+{E_{n-3}}+{E_{n-6}}

= 4{E_{n-3}}+{E_{n-6}}

q.e.d.

Wir können also auf das Aufstellen der gesamten Fibonacci-Folge verzichten und brauchen nur die Glieder der Teilfolge:

fib_teil = 2;
act = 8;
it = 2;
grenze = 4000000;

while act &amp;amp;amp;amp;amp;lt;= grenze
    fib_teil = [fib_teil act];
    it = it + 1;
    act = 4 * fib_teil(it-1) + fib_teil(it-2);
end

summe = sum(fib_teil)

Rechenzeit: 0.001152 Sekunden, also noch einmal fast 50% Verbesserung.

This Post Has 2 Comments

  1. Bei Möglichkeit 2 ist ein Zahlendreher. Die dritte gerade Zahl müsste 34 heißen. Hier steht 43.
    Das erscheint auch bei der Suche in der Anzeige und führt zu reichlich Verwirrung.

  2. Wurde korrigiert! Danke!

Leave a Reply

Close Menu