For any given prime number, can you estimate what the next prime will be based on any pattern apparent in the sequence of the previous primes?

‘Hey, Salviati, can you estimate the next prime after 100003?’

‘Sure. It’s 100019.’

‘Wait, what? How did you know?’

‘Oh, easy. 9991=100^2-9=(100-3)(100+3), so 99910 is divisible by both 97 and 103, so neither 99910+97 nor 99910+103 can be prime. This takes care of 100007 and 100013. Both 100011 and 100017 are obviously divisible by 3, while 100009 is divisible by 7, which leaves 100019. I ran a quick primality test and it is, indeed, prime. So there you go.’

‘No no no no, you don’t understand! I didn’t want you to find the next prime with all these crazy computations, I wanted you to estimate it.’

‘Estimate? Why would I estimate if I can calculate?’

‘Because calculating is hard! I’m looking for an easy way, using patterns.’

‘What patterns?’

‘Patterns in the previous primes leading up to it.’

‘Simplicio, my good man. There are 9593 primes below 100003. You want me to process nine thousand previous primes as an easy way to estimate the next prime?’

‘Well, I’m hoping there’s some pattern…’

‘Of course there’s a pattern. Those are the prime numbers, dude, they are among the simplest of sequences, determined by the simplest of rules. Rules are patterns.’

‘Ha, really? So what’s the pattern?’

‘If you actually gave me those 9593 previous primes, all I would have needed to do is skip-count from each of them to find their multiples, and then the first number left standing is your next prime. It’s a very nice pattern, really. Quite skippy-trippy.’

‘Oh well that’s because you pretend you already have all those earlier primes. What if you don’t?’

‘You want me to estimate the next prime after 100003 using patterns in the sequence of previous primes without having the sequence of previous primes? Where am I supposed to look for a pattern?’

‘Well, I… ugh, you make everything so complicated! I’m asking a simple question: can you *quickly* estimate the next prime using some *simple* pattern in the previous primes?’

‘Sure, I can very quickly estimate the next prime, much more quickly than actually finding it. The next prime after anything around 100000 is going to be about 12 numbers ahead, because the natural log of 100000 is about 11.5. Here we had to skip 16, which is a bit more than expected but not by much.’

‘You didn’t use any pattern in the previous primes…’

‘I know. I don’t need to. I have a pretty good estimate just from the number itself.’

‘Ok, but can you find a better estimate if you do include the previous primes?’

‘The trouble with your question is that you want to gain speed by offering data, but the data is so large that doing anything with it is very time consuming, so we can’t expect to gain speed. The constraints of the question are unreasonable, if not downright self-contradictory.’

‘Ok, ok. I know you always end up talking about polynomial-time and stuff. Is this solvable in polynomial time?’

‘We don’t know. The question isn’t really about finding primes, since we already know how to do that in polynomial time. The question is about the size of the gaps. Is it true that every prime is followed by another prime no more than, say, O(\log^2 n) away? If so, and it probably is, then a naive search would find the next prime in polynomial time. This is Cramèr’s conjecture, and it’s an interesting open problem.

However, (continued Salviati), there’s no meaningful way to define what a “pattern” might be beyond the simple pattern which is the very definition of the primes, and using previous primes cannot be much help in finding the next prime – mainly because you don’t need much help anyway. Algorithmically, it’s a fairly easy problem.’

‘So what’s the next prime after 2^{82589933}-1?’

‘Oh, it’s around 2^{82589933}+57000000, give or take.’

‘Really? Then find it!’

‘Simplicio, you’re simply insufferable.’