Prepending strings to primes.

Question

Hello, we all know that 31,331,3331,33331,333331,3333331,33333331 all are primes, and that 333333331 is not. Here we prepend the digit 3 to 31, to get a list of 7 primes.This gives me the following thought:

Let $$D = \{\text{all possible nonnull finite digit strings}\},$$ $$D' = \{\text{all things in D that do not start with 0}\}.$$
Define a function $m: D' \times D \to N \cup {\infty}$ by: $$m(A,B)= \min \{ k\geq 1 \colon A^kB \text{ is composite} \} - 1,$$ i.e., the number of consecutive primes at the beginning of the list $AB, AAB, AAAB, \dots$. For example, $m(3,1)=7$.

Which values does $m$ take? Is it unbounded? Is it ever $\infty$?

This question has been posted to math.stackexchange too, and I got one comment talking about that it might involve Tao-Ziegler extension to the Green-Tao theorem, and so I thought it might be more appropriate here. So please, excuse me if it's posted wrongly, or if one shouldn't post to both channels.

Answer 1

Two comments:

(1) It is impossible that $m(A,B)= \infty$. The sequence you are interested in is $B$, $10^k A+B$, $(10^{2k}+10^k)A+B$, $(10^{2k}+10^{2k}+10^k)A+B$, etcetera. Let $p$ be a prime dividing $B$. We claim that there is some $n$ such that $p$ divides $(10^{nk}+\cdots +10^{2k}+10^k)A+B$. Proof: if $p=2$ or $5$ then this is true for any $n$. If $p$ does not divide $10^k-1$, then $p$ divides $(10^{(p-1)k}-1)*10^k/(10^k-1)$ by Fermat's Little Theorem, so $p$ divides $(10^{(p-1)k} + \cdots + 10^k)A + B$. If $p$ divides $10^k-1$ then $10^{pk}+10^{(p-1)k}+\cdots + 10^k \equiv 1+1+\cdots+1 \equiv 0 \mod p$. So $p$ divides $(10^{pk}+10^{(p-1)k}+\cdots + 10^k )A+B$. In every case, we have found a non-prime member of the sequence.

(2) I don't see how to get arbitrarily many primes of this form out of Green-Tao or Tao-Ziegler. Given fixed $k$ and $\ell$, Green-Tao will tell you that there are $A$ and $B$ such that $B$, $10^k A+B$, $(10^{2k}+10^k)A+B$, ..., $(10^{\ell k} + \cdots + 10^{2k} + 10^k)A+B$ are all prime. But it won't guarantee that $A$ and $B$ are less than $10^k$. Tao-Ziegler guarantees that there is some base $R$ and some constant $R$ such that $B$, $R+B$, $R^2+R+B$, ..., $R^{\ell}+R^{\ell-1} + \cdots +R+B$ are all prime. So you can take $A=1$ if you are willing to work in bases other than $10$. But Tao-Ziegler doesn't guarantee that you can take $B<R$; the bounds in that paper go the other way, telling you that you can take $R=O(B^{\epsilon})$.

Answer 2

In base 10, here's a few values of $m$:

• $m(1,2) = 0$
• $m(1,1) = 1$
• $m(1,3) = 2$
• $m(33,1) = 3$
• $m(09,47) = 4, m(42,43) = 4$ (in case you dislike a leading 0 in $A$)
• $m(3,331) = 5$
• $m(87,323) = 6$
• $m(3,1) = 7$
• $m(867,1907) = 8$

By exhaustive search, the largest value of $m$ with both $A,B$ having 4 or fewer letters is 8.

Here's Mathematica code that evaluates $m$; usage is "m[{8,6,7},{1,9,0,7}]".

m[A_, B_] := 
  If[Union[A] == {0} || Union[A] == {}, 
     -Infinity,
     Module[{counter = 1, F},
       F[1] = Join[A, B];
       F[k_] := F[k] = Join[A, F[k - 1]];
       While[PrimeQ[FromDigits[F[counter]]], counter++];
     counter - 1]
    ]

Answer 3

To supplement David's answer, the 2nd option, I can add the following heuristics. If we fix a positive integer $n$ and take irreducible polynomials $$ f_k(x) =A\frac{x^{k+1}-1}{x-1}+B =A(x^k+x^{k-1}+\dots+x)+B, \qquad k=1,\dots,n, $$ subject to the condition that $f_1(x)\dots f_n(x)/m$ is not an integer-valued polynomial for all $m>1$ (take, for example, $A=3$ and $B=1$), then Schinzel's Hypothesis H implies that the numbers $f_1(R),\dots,f_n(R)$ are simultaneously prime for infinitely many positive $R\in\mathbb Z$. There is no guarantee however that $R$ assumes the form $10^k$. I owe this idea to Frictionless Jellyfish who removed his/her related comment to this post (which I would definitely accept as answer).