Problems & Puzzles: Puzzles

Puzzle 72.- Persistent Palprimes

Patrick De Geest  in his always-interesting pages  asked for the primality condition of a palprime after a digit d (from 0 to 9) is inserted between its adjacent digits.

De Geest found that:

 "13331 is the smallest palprime with the following property: Inserting any digit d between adjacent digits of this palprime never produces a new prime !".

Later he also found that 131 remains prime 6 times out of 10:

10301 = prime
11311 = prime
12321 = 3 x 3 x 37 x 37
13331 = prime
14341 = prime
15351 = 3 x 7 x 17 x 43
16361 = prime
17371 = 29 x 599
18381 = 3 x 11 x 557
19391 = prime

I have found that 7762868682677 remains prime 7 times out of 10 (for d = 0, 2,  4, 5, 6, 7, 8)

Here is the latest state of affairs (24/10/99) concerning the smallest existing  Persistent Palprimes for the following eleven possible cases :

     0 out of 10 = 13331
     1 out of 10 = 101
     2 out of 10 = 383
     3 out of 10 = 151
     4 out of 10 = 11311
     5 out of 10 = 353
     6 out of 10 = 131
     7 out of 10 = 7762868682677
     8 out of 10 = ?
     9 out of 10 = ?
     10 out of 10 = ?

With Patrick's kind permission I can now bring his puzzle to you through
these PP&P-pages and added the following extra questions :

1.- Is it theoretically possible that a palprime - modified according to the above prescribed insertion rule - remains prime 8, 9 or 10 times out of 10?

2.-Can you find better-ranked palprimes than  7762868682677 for the 7 out of 10 or is this the smallest possible palprime?

3.-Can you find the smallest palprime for the remaining cases '8 out of 10', '9 out of 10' and '10 out of 10'.

4.- Can you redo the exercise but this time with 'composites' and 'primes' instead of only 'palprimes' ?

---

Felice Russo sent (26/11/99) his results for the item 4. of this puzzle:

"For prime numbers I found:

 n                  #p
--------------------
439               0
 101              1
 31                2
 29                3
 53                4
 11                5
 17                6
 1933            7
 1411789     8

where n is the smallest persistent prime number and #p the number of primes generated. No solution for #p=9 and 10 up to 78*10^6.

For composite numbers instead I obtained:

  n        #p
--------------
121        0
 111       1
 69         2
 27         3
 33         4
 21         5
 49         6
 1513     7
 5809     8

and no solution for #p=9 and 10 up to 8.2*10^6."
***
Felice Russo (20/12/99) "Item 2.  No solution for rank 7/10 has been found up to 10^11." Later (10/1/2000) he added: "The palprime 7762868682677 is the smallest one for the rank 7/10."

***

On March 2011, Giovanni Resta wrote:

I studied puzzle 72 a little. These are my findings:

Question Q3 (palprimes)
the smallest prime palindrome which produces 8 out of 10
primes is 7792235971795322977

(This was not asked, but the smallest palindrome
composite for 7/10 is 1190906090911 and
for 8/10 is 9605826109016285069).

If there are palindromes (prime or composite)
which produces 9 or 10 primes, they must have
at least 25 digits.

Question Q4 (non palindromes)
For non palindromes we have,

for composites:
9:  1048435661
10: 7691546233

and for primes:
9:  1485444967
10: 1003229774283941

This last value it is also the missing
value for the solution of Puzzle 557 (Q1).

This last finding was a lucky one, since it is quite
at the beginning of the set of numbers with 16 digits.
I examined all the numbers up to 13 digits in
3 or 4 days thanks to a little modular trick
that let me speed up the search about 100 times.
And it is easy to see that there can not be
solutions with 10/10 for numbers with 14 or 15 digits, so
the next step was to search 16-digit numbers.

***