As you know, I don't know Jack about number theory, so I need to ask.
If I'm not mistaken, there are k's that produce more primes than others. Is this predictable or trial and error?
If predictable, we could try the numbers with higher probability first.
May the professionals warp in.
H.