Problems & Puzzles: Puzzles

Puzzle 1007. Self inserted primes Carlos Rivera recently posed the sequence A335271 devoted to the "Full auto-insertable primes" defined as  "such primes that remain prime after all the possible internal auto-insertions, one at a time".   Rivera discovered the first 23 examples of these primes: 131, 173, 179, 191, 197, 283, 293, 367, 383, 401, 547, 587, 641, 701, 709, 757, 797, 827, 12197, 12289, 53881, 54779, 68927   The prime 131 can be inserted into itself in two positions: 1'131'31, 13'131'1. Both are primes. The prime 68927 can be inserted into itself in four positions: 6'68927'8927, 68'68927'927, 689'68927'27, 6892'68927'7. All the four are primes. No more prime of these were found less that 2^32. So he suspects that there are not any more, but without proof, just as an empirical guess.   Q1. Can you try to find some more primes for the sequence A335271?   If we just try to list the "champions" of these primes, full or not full, just for the quantity n of primes obtained, this is the list that Rivera has obtained:   n smallest P Primes obtained 1 109 (1/2) 110909 2 131, full (2/2) 113131, 131311 3 10289 (3/4) 1102890289, 1010289289, 1028102899 4 12197, full (4/4) 1121972197, 1212197197, 1211219797, 1219121977 5 1227797 (5/6) 11227797227797, 12122779727797, 12212277977797, 12271227797797, 12277912277977 6 101636629 (6/8) 110163662901636629, 101610163662936629, 101631016366296629, 101636101636629629, 101636610163662929, 101636621016366299 7 118561139 (7/8) 111856113918561139, 118118561139561139, 118511856113961139, 118561185611391139, 118561118561139139, 118561111856113939, 118561131185611399 Q2. Would you like to extend that table?

---

During the week 4-10, July, 2020, contributions came from Oscar Volpatti, Jan van Delden, Fausto Morales.

***

Oscar wrote:

a) The smallest champion for n = 8 is the prime P = 10596073217, with rate 8/10.

 

prime 1: 1059607321105960732177;

prime 2: 1059607321059607321717;

prime 3: 1059607310596073217217;

prime 4: 1059607105960732173217;

prime 5: 1059610596073217073217;

prime 6: 1059105960732176073217;

prime 7: 1051059607321796073217;

prime 8: 1105960732170596073217;

 

composite 1: 1059601059607321773217 = 13 *17 *113114671*42386852987;
 

composite 2: 1010596073217596073217 = 257*719*5469096579325999.
 

b) The prime P = 37898818253 can be inserted into itself in ten positions, obtaining ten primes:

 

3789881825378988182533;

3789881823789881825353;

3789881837898818253253;

3789881378988182538253;

3789883789881825318253;

3789837898818253818253;

3789378988182538818253;

3783789881825398818253;

3737898818253898818253;

3378988182537898818253.

 

The prime P = 37898818253 is also the smallest champion for n = 9 and for n = 10.

And due that it is a "full", it is also the 24th term of sequence A335271

***

Jan wrote:

I found 37898818253 (10/10) and 1032498666109 (10/12), but my routine didn’t finish 13 digits yet. The other results are as given in the table.
 

I only investigated primes having an odd number of digits. Primes having [math]2n[/math] digits are divisible by [math]11[/math] if one inserts at every other position and are divisible by [math]10^n+1[/math] and have therefore less potential.

 

...

 

Later, on July 16, 2020, he added:

 

The prime 6152275637107 (11/12) is the best possible for 13 digits.

The number 66152275637107152275637107 is not prime.

 

***

Fausto wrote:

Q1

Primes with a even number of digits d = 2*n should be excluded from search for solutions with a full set of prime self-insertions, as the central insertion always produces an integer with string duplications on both (left and right) halves, which makes the resulting number automatically divisible by 10^(d/2) + 1

For instance, the next prime up, beyond the range of search reported, 2^32  + 15, gives upon central self-insertion:

 

42949'4294967311'67311 =
 

11 * 9091 * 12299129 * 34920359 and
 

11 * 9091 = 100001

So, any new solutions can only be greater than 10^10.

My general impression, based on this constraint just described, the Prime Number Theorem, and a couple "reasonable" heuristic assumptions, is that existence of any further solutions to Q1 is quite unlikely.

***