Proof that there are infinitely many prime numbers starting with a given digit string

Question

To prove the following fact: given any sequence of digits in any base, eg 314159265358979323 base 10, there are infinitely many primes that start with these digits,eg when expressed in decimal they start with 314159265358979323. I think using a prime number theorem will be helpful . But I am still not getting a point of how to start the proof.

Answer 1

We use the Prime Number Theorem, nothing else, and do all the details for a particular case. The method used can be easily transferred to the general case.

Let $\pi(x)$ be the number of primes that are less than or equal to $x$. For any real number $x>1$, let $F(x)=\dfrac{x}{\ln x}$. The Prime Number Theorem says that $$\lim_{x\to \infty}\frac{\pi(x)}{F(x)}=1.$$ By the definition of limit, given any positive $\epsilon$, we have $$1-\epsilon <\frac{\pi(x)}{F(x)} <1+\epsilon\qquad\text{(Inequality $1$)}$$ if $x$ is large enough. (The meaning of "large enough" depends on the value of $\epsilon$.)

We will show that there are infinitely many primes whose hexadecimal representation starts with $324$. Why $324$? The hexadecimal representation of $\pi$ starts with $3.24$. The OP used a much longer string of digits, also connected to $\pi$. But something of that length, in either hex or decimal, would be a nuisance to type. It seems appropriate to use initial "digits" of $\pi$, since we will be working with $\pi(x)$. Why hexadecimal? To show that the base does not matter. Also, the question originally came from a programming site! Why not use a general beginning and a general base? Because doing so might conceal the basic simplicity of the argument.

Important Note: In what follows, the numbers $324$ and $325$ appear often. They are always to be read as numbers to the base $16$. (So, for example, $324$ refers to the number which in base ten would be written as $804$.) The base $16$ occurs fairly often. Of course, it must be read in base ten! The few other numbers that appear, unless it is otherwise specified, are to be read as base $16$ numbers. Occasionally, for emphasis, the base is explicitly mentioned.

We want to show that there are arbitrarily large integers $n$ for which there is a prime $p$ with $$324_{16}\times 16^n <p < 325_{16}\times 16^n.$$ (The above inequality is equivalent to saying that the first three hexadecimal "digits" of $p$ are $3$, $2$, and $4$.)

By Inequality $1$, the number of primes less than $325\times 16^n$ is $>(1-\epsilon)F(325\times 16^n)$. Again by Inequality $1$, the number of primes less than $324\times 16^n$ is $<(1+\epsilon)F(324\times 16^n)$. So the number of primes in the interval ($324_{16}\times 16^n, 325_{16}\times 16^n)$ is greater than $(1-\epsilon)F(325\times 16^n) -(1+\epsilon)F(324\times 16^n)$. Thus if
$$(1-\epsilon)F(325\times 16^n) -(1+\epsilon)F(324\times 16^n)>0,$$ there must be at least one prime between our two bounds. (Recall that we are counting primes. If an inequality tells us the count is greater than $0$, that count is at least $1$.)

So we want to choose $n$ large enough so that Inequality $1$ is satisfied, and such that $$(1-\epsilon)\frac{325\times 16^n}{\ln(325\times 16^n)}>(1+\epsilon)\frac{324\times 16^n}{\ln(324\times 16^n)}.$$ The "laws of logarithms," together with some rearranging, show that the above inequality is equivalent to $$n(\ln 16)(1-649\epsilon)>(1+\epsilon)(324)(\ln 325)-(1-\epsilon)(325)(\ln 324)\qquad\text{(Inequality $2$)}$$ Note that $649$ is to be read in base $16$. Now we are ready for the final push.

First, let $\epsilon$ be the reciprocal of $1000_{16}$ (this reciprocal is safely less than the reciprocal of $649_{16}$).

Then on the left of Inequality $2$ we have $n$ times a positive constant, and on the right we have a constant. Next, let $n$ be large enough to ensure that Inequality $1$ is satisfied for our chosen value of $\epsilon$ and $x >324\times 16^n$.

Finally, let $n$ be also large enough to ensure that Inequality $2$ is satisfied for our chosen value of $\epsilon$. Then there is always a prime between $324_{16}\times 16^n$ and $325_{16}\times 16^n$, that is, a prime whose initial hexadecimal "digits" are $3$, $2$, and $4$.

Only minor editing changes are needed to make the argument work for any initial "digit" sequence, and any base.

Answer 2

A simple consequence of the PNT is the fact that for any real number $k>1$ there exists an $n_0$ such that there is a prime between $n$ and $kn$ for all $n > n_0$. Now suppose your desired starting base-$b$ sequence is $d$ digits long; set $k = 1 + b^{-d}$ and apply the preceding fact.

Answer 3

This is a special case of the following fact, a simple and short proof of which appears on p. 4 of Disjunctive sequences: An overview, by Calude, Priese and Staiger (1997):

• If $a_1, a_2, a_3, \dots$ , is a strictly increasing infinite sequence of positive integers such that $\lim_{n \rightarrow \infty} (a_{n+1}/a_{n}) = 1$, then for any positive integer $m$ and any integer base $b ≥ 2$, there is some (and hence infinitely many) $a_n$ whose expression in base $b$ starts with the expression of $m$ in base $b$.

The desired result follows by taking $a_n$ to be the $n$th prime $p_n$, noting that the prime number theorem implies $p_n \sim n \ln n$, and hence that $\lim_{n \rightarrow \infty} (p_{n+1}/p_{n}) = 1$.

Answer 4

Use the prime number theorem to prove that there is an N such that for every M>N there is at least one prime that is written as 314159265358979323 followed by M other digits.

(Heuristically: There are $10^M$ possible numbers of this form, and the probability of each of them being prime is asymptotically proportional to 1/M -- thus the expected number of primes in each such interval grows towards infinity. Devising a rigorous argument from this sketch and one of the exact-bound versions of the prime number theorem is left as an exercise :-)