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.

  • $\begingroup$ Cf. A018800. $\endgroup$ Dec 23 '14 at 20:44
  • $\begingroup$ Thanks so much @EricM.Schmidt $\endgroup$ Dec 29 '14 at 21:37

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.


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.

  • $\begingroup$ 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! $\endgroup$ Oct 19 '13 at 19:29
  • $\begingroup$ @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. $\endgroup$
    – Old John
    Oct 19 '13 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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