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?
$\begingroup$
$\endgroup$
7
-
$\begingroup$ Okay, the problem is clear now. But what have you tried? So far, this is a dump of a problem, not a question. If you have a specific question regarding the wording of the problem or about concrete steps in your own attempts at solving the problem, feel free to edit accordingly and we can reopen the question. See here for a relevant discussion. $\endgroup$– RaphaelJan 23, 2014 at 13:34
-
$\begingroup$ Every string should be contained in some prime. That should follow from the prime number theorem. To find the very first prime containing it, I'm not sure there is anything smarter than just going over all of them in sequence. $\endgroup$– Yuval FilmusJan 23, 2014 at 13:40
-
1$\begingroup$ Is this going to be a practical algorithm (I guess so because you were talking about a C++ implementation)? If so, you should mention what additional constraints you might have. $\endgroup$– JuhoJan 23, 2014 at 13:51
-
$\begingroup$ @YuvalFilmus Maybe, if we fix $\omega$ as the most significant bits, it's possible to pad with less significant bits in a structured way so the result is prime? I don't know enough about number theory to have an informed intuition. $\endgroup$– RaphaelJan 23, 2014 at 17:10
-
$\begingroup$ An idea for a very fast practical implementation: precompute and store every prime up to a certain limit. Mark the indices of the first prime with $2, 3, \ldots, N$ digits. Given $\omega$, start going through the array from the first prime with at least $\omega$ digits. If you know something further about your queries or $\omega$, you can optimize this approach further. $\endgroup$– JuhoJan 23, 2014 at 18:13
|
Show 2 more comments
1 Answer
$\begingroup$
$\endgroup$
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.
answered Jan 23, 2014 at 20:58