So, I've got this problem:
Given a string $\omega\in\{0,\ldots,9\}^*$, find the smallest prime number (in base 10) that contains that string, or otherwise returns 0.
What I'm asking is a fast algorithm for the problem?
So, I've got this problem:
Given a string $\omega\in\{0,\ldots,9\}^*$, find the smallest prime number (in base 10) that contains that string, or otherwise returns 0.
What I'm asking is a fast algorithm for the problem?
This answer only shows that every string actually appears in some prime. Without loss of generality, $\omega$ doesn't start with zero (otherwise, consider $1\omega$ instead). Consider all digits in the range $\omega \times 10^N$ to $\omega \times 10^N + 9 (10^{N-1} + \cdots + 10^0)$, an interval of length $10^N$. Let $M = \omega \times 10^N$. According to the prime number theorem, there are roughly $(M+10^N)/\log M - M/\log M \approx 10^N/\log M$ prime numbers in this interval. Since $10^N/\log M \to \infty$, for large enough $M$ there will be a prime number in the interval, and its most significant digits would be exactly $\omega$.
I don't expect there to be an algorithm much faster than going over all primes in sequence. If you expect the answer to be one of the first few primes (here few can be a rather large number, say $10^9$), then you can probably do some preprocessing to be able to handle such queries fast.