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 PS that can be transformed to each one of the first K primes - one at the time - of the minimal set S obtained by Shallit.


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) 4k-1
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



Table of results for question 1:

K Minimal prime PS Author
1 2 CR
2 23 CR
3 523 CR
4 2357 CR
5 112573 CR
6 1123597 CR
7 12341579 CR
26 (Hint: less than 23 digits)
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^633-507.
In the 4k-1 case, the range of the 138 members is even wider: from the 1 digit prime 3 to the 19153 digit (probable) prime 2*(10^19153-1)/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 2000-3000 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 4k-1 list consists of just 3 ;)





Records   |  Conjectures  |  Problems  |  Puzzles