Suppose you have N symbols (e.g. "1","2",...,"N" or "a","b",...,"$") and a string of these symbols (say, the first trillion digits of pi). Then does there exist a prime number whose N-ary representation contains that string of digits?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
Yes. This follows from the strong version of Bertrand's postulate. For example, to see that there is a prime which contains the digits 314159, use the fact that there is a prime between 314159*10^N and 314159*10^N*(1.000001) for N sufficiently large.
answered Oct 27, 2009 at 17:39
-
$\begingroup$ What is it, Bertrand's postulate week? $\endgroup$ Commented Oct 27, 2009 at 18:54
-
3$\begingroup$ Every week is Bertrand's postulate week. $\endgroup$– S. Carnahan ♦Commented Oct 28, 2009 at 2:18
$\begingroup$
$\endgroup$
If the sequence of digits ends in a digit that is coprime to N, one can make the stronger statement that there exists a prime number whose final digits are exactly that sequence; this is just Dirichlet's theorem about primes in arithmetic progression.
If the last digit isn't already coprime to N, just tack on an additional "1".
answered Oct 27, 2009 at 18:57
$\begingroup$
$\endgroup$
1
I think there's an easier way (well, easier if you assume Dirichlet's Theorem - I think it's simpler than the strong form of Betrand's Postulate). Interpret the string as an integer M in base N; if it happens to be relatively prime to N, you're done - use Dirichlet to find a prime congruent to M modulo N^k where k is the length of the string. David's method places the given string as the most-significant digits of the prime, whereas this approach places it as the least-significant ones.
If M happens to have a common divisor with the base N, you can just pad it with a "1" at the end (e.g. replace 31415 with 314151 in base 10). The padding replaces M by NM+1 which is obviously relatively prime to N.
answered Oct 27, 2009 at 18:58