18:32
Actually, another improvement. If you're diagonally iterating through all pairs (a, b), rather than checking the integers a and b, check the a'th prime and the distance between the a'th prime and the a+b'th prime.
And if said distance is smaller than the k you're looking for, you can rule it out (I think)
Only downside to that is that you'll end up checking really big intervals before big primes (which may or may not be a problem)
The goal ultimately would be to find the an + b
sequence of k
primes that minimizes b + n(k - 1)