4
$\begingroup$

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?

  • 0
    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](http://en.wikipedia.org/wiki/Green%E2%80%93Tao_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...2010-12-21
  • 1
    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.2010-12-21
  • 0
    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$.2010-12-21
  • 0
    @Oscar: I fail to see how 1, 11, 111 etc are $10^n-1$...2010-12-21
  • 0
    Right you are, that should have been $\frac{10^n-1}{9}$2010-12-21
  • 0
    This is much harder than the question you asked on MO. Do you want the answer to your original question?2010-12-21
  • 0
    Qiaochu: Thank you! I did however figure it out after your nice comment there. So no need to.2010-12-22
  • 0
    What made you think that we all know that $31$, $331$, $3331$, $33331$, $333331$, $3333331$, $33333331$ are primes? I didn't.2011-10-10

1 Answers 1

2

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.

Well, there are a few little things I've swept under the rug here, but I think they're all easily handled.

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.