1
$\begingroup$

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?

$\endgroup$
  • $\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$ – Raphael Jan 23 '14 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 Filmus Jan 23 '14 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$ – Juho Jan 23 '14 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$ – Raphael Jan 23 '14 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$ – Juho Jan 23 '14 at 18:13
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.