Problems & Puzzles: Puzzles

Puzzle 131.  Growing primes

For sure you know the primes 73939133 and 357686312646216567629137. They are respectively the largest right-truncatable and the largest left-truncatable primes. 

These primes are the matter of two articles (1, 2) of the well known glossary prime pages of Chris Caldwell, and was also part of the matter of an old puzzle in my pages.

Let's concentrate by the moment in the right-truncatable record prime. 73939133 is a prime & the largest ever possible prime such that all of the substrings of the original prime are also prime numbers

73939133
7393913
739391
73939
7393
739
73
7

In the original definition you choose an initial prime that remains prime after cutting one digit at a time "by the right" until you reach to a one-digit prime.

But you can view this process upside down: 73939133 is the largest prime that can be constructed over an initial one-digit prime adding one digit by the right producing in every step of the process only prime numbers

7
73
739
7393
73939
739391
7393913
73939133

From this point of view you can see this sequences as a sequence of "growing primes" (by the right). This is the point of view of a puzzle posted by Frank Rubin in his always interesting contest pages (The Contest Center).

But this point of view permits to start not from a one-digit primes (that is to say 2, 3, 5 or 7) but you can start with any prime number.

For example: the prime 43 is the smallest prime that can grow 5 times:

43
439
4391
43913
439133
4391339

From this point of view 73939133 is no more a limit to the growth and you may have a sequence of more than 8 growing primes 

As a matter of fact Rubin makes the following puzzling statements about this kind of objects:

1) "no matter what prime you start with and what digits you append each such sequence always ends. That is, there comes a point where there is no digit that can be appended to form another prime."

2) "Conversely ... that for any N there is always a sequence of N such primes [starting with a proper prime]"

Questions:

1) Can you prove the two Rubin's statements about the growing primes by the right?

2) Can you extend the following table

3) Remain the validity of the Rubin's statements for "growing primes" by the left?

4) Construct the corresponding Table for the growing primes by the left.

Solution

***

Later ( 25/3/01) he added: I get this for part 4:

***

On April 13, 2007 J. K. Andersen wrote:

2)
K   Least initial  Largest growing (by the
    prime          right) prime
--  -------------  -----------------------
12  2744903797     2744903797:739993993333
13  5232781111     5232781111:9399399313393
14  133028062963   133028062963:79339933399333

4)
K  Least  Largest growing (by the left) prime
   prime
-- -----  ------------------------------------
0   2     :2
1   1303  9:1303
2   757   67:757
3   379   576:379
4   1049  6798:1049
5   139   84954:139
6   1061  939135:1061
7   383   7213272:383
8   359   96212633:359
9   109   997843951:109
10  223   9993243381:223
11  107   69213573395:107
12  227   976263648789:227
13  23    8372669942975:23
14  43    69334276539184:43
15  31    153994591539733:31
16  13    1986153454518136:13
17  11    48616876513572342:11
18  29    991273987576686678:29
19  3     3648495721353667688:3
20  19    98633312193846876837:19
21  59    787383153426187623456:59
22  37    3576863126462165676291:37
23  7     35768631264621656762913:7
24  76922083307  968429465126331891833378:76922083307

If the least prime can grow to more than one prime of the same length, then 
the largest of those primes is listed. Jud McCranie listed a smaller prime of 
the same length for K = 4, 5, 7, 9, 10, 12.

The solutions for K=22 and K=23 grow to the largest left-truncatable prime.
It was first computed at least 30 years ago:
http://links.jstor.org/sici?sici=0025-5718%28197701%2931%3A137%3C265%3AOTP%3E2
"On Truncatable Primes" by I. O. Angell and H. J. Godwin,
Mathematics of Computation, Vol. 31, No. 137 (Jan., 1977), pp. 265-267

The solution for K=24 is the only 11-digit prime which can grow 24 times,
so 96842946512633189183337876922083307 is the smallest (and only known) prime 
which can be truncated more times than the largest left-truncatable prime.

"...what can you say about the Rubin's statement?:"

Based on common heuristics I guess that Rubin is right, and that the same
applies to growing to the left. I have no proofs. I don't think anybody
today can prove that there is no upper limit to how long primes can grow.
It may be easier to prove that no prime can grow forever.

 

***