Can we prove that infinite many primes begin with any given digitstring? With Dirichlet's theorem, we can easily prove that infinite many primes end with a given digitstring with final digit $1,3,7$ or $9$. 

Can we also prove that infinite many primes begin with a given digit-string with first digit non-zero ?

Intuively, this should be the case, but I wonder whether we can show it rigorously. I thought of prime gaps, but I am not sure whether the best proven prime gaps are sufficient.
 A: Yes.  All you need is a prime gap of the form $p_{n+1}-p_n\lt (p_n)^\theta$ for $\theta\lt 1$; this is well-known (Wikipedia suggests that Hoheisel was the first to prove a bound of this form). Once you've got that, it becomes a matter of simple math; let $K$ be the initial digit string, of length $k=\lceil\log_{10}(K)\rceil$. Then the difference between e.g. $10^n\cdot K$ and $10^n\cdot(K+1)$ is $10^n$ whereas we have $10^n\cdot K\lt 10^{n+k}$. Now just choose $n$ such that $\theta\cdot (n+k)\lt n$; then the gap between $10^n\cdot K$ and $10^n\cdot (K+1)$ is larger than the largest possible prime gap there.
Note that this proves even more that was asked: not just that there are infinitely many primes of the given form, but that given an initial digit string, then for every sufficiently large $n$ there's at least one $n$-digit prime beginning with that digit string.
A: By the Prime Number Theorem, for any fixed $\epsilon>0$, we have  $\pi((1+\epsilon)n)-\pi(n)\to\infty$ as $n\to\infty$. In particular, for any number $a$ representing the desired initial digits, we will find many primes between $a10^k$ and $(a+1)10^k$ for all large enough $k$.
