Strings of digits and prime numbers

This weekend, I attended a conference about geometry and topology. Last night was the conference banquet and there I was sitting in a table at dinner time with a bunch of mathematicians. After some egg rolls and a wonton soup, and obvious topic made its appearance: prime numbers.

My friend Brian Streit was sitting next to me, and in the middle of the dinner he proposed this interesting and rather old question:

Given any string of digits, can one find a prime number ending in such a string? How about beginning in it?

My immediate reaction was to answer yes to both questions, as I recall seen them before in my early olympic training days.

That also made me remember a conjecture that was given to me few months ago by one of my friends back home, Rafa Martinez, who was claiming the following:

Given any string of digits, there exists a digit such that you can insert it in at a position in the original string such that the resulting number is prime.

This statement is in a sense much stronger than the previous one, and as strong as it seems, it turns out to be false, but thinking about it can make you discover some interesting properties about prime numbers and base representation of numbers.

When Rafa gave me this problem, he was so convinced of its validity and I was so convinced of its falsity, that I started looking for a counterexample. First, I started with a single digit prime number, then I start looking for two digit prime numbers that contained the first one. Then I looked for 3-digit prime numbers that contained the previous one and so on.

The first counterexample that I found by this method was 612113, but thinking of this led me to state the same question but in a different base, say $b$. Of course, the statement will still be false, but now, depending on $b$, the length of the counterexample would be different. For instance, if we are in base 2, a counterexample would be 1 (which is not prime), in base 3 we have for example 212, etc.

Basically, this phenomenon is due to the rate of growth of the prime numbers and how that can be related with the base in which numbers are written in.

Broadly speaking, we can make use of the prime number theorem to establish the rate of growth of prime numbers. It basically says, in simple words, that prime numbers grow in a logarithmic way, notice I'm not talking about the density of the primes, but about the size of a prime itself.

Hence, there is a high probability that if a number $p$ is prime, then "$ep$" is also a prime number, which, in some sense says that the most natural "base" to write prime numbers in is un "base $e$".

Of course $ep$ is not a prime number, as it is irrational, even more, what does "base $e$" mean anyway? The idea is to use this approach to find some appropriate bases for writing prime numbers. An appropriate base would be one such $b$ is close to a power of $e$. The first of these such powers is

$b=20\sim e^3=20.085536923187667740928529654581717896987907838554150144...$

The next one is

$b\sim e^8=2980.9579870417282747435920994528886737559679391328357022089...$

and so on.

Of course, changing base representation wont make the behavior of prime numbers different or anything like that, but maybe using this representations could lead to nice patterns on its representations.

After this little digression, I was then left with the original question of Brian, which I didn't think until today in the morning when I was discussing it about with other participant of the conference.

About the question that if you could find a prime number starting with a given string of digits (not ending in even or 5,0 of course) the simplest solution I could think was using Dirichlet's theorem on arithmetic progressions. Given a string of digits $a$, we look at the sequence

$a+k10^n$

with $k$ running over the positive integers and $n$ been the length of $a$. Hence Dirichlet's theorem asserts that there are in fact, infinitely many primes in this sequence, and hence, infinitely many numbers answering positively the question posed.

For the remaining question, my proof didn't come as quickly as the previous one, and it took me the entire last talk (which sadly I didn't pay attention to) to come up with a proof, aided with my good old friend Wikipedia.

I found this interesting fact about prime gaps due to Hoheisel, that states that

$p_{n+1}-p_n \leq p_n^\theta$ for $\theta$ less than 1

where $p_n$ is the $n$th prime number.

With the help of this, proving the statement is not really hard. Proceeding by contradiction, suppose that $a$ is a given string of digits, and that there is no prime number in between $a10^m$ and $(a+1)10^m$ for all $m$, hence this would imply that the relative gap of prime numbers would be of at least

$\frac{ a 10^m- (a+1) 10^m}{a 10^m}=\frac{1}{a} $

but by Hoheisel's result, as $n\to\infty$

$ \frac{p_{n+1}-p_n}{p_n}\to 0$

which leads to a contradiction.

I particularly find really interesting this connections between prime distributions and base representations, it seems that we don't completely understand yet the interaction of these two, but definitely there is an intimate relation among them.