Blog

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, 43, 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 <= 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 <= 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.

Leave a Reply

Close Menu