# Last 10 digits of the billionth fibonacci number?

I want to compute the last ten digits of the billionth fibonacci number, but my notebook doesn't even have the power to calculate such big numbers, so I though of a very simple trick: The carry of addition is always going from a less significant digit to a more significant digit, so I could add up the fibonacci numbers within a boundary of 8 bytes ($0$ to $18\cdot10^{18}$) and neglect the more significant digits, because they won't change the less significant digits anymore.

So, instead of using $$F_{n+1}=F_n+F_{n-1}$$ to compute the whole number, I would use $$F_{n+1}=(F_n+F_{n-1})\operatorname{mod}18\cdot10^{18}$$ to be able to keep track of the last 10 digits.

Here my question: Can I do this?

• You can certainly look at your recursion mod(N) for whatever N you choose...but I'd rethink the choice! Most choices of modulus fail to preserve last digit (12 = 0 mod(3), for example). But there is a good choice of N available to you.
– lulu
Jul 7 '15 at 21:29
• If you just want the last $10$ digits, you should reduce mod $10^{10}$. Jul 7 '15 at 21:32
• @DavidC.Ullrich I didn't implement it recursively, but with a loop and three variables. Jul 7 '15 at 21:33
• @DavidC.Ullrich Noone forces you to use recursion here ^^ The iterative approach should work quite well for such few iterations depending on the computing power. The iterative algorithm will have linear time complexity. Jul 7 '15 at 21:35
• @DavidC.Ullrich $O(10^9) = O(1)$, using this notation in such a way is just confusing. Jul 7 '15 at 21:40

EDIT: The period of repetition I claimed was incorrect. Thanks to @dtldarek for pointing out my mistake. The relevant, correct statement would be

For $n\geq 3$, the last $n$ digits of the Fibonacci sequence repeat every $15\cdot 10^{n-1}$ terms.

So for the particular purpose of getting the last $10$ digits of $F_{1{,}000{,}000{,}000}$, this fact doesn't help.

For $n\geq 1$, the last $n$ digits of the Fibonacci sequence repeat every $60\cdot 5^{n-1}$ terms. Thus, the last $10$ digits of $F_{1{,}000{,}000{,}000}$ are the same as the last $10$ digits of $F_{62{,}500{,}000}$ because $$1{,}000{,}000{,}000\equiv 62{,}500{,}000\bmod \underbrace{117{,}187{,}500}_{60\cdot 5^9}$$ This will help make the problem computationally tractable.

• This is great! This willl save some computation time, when the numbers are getting even bigger :) Jul 7 '15 at 21:47
• I thought the period of $F_n \bmod 10^k$ is $15\cdot 10^{k-1}$ for $k\geq 3$? Jul 7 '15 at 21:51
• @dtldarek: Damn, you're right, I just remembered incorrectly. Wikipedia confirms. Jul 7 '15 at 21:59
• @Cubinator73: Please unaccept, my answer is incorrect. Jul 7 '15 at 22:00

A hint regarding some of the comments: Say $$X_n=\left[\begin{array}{}F_n\\F_{n+1}\end{array}\right].$$ Then $$X_{n+1}=AX_n$$for a certain $2\times 2$ matrix $A$. So you just have to calculate $A^n$.

Why would you go to the trouble of implementing $2\times 2$ matrix multiplication? Because then you can use "fast exponentiation", giving the result in time $\log(n)$. An example giving the idea of that: You'd calculate $A^{11}$ as $$A^{11}=AA^2A^8,$$after finding $A^{2^k}$ for $1\le k \le 3$. Which you do very quickly using $$A^{2^{k+1}}=\left(A^{2^k}\right)^2$$in a loop. A very short loop...

Oh. Didn't realize that's what the link "indeed" went to. Anyway there it is.

You idea is very good, but the digits are only preserved in every iteration iff the modulus is a multiple of $10^{10}$. In other words, look at $$\tilde{F}_{n+1} = (\tilde{F}_n + \tilde{F}_{n-1}) \bmod 10^{10}$$ instead. $\tilde{F}_{1000000000}$ will then consist exactly of the last $10$ digits of $F_{1000000000}$

• Also thank you for the tip with the modulus :) Jul 7 '15 at 21:48

Given the following Mathematica code, based on identities found here

Clear[f];
f[0] := 0;
f[1] := 1;
f[2] := 1;
f[n_ /; Mod[n, 3] == 0] := f[n] = With[{m = n/3},
Mod[5 f[m]^3 + 3 (-1)^m f[m], 10^10]];
f[n_ /; Mod[n, 3] == 1] := f[n] = With[{m = (n - 1)/3},
Mod[f[m + 1]^3 + 3 f[m + 1] f[m]^2 - f[m]^3, 10^10]];
f[n_ /; Mod[n, 3] == 2] := f[n] = With[{m = (n - 2)/3},
Mod[f[m + 1]^3 + 3 f[m + 1]^2 f[m] + f[m]^3, 10^10]];

evaluating f[1000000000] results in

1560546875

in less than a 0.000887 seconds.

The only evaluations it does are

f[0] = 0
f[1] = 1
f[2] = 1
f[3] = 2
f[7] = 13
f[8] = 21
f[23] = 28657
f[24] = 46368
f[69] = 9030460994
f[70] = 2490709135
f[209] = 3274930109
f[210] = 9082304280
f[627] = 3331634818
f[628] = 5364519011
f[1881] = 6891052706
f[1882] = 7684747991
f[5645] = 9674730645
f[5646] = 6983060328
f[16935] = 3041238690
f[16936] = 6494990027
f[50805] = 9095828930
f[50806] = 1802444783
f[152415] = 8092298210
f[152416] = 439009787
f[457247] = 3467735873
f[457248] = 3439061376
f[1371742] = 3463150271
f[1371743] = 8878860737
f[4115226] = 976213368
f[4115227] = 2499441093
f[12345679] = 9190666621
f[12345680] = 4288166885
f[37037037] = 2169005442
f[37037038] = 1145757919
f[111111111] = 7067038114
f[111111112] = 440574219
f[333333333] = 6434013378
f[333333334] = 4572218287
f[1000000000] = 1560546875
• The same code gets the last million digits in less that four seconds. Jul 8 '15 at 0:03
• Ok, so my 1560546875 for the last ten digits of $F_{10^9}$ was right, great. Of course $10^9$ is a little small. I get the last ten digits of $F_{10^{10000}}$ in three or four seconds. With homemade Python, code implementing the hints in my answer. Jul 8 '15 at 0:23
• I cannot get past $F_{10^{100000}}$ because the recursion is killing me. One could precompute the values of f which are needed, and compute the function in the reverse order,thereby avoiding all recursion, and that should get one much further. Maybe someone with the energy can try? Jul 8 '15 at 0:37
• Notice that David is using essentially identities for the duplication of the argument while mine are for triplication — as 3 is larger than 2, this is in the long run much faster :-) Jul 8 '15 at 0:42
• Touche. New worlds to conquer - invent "ternary exponentiation". Then quartic, quintic, I think I'm going to like sextic... Jul 8 '15 at 0:46