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?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
6
|
|
|||
|
|
|
8
|
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. |
||||||||
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
5
|
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". |
||
|
|
|
4
|
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. |
|||
|
