Number of Primes with Desired Digit Strings

This post was previously very, very wrong. It has been corrected as of July 12th, 2011.


Greetings and salutations to my loyal readers (there are about 30 of you I think)!

I've been a bit busy recently organizing an online study group for The Feynman Lectures on Physics, so today I'll just post a short note based on an observation someone made about my last post on the Kempner series.

The observations was that since the prime harmonic series (1/2 + 1/3 + 1/5 + 1/7 + 1/11 + ...) diverges, we can take out all the terms with a specific sequence of digits to make the series convergent as we did with the harmonic series. Or in other words:

"given any finite string of numbers, i.e. 24485983 that there exist infinitely many primes whose base 10 representation contain that string."

We knew from the my last post that the harmonic series became convergent if we took out all the terms with a '9' (or more generally any string of digits). For example, we could take out all primes with the digit string '13'. This would make the harmonic series convergent (after removing all the terms with '13'). Now consider the prime harmonic series, which is a subset of the original full harmonic series. Since the prime harmonic series diverges to infinity, we must have taken out an infinite number of primes with '13'. Therefore, the conclusion is that there are an infinite number of primes with any string of digits you can imagine.

The purpose of this note was to show that the same conclusion could be reached via a direct proof rather than as a corollary of another proof. However, I realized that my direct proof had a rather large flaw in it. As a cop-out, I'll show in this note that one can prove this result as a corollary of another theorem, namely Dirichlet's theorem for prime progressions.

Proof

Dirichlet's theorem states that there are infinitely many primes in the arithmetic sequence \[a, a+d, a+2d, a+3d, \ldots\] where $a$ and $d$ are coprime.

To prove that there are infinitely many primes which contain '13', set $a=13$ and $d=100$. We get the sequence 13, 113, 213, ... in which all terms contain the digit string '13' and by Dirichlet's theorem must contain an infinite number of primes.

$\blacksquare$

Although we used Dirichlet's theorem for showing this particular result, there are other theorems we could have used as well. For example, we could have used the fact that the prime counting function $\pi(x)$ is bound by \[\frac{1}{2}\frac{x}{\log(x)}<\pi(x)<2\frac{x}{\log(x)}.\]
Just so I don't feel like a complete hack, here are some exercises for you guys.

Exercises

1. Prove that there are infinitely many primes containing 42 (if you use Dirichlet's Theorem, use it carefully).
2. Prove that there are infinitely many primes starting with the digits 42.