Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

To ask in another way: Is it guaranteed that any given sequence of digits will be at the beginning of some prime number?

We know from Dirichlet's theorem that there are an infinite number of values of $n$ such that $k*n+b$ is prime, as long as $k$ and $b$ share no factors.

Adding digits to the end of some number $k$ in base $B$ can be written in the form $k*B^{n} + b$. Can we use Dirichlet's theorem to guarantee that this will generate some prime number?


Motivation: This is how so-called "illegal primes" were found, but I'd like to be familiar with the theory of why it works.

share|improve this question
add comment

2 Answers

up vote 11 down vote accepted

I also don't see how to use Dirichlet's arithmetic progression theorem. But I see an easy proof using the prime number theorem. I don't see a more elementary way yet.

The solution goes like this. Take an arbitrary number $k$. We want to prove that there is a natural $n$ such that interval $[k \cdot B^n, (k+1) \cdot B^n)$ contains at least one prime. We will show that this is in fact true for all $n$ starting from some $n_0$ (that may depend on $k$, of course).

In terms of the prime counting function, we want to show that $\pi((k+1)B^n) > \pi(k \cdot B^n)$, where $\pi$ is the prime counting function and $n$ is large enough.

Pick an arbitrary $\varepsilon > 0$. By the prime counting theorem, when $x$ is large enough, we have $1 - \varepsilon < \pi(x) \ln x / x < 1 + \varepsilon$. Then, when $n$ is large enough, we have $$ \begin{array}{rcl} \pi(k B^n) & < & (1+\varepsilon) \frac{k B^n}{\ln k + n \ln B} \qquad \text{and} \\ (1 - \varepsilon) \frac{(k+1)B^n}{\ln (k+1) + n \ln B} & < & \pi((k+1)B^n). \end{array} $$

Now, $\varepsilon$ is arbitrary. Let us pick $\varepsilon$ in such a way that $(1 + \varepsilon) k < (1-\varepsilon)(k+1)$. Then, for $n$ large enough, we have $\pi(kB^n) < \pi((k+1)B^n)$, QED.

share|improve this answer
add comment

The answer to the question in the title is "yes" (and more is in fact true), but I am unsure if Dirichlet's theorem can be used to prove it.

In Sierpinski's book "A Selection of Problems in the Theory of Numbers" he writes:

"If we have two arbitrary sequences of digits (in decimal notation) $a_1, a_2, \dots, a_m$ and $b_1, b_2, \dots, b_n$, where $b_n = 1, 3, 7$ or $9$, then there exist arbitrarily large primes $p$ such that the first $m$ digits are successively $a_1, a_2, \dots, a_m$ and the last $n$ digits are successively $b_1, b_2, \dots, b_n$."

He also says that the proof of this is difficult although it can be carried out in an elementary way, and refers to a paper of his:

"Sur les nombres premiers ayant des chiffres initiaux et finales donnés", Acta Arith. 5 (1959), pp. 1046-1047.

share|improve this answer
    
Thanks for sharing that gem! That's neat that it covers both ends of the number. I was wondering if Dirichlet's theorem could be used to connect the digits of two co-prime numbers with an arbitrary number of zeros between them to make a prime. You really hit on an theorem that is close to that. Thanks! –  shaun Oct 19 '13 at 19:29
    
@shaun You are welcome. Unfortunately, I have not been able to locate an actual copy of those pages from the journal - maybe someone will find it somewhere. –  Old John Oct 19 '13 at 20:05
add comment

Your Answer

 
discard

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.