Problems & Puzzles:
Puzzles
Puzzle 178. Shallit
Minimal Primes Set
Believe it or not the
following set S of 26 primes:
S
= {2,3,5,7,11,19,41,61,89,409,449,499,881,991,6469,6949,9001,9049,
9649,9949,60649,666649,946669,60000049,66000049,66600049}*
has the following very nice &
interesting property:
Any
prime or is
already a member of S
or it can
be transformed to at
least one of these 26 primes in S,
by the simple and only procedure of
eliminating one or several digits.
This was formally and completely
proved by Jeffrey Shallit. See the proof here.
See also this
page.
Example:
the prime 1031 can be transformed to the prime 3 (eliminating
the digits 1,0 & 1) or to the prime 11
(eliminating the digits 0 & 3).
Example: The prime 911 can not be transformed to
the prime 19, just to the prime 11.
1. Find the
minimal prime P_{S}
that can be transformed to each one of the first K primes  one at the
time  of the minimal set S
obtained by Shallit.
Example:
The prime 12341579 is
the minimal prime that can be reduced to each of the first seven (K=7)
primes in S (See below the table of
the first results)
2.
Find the corresponding minimal set of primes S
if
the universe of primes is restricted to the following types of primes:
a) 4k+1
b) 4k1
c) palindromic primes.
_____________
* While Shallit
obtained that set by a complete logical analysis of the string possibilities
of the universe of the primes, we can produce them by a recursive
procedure  that for sure you'll imagine very soon. But using this last
approach you can never know when you have finished the generation of the minimal set of primes.
As a matter of fact, I asked to Shallit
for a halt rule to the recursive procedure.
Two minutes later he answered:
CR: Do you think that exists a rule like
that?
JS: Almost certainly not. You can probably
show the problem is recursively unsolvable
Solution:
Table of results for question 1:
K 
Minimal prime P_{S} 
Author 
1 
2 
CR 
2 
23 
CR 
3 
523 
CR 
4 
2357 
CR 
5 
112573 
CR 
6 
1123597 
CR 
7 
12341579 
CR 
8 


9 


10 


11 


12 


13 


14 


15 


16 


17 


18 


19 


20 


21 


22 


23 


24 


25 


26 
(Hint:
less than 23 digits)
1235607889460606009419 
CR
Andrew Rupinski 
***
Andrew Rupinski also got the
solution for K=26:
The solution for K=26 is 1235607889460606009419. I have not worked out
solutions for smaller K.
This is actually the solution to the more general question of what is
the smallest prime transformable to all minimal primes in a given base b.
I have solved this general problem for nearly all b = 2 to 10, the only
exceptions being b=8 and b=9 for which I have not spent time trying to
compute the answer yet. I do have the minimal prime sets for all b<11.
For b=11 I started computing the set, but already it contains over 60
members and my complete analysis is far from complete.
If anyone is interested, they may want to compute the least prime
transformable to all minimal primes base b for b<10.
If you like, I can provide the details of my partial solution to Puzzle
178.
***
Andrew Rupinsik wrote the
following solution
for question 4a., on 18/4/06. His own comments are:
I have what I believe to be complete solutions to
problems 2a and 2b of puzzle 178. The requisite lists of primes are
attached.
The 173 primes in the set of minimal 4k+1 primes range
from the 1 digit prime 5 to the 633 digit (probable) prime 10^633507.
In the 4k1 case, the range of the 138 members is even
wider: from the 1 digit prime 3 to the 19153 digit (probable) prime
2*(10^191531)/9+77.
When I first began computing, it seemed like it would be
a daunting task to compute these sets, but as I went along, I got a lot
of small primes which helped reduce the number of calculations of larger
primes. Overall I probably tested around 20003000 numbers (with as many
as 180 cases for particular digit combinations), then compared the
resulting primes to weed out the minimal members. I believe all the
listed primes are pairwise incomparable in the two lists, although I may
have missed a few so these lists might have one or two elements that
shouldn't still be there. Conversely, I think that I considered all the
cases accurately, although in some digit combinations there were so many
numbers to check that I might have overlooked a small subset. Overall,
these lists ought to be 99.9% accurate. If anyone is crazy enough to
want to check the work, I have left the numbers roughly in the order I
considered them so someone could theoretically follow the cases through
in the order I did.
After doing all this work, I realized that I could have
made the work a lot easier if I had worked in base 2 in which case the
4k+1 list consists of just 5 and the 4k1 list consists of just 3 ;)
***
