5

This question is more of a curiosity than anything.

Start with a prime number and consider concatenating digits onto the right hand side. Sometimes you can make a prime and continue the process making bigger primes but this process always ends.

I have checked this computationally and find the biggest such prime created is the number $73939133$.

My question is, does there exist a theoretical explanation as to why this process ends? I can't find one myself but I am convinced there should be a reason.

VividD
  • 15,966
fretty
  • 11,156
  • 1
  • 26
  • 37
  • I guess the prime you start with can only have one digit? – Tim Vermeulen Aug 27 '13 at 11:43
  • Well in my computations it did...but I think it also must end for primes of more than one digit? – fretty Aug 27 '13 at 11:44
  • Right, but then $73939133$ obviously is not the biggest prime you'll yield. – Tim Vermeulen Aug 27 '13 at 11:46
  • Well no but what i'm saying is originally I considered only one digit primes but I am conjecturing that the process always ends for ANY prime. If you can only see reasons why it should end for single digit primes then that will do though. – fretty Aug 27 '13 at 11:48
  • @fretty, just to check your calculations, which number did you start from to yield the biggest number as 73939133? – Parth Thakkar Aug 27 '13 at 11:52
  • Well it would be 7...to get 73,739,7393,73939,739391,7393913,73939133. – fretty Aug 27 '13 at 12:17

3 Answers3

4

Here is a very rough argument.

The average gap between primes of size about $p$ is about $\ln p$.

To add another digit to $p$ you have to find a prime amongst $10p+1$, $10p+3$, $10p+7$, $10p+9$. If there is a gap at least between $10p-1$ and $10p+11$ you won't be able to proceed.

Obviously your process is cherry-picking the best examples, but even so, as the gaps increase in size you are more likely to find yourself in the middle of a gap as on the edge (with a prime to pick).

It would take a special feature of the distribution of primes to suggest that the process of adding digits in base $10$ (which has no obvious reason to be special) could go on for ever.

Mark Bennet
  • 100,194
  • I was thinking along these lines but of course this is a heuristic argument, it doesn't prove that at some point it becomes impossible to extend...only that it is unlikely. – fretty Aug 27 '13 at 12:19
  • @fretty Indeed. But when the average gap gets, say, to $2 000 000$ you need a pretty good reason to believe you will keep hitting prime after prime. – Mark Bennet Aug 27 '13 at 12:21
  • Yeah sure. Hopefully there will be a rigorous proof out there. In doing my computations I found that the process of extending seems to work for quite a few strings until you hit to 7-8 digit point and the strings terminate. – fretty Aug 27 '13 at 12:28
  • @fretty The rigorous proof starting with single digit primes is to try all sequences and show they all terminate, which is a finite task, and which you say you've done. The reason the sequences terminate is that there aren't enough primes to sustain the process. If you can start with any prime, you can start with an abitrarily large one. – Mark Bennet Aug 27 '13 at 12:35
  • Yes, I accept that it is true but is there a profound reason why (without having to resort to heuristics)? Also given ANY initial prime must the process terminate? I believe it must (for the same kind of heuristics given in the answers here) but is there an actual proof? – fretty Aug 29 '13 at 07:10
2

Between $N$ and $N+10$ there are approximately $\frac{10}{\ln N}$ primes. So if there are $a_n$ primes with $n$ digits (either starting at this length or counting only those obtained step by step from one-digit primes), we count primes in intervals $[N,N+1]$ for $a_n$ distinct values of $N$ and each is $\approx 10^n$. Then in the next round we can expect $a_{n+1}\approx a_n\cdot \frac{10}{n\ln 10}$ primes by appending a digit. As $n$ grows, this quickly brings $a_n$ down to zero.

Hagen von Eitzen
  • 374,180
1

A more or less current record (as of 2007; belongs to J.K.Andersen, see Growing primes) is sequence $$ 133028062963:79339933399333 \,. $$ This means we start with prime number $133028062963$, then add digit $7$, then $9$, etc. Thus we have the sequence of $15$ primes, with each next term in it obtained from the previous one by tacking on one digit at the end.

However, I could not find anywhere a proof that there is no such infinite sequence - although in some web articles it was hinted at as a proven fact but with no attribution or reference.

JimT
  • 763
  • 3
  • 11