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