# Prime numbers and strings of symbols

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?

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.

• What is it, Bertrand's postulate week? – Michael Lugo Oct 27 '09 at 18:54
• Every week is Bertrand's postulate week. – S. Carnahan Oct 28 '09 at 2:18

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".

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.

• D'oh! Beaten to the punch :-) – Alon Amit Oct 27 '09 at 18:58