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

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

 Growing primes by the right The least prime for K growing steps K Least initial prime Largest growing (by the right) prime 0 53 53 1 11 113 2 97 9719 3 17 17333 4 71 719333 5 43 4391339 6 13 13999133 7 2 29399999 8 19 1979339339 9 103 103997939939 10 409 4099339193933 11 1457011 145701173999399393 12 ? ? 13 ? ? 14 ? ? 15 ? ?

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

Jud McCranie comments (24/3/01): "It is easy to see that at most one of the digit of 1 and 7 can be added. Except for possibly one 1 or one 7, the rest of the digits added to the right must be 3 or 9"

***

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

 Growing primes by the left The least prime for K growing steps K Least prime Largest growing (by the left) prime 0 2 2 1 1303 91303 2 757 67757 3 379 576379 4 1049 43681049 5 139 69354139 6 1061 9391351061 7 383 3213272383 8 359 96212633359 9 109 933843951109 10 223 3695133381223 11 107 69213573395107 12 227 959349938789227 13 23 837266994297523 14 43 6933427653918443 15 16 17

***

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

***

 Records   |  Conjectures  |  Problems  |  Puzzles