# Fibonacci sequence digits

We define the Fibonacci sequence by $F_{n+2}=F_{n+1}+F_{n}$, with $F_0=0$ and $F_1=1$.
How to compute the last $30$ digits of $F_{2^{200}}$ for instance? can we use Python?how?

• A simple straight forward method would be using the en.wikipedia.org/wiki/Fibonacci_number#Matrix_form with a fast square-and-multiply exponentiation algorithm $\bmod 10^{30}$. Jan 14 '16 at 12:25
• Cannot give a Python script, but with the Pari/GP function fm(n)={local(f,m); m=10^30; f=[Mod(1,m), Mod(1,m); Mod(1,m), Mod(0,m)]; lift((f^n)[1,2])} implementing the matrix power idea, you get with fm(2^100) the value $$F_{2^{100}} \bmod 10^{30} = 510152048013283132235917685307$$ Jan 14 '16 at 13:24

We may use the Chinese remainder theorem and compute $F_{2^{100}}\pmod{5^{30}}$ and $F_{2^{100}}\pmod{2^{30}}$ by exploiting the properties of the associated Pisano periods (for instance, the period of the Fibonacci sequence $\pmod{5^n}$ is just $4\cdot 5^n$) or consider that it is simple to compute $(F_{2k},L_{2k})$ from $(F_k,L_k)$, since:
$$F_{2k} = F_k L_k, \qquad L_{2k}=5 F_k^2+ 4(-1)^k. \tag{1}$$ $(1)$ gives that we just need to perform $200$ multiplications in $\mathbb{Z}/(10^{30}\mathbb{Z})$ to recover the last $30$ digits of $F_{2^{100}}$.