MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 12 down vote accepted

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

share|cite|improve this answer
In comment (1), you still haven't eliminated $B=00\cdots01$, as then $B$ does not have any prime factors. – Kevin O'Bryant Dec 21 '10 at 20:10
Oh, right. Better to start with p a prime factor of $A 10^k+B$ and then modify the argument accordingly. – David Speyer Dec 21 '10 at 20:28
Similarly, you don't need B < R because you can just start from a late enough term of the sequence and take that (padded with some zeros) as B instead. – Zsbán Ambrus Dec 30 '10 at 18:09

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] == {}, 
     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]
share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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