I first encountered **PARI/GP** when lumyk posted a solution for Project Euler Problem 258:

“A sequence is defined as:

g_{k}= 1, for 0k1999g_{k}=g_{k-2000}+g_{k-1999}, fork2000.Find

g_{k}mod 20092010 fork= 10^{18}.”

One solution was using matrix multiplication in 19 hours (!!!) and I was curious if lumyk’s claim that **PARI/GP** could solve it in 2s (!!!) was true.

so I tried it.

yup. 2 seconds. Now, that’s very, very fast. Once you’ve solved the problem, you can check out the forum for other algorithms for this lagged Fibonacci problem.

Advertisements