Finding the least prime of the form $6^{6^6}+k$

Question

I try to find the least prime number of the form $6^{6^6}+k$. I sieved out the candidates by trial division upto $10^6$, but there are still many candidates left upto $k=10000$

• How can I further reduce the number of candidates ?

• Where can I download a FAST calculator able to check numbers of this magnitude ($36306$ digits) ? PARI can do this, but takes about $10$ minutes which is too much considering the number of tests probably required.

  I do not want to prove the number to be prime. I am content if the number is pseudoprime for base $2$.

Answer 1

By examining A103111 you can see that $k=96545,$ found by the late Donovan Johnson in 2008. Otherwise srsieve and pfgw are a pretty good combination.