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?

  • 5
    $\begingroup$ 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}$. $\endgroup$ Jan 14 '16 at 12:25
  • 2
    $\begingroup$ 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$$ $\endgroup$ 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}}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.