MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 8 down vote accepted

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.

share|cite|improve this answer
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".

share|cite|improve this answer

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.

share|cite|improve this answer
D'oh! Beaten to the punch :-) – Alon Amit Oct 27 '09 at 18:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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