4
$\begingroup$

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$?

$\endgroup$
  • 5
    $\begingroup$ Could we avoid using these OEIS numbers in the title? The title is addressed to human beings, not robots. $\endgroup$ – YCor Feb 11 '16 at 11:17
  • 1
    $\begingroup$ @YCor What title do you suggest? The sequence is defined too to put it in a better title IMHO. $\endgroup$ – joro Feb 11 '16 at 11:55
  • $\begingroup$ 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. $\endgroup$ – YCor Feb 11 '16 at 12:47
  • $\begingroup$ @YCor I prefer the new title too. To my knowledge I don't know "all the OEIS numbers". $\endgroup$ – joro Feb 11 '16 at 13:11
  • 1
    $\begingroup$ At least for $n \le 10^5$, it always suffices to insert one digit in each position. $\endgroup$ – Robert Israel Feb 12 '16 at 17:01
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – joro Feb 11 '16 at 12:07
  • $\begingroup$ 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. $\endgroup$ – user9072 Feb 11 '16 at 12:16
  • $\begingroup$ 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. $\endgroup$ – joro Feb 11 '16 at 12:32
  • 1
    $\begingroup$ I interpreted the wording of the problem to mean, inserting one digit between each pair of (adjacent) digits. $\endgroup$ – Gerry Myerson Feb 12 '16 at 22:53
  • 1
    $\begingroup$ @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. $\endgroup$ – user9072 Feb 12 '16 at 23:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.