Solving Project Euler problem #258 using PARI/GP

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

“A sequence is defined as:

  • gk = 1, for 0 ≤ k ≤ 1999
  • gkgk-2000gk-1999, for k ≥ 2000.

Find gk mod 20092010 for k = 1018.”

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.

Solving Project Euler Problem #258 using PARI/GP

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

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s