Can we always attain another prime via inserting digits between the digits of a fixed prime?

The sequence OEIS A080437 is

For n > 10, let m = n-th prime. If m is a k-digit prime then a(n) = smallest prime obtained by inserting digits between every pair of digits of m.

I don't see why this sequence is defined for all $n$, i.e. why prime $a(n)$ must exist, that is why this process of digit-insertion always yields some prime.

For two digit primes, this appears an accident to me.

For sufficiently large primes, probabilistic arguments suggest it is defined.

Question: Is OEIS A080437 defined for all $n$?

• Could we avoid using these OEIS numbers in the title? The title is addressed to human beings, not robots. – YCor Feb 11 '16 at 11:17
• @YCor What title do you suggest? The sequence is defined too to put it in a better title IMHO. – joro Feb 11 '16 at 11:55
• I just suggest to not use such codes in title. The title is supposed to convey some idea of the subject, which helps me to decide if I want to open the post without further inquiry. Possibly you know by heart all OEIS numbers. I don't. Also many readers don't even know that what "OEIS" stands for. The new title looks fine to me. – YCor Feb 11 '16 at 12:47
• @YCor I prefer the new title too. To my knowledge I don't know "all the OEIS numbers". – joro Feb 11 '16 at 13:11
• At least for $n \le 10^5$, it always suffices to insert one digit in each position. – Robert Israel Feb 12 '16 at 17:01

It is always possible to construct a prime in the way described and the sequence is thus well-defined.

Let me first write out the process in more detail. For defining $a(n)$ we start with $p_n$ the $n$-th prime. Let it be $p_n=(d_{m-1} \dots d_0)_{10}$ where by the expression on the right I mean the decimal digit representation.

The numbers to consider then are $(d_{m-1}S_{m-1}d_{m-2} \dots d_2S_2d_1S_1d_0)_{10}$ where $S_i$ is a non-empty string of decimal digits.

The $a(n)$ is the smallest number of this form that is prime. The question to answer is whether there is a prime of this form at all. That we can/have to insert strings at several places is not very relevant. We fix $S_2, \dots, S_{m-1}$ as $0$, or whatever string we like.

The fact we seek to prove will follow from the following; a subscript $g$-adic means a $g$-adic digit expansion.

Lemma: Let $g \ge 2$ be an integer, let $b_{k-1}, \dots , b_{0}, c_{l-1}, \dots, c_{0} \in \{0,\dots, g-1\}$, and let the $c_i$ be such that $(c_{l-1}\dots c_0)_g$ is co-prime to $g^l$. Then there is a prime, indeed infinitely many, of the form $(b_{k-1} \dots b_{0}Sc_{l-1}\dots c_0)$ where $S$ is a non-empty string over $\{0, \dots, g-1\}$.

To prove this we recall the following consequence of the Prime Number Theorem in arithmetic progressions (or the stronger Siegel–Walfisz theorem).

Let $c>0$ real. Let $n\ge 2$ be a fixed natural number. For all sufficiently large $x$ coprime to $n$ the set $x+ i n$ with $0 \le i \le cx/n$ contains a prime number.

(The number of primes in the class of $x$ below $x$ is $\frac{1}{\varphi(n)}x/ \log (x) + O(x/(\log x)^2)$ while below $x+cx$ there are $\frac{1}{\varphi(n)}x(1+c)/ \log (x(1+c)) + O(x(1+c)/(\log x(1+c))^2 )= \frac{1+c}{\varphi(n)}x/ \log (x) + O(x/(\log x)^2 )$, and for sufficiently large $x$ this means there need to be some in between.)

Now for the proof of our lemma. Let $N_o= (b_{k-1}\dots b_0)_g$ and $N_u= (b_{k-1}\dots b_0)_g$. We introduce a parameter $p$ to be fixed later. We note that the set of all numbers of the form $(b_{k-1} \dots b_{0}Sc_{l-1}\dots c_0)$ where $S$ is a string of size $p$ is $N_u + g^l i + g^{l+p}N_o$ for $0 \le i < g^p$. We set $c= g^{-l-k-1}$. We set $x_p = N_u+ g^{l+p}N_o$ and we note $g^p> c x_p$. By assumption $N_u$ and thus $x_p$ is coprime to $g^l$. Thus if $x_p$ is sufficiently large there is a prime among $N_u + g^l i + g^{l+p}N_o$ for $0 \le i < g^p$. This can be attained by choosing $p$ large. This shows the lemma.

To finish the argument we apply the lemma with $d_0 = c_0$ and $b_{2i} = d_{i+1}$ and $b_{2i-1}=0$ for $i=1, \dots ,m$, for example (the choice of the $b_i$ is not really relevant). This is possible since $c_0=d_0$ is the lowest digit of a multi-digit prime and thus it is coprime to $10$.

• Thanks. How are we in "prime residue class mod 10"? 19 mod 10=9 is not prime. And don't you need bound for the smallest prime in AP to need only k-1 digits? – joro Feb 11 '16 at 12:07
• I call a residue class $a$ mod $n$ prime if $\gcd(a,n)=1$; then it will contain infinitely many primes. What I need is a result that says $[x,(1+c)x] \cap ( a+ 10 \mathbb{Z})$ contains something not too far of the usual number of primes. I will supply a reference later. – user9072 Feb 11 '16 at 12:16
• I see, I would call "prime residue class" something like "coprime AP" in this case. I would prefer answer not based on purely probabilistic arguments like "from 10^(k-1) numbers < 10^(2k-1) the probability at least one is prime tends to one". Maybe will edit after your answer. Thanks. – joro Feb 11 '16 at 12:32
• I interpreted the wording of the problem to mean, inserting one digit between each pair of (adjacent) digits. – Gerry Myerson Feb 12 '16 at 22:53
• @GerryMyerson I pondered this for a while too. But first it says "by inserting digits between every pair" (plural), but this is not completely unambiguous yet. But then there is this phrase in the OEIS description: "There are (k-1) places where digit insertion takes place and a(n) contains at least 2k-1 digits." To say at least 2k-1 digits makes only sense if one can insert more than one digit. – user9072 Feb 12 '16 at 23:51