# Prepending strings and primes?

we all know that 31,331,3331,33331,333331,3333331,33333331 all are primes. 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 -> N \cup {\infty}$ by: $m(A,B)= |${all prime members of the list AB, AAB, AAAB, ...up until but not including the first composite member}| (the size of the set).Then: Does m ever take the value $\infty$ ? If not, is it an unbounded function?

-
Not an expert, but an indication that this question may be harder than at first sight (though I may be completely off base here). Your question would be answered in the affirmative by the Tao-Ziegler extension to the Green-Tao theorem if you can in addition prove a theorem about the asymptotic density/distribution of solution pairs $(x,m)$ in terms of the coefficients of the polynomials $P_k$. In other words, your question is the content of the Tao-Ziegler theorem with additional restrictions. So my guess is that... – Willie Wong Dec 21 '10 at 15:49
either (a) your additional constraints are too strong and there's a easy reason why $m$ is a bounded function (I consider that unlikely) or (b) your constraints are weak enough that the answers are in fact positive (at least for part 2), but will require some heavy machinery to prove. – Willie Wong Dec 21 '10 at 15:51
It's conjectured that there are infinitely many primes of the form 1, 11, 111... ie $10^n-1$, and this is in analogy with the conjecture that there are infinitely many Mersenne primes: of the form $2^n-1$. – Oscar Cunningham Dec 21 '10 at 16:00
@Oscar: I fail to see how 1, 11, 111 etc are $10^n-1$... – Willie Wong Dec 21 '10 at 17:59
Right you are, that should have been $\frac{10^n-1}{9}$ – Oscar Cunningham Dec 21 '10 at 19:08

I think it's easy to show that $m$ is finite. Assume $AB$ is prime (otherwise, $m=0$, which is extremely finite). I'll prove there are later terms in the sequence divisible by $AB$. Subtract $AB$ from each of the later terms in the sequence (that won't affect divisibility by $AB$), then all I have to do is show $AB$ divides $AA\dots A00\dots0$, indeed, $AA\dots A$, for some number of repetitions of $A$. If $A$ is of length $s$, then $AA\dots A=A\times(10^{ns}-1)/(10^s-1)$ where $n$ is the number of repetitions of $A$. If we take $n=AB-1$, then by Fermat, $AB$ divides $(10^s)^n-1$, and we're done.
Proving $m$ is unbounded looks harder. It's not a million miles from proving that for every $m$ there's a prime $p$ such that $2p+1,4p+3,\dots 2^mp+2^m-1$ are all prime (in binary, these are the numbers you get from $p$ by tacking ones onto the right end of it), and that's a notorious unsolved problem.