025 – Fibonaccizahl mit 1000 Stellen

 

Die Fibonacci Folge ist wie folgt rekursiv definiert:

Fn = Fn−1 + Fn−2, mit F1 = 1 und F2 = 1.

Die ersten 12 Folgeglieder sind also:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144

Das 12te Folgeglied, F12, ist das erste mit drei Ziffern.

Welches Folgeglied ist das erste mit 1000 Stellen?

Lösung

Wir benutzen symbolische Variablen, um die auftretenden riesigen Zahlen verarbeiten zu können.

Matlab-Code:

clear
tic

a = sym('1');
b = sym('1');
c = sym('0');
grenze = sym('1e999');
i = 2;

while floor(c / grenze) == 0
    c = a + b;
    a = b;
    b = c;
	i = i + 1;
end

disp(['erste mit 1000 Ziffern: ' int2str(i)])
toc

Ergebnis: 4782
Rechenzeig: 19.329795 Sekunden

Hier sieht man, dass große Zahlen eine Schwäche von Matlab sind. In anderen Programmiersprachen dauert die Berechnung des gewünschten Folgegliedes weniger als eine Sekunde.

Die erste Fibonaccizahl mit 1000 Stellen ist übrigens:

107006626638275893676498058445739688508368389663215166501323520337
531452060469404062188914758248979265780469488817759195748433646667
256995951299603046126274809248218614406943305123477444275027378175
308757939166619214925918675955396642283714894311307469950343954700
198543260972306729019287052644724372611771582182554849112052501320
147861296593138179223555965745203950613755146783754322911960212993
404826070617539770684706820289548690266618543512452190036948064135
744747091170761976694569107009802439343961747410373691250323136553
216477369702316775505159517351846057995491941096777837322966579658
164651390348815425631018422419025984608800011018625555024549393711
365165703944762958471454852342595042858242530608354443542821261100
899286379504800689433030977321783486454311320576565986845628861680
871869383529735064398629764066000072356291790520705116407761481249
188583094594056668833910935094445657635766615161931775379289166158
132715961687748798382182049252034847387438473677193451278702921863
6250627816