Friday 17 May 2013

Knockout Primes, And a new Notation




May 17 was the 137th day of the year, and as usual on my "On This Day in Math" post I added a note that "The 137th day of the year; 137 is the sum of the squares of the first seven digits of pi, 32+ 12 + 42 + 12 + 52 + 92 + 22 = 137."   (Plus a bit more)

When I posted a tweet of the above, I got a note from jignesh rathod@engineer_rathod to inform me that 137 was also unique in that if you drop any one of the digits, the remaining digits form a prime.  I pushed this to the point that if we allow the old-fashioned idea that 1 was a prime then 137 was a prime number which would still be prime if any number was eliminated, and each digit is prime (2nd thoughts about this, more later) .  In fact, when any digit is removed, the remaining digits may be placed in any order and would still be prime. (take out 3 and we have 17 and 71).  

I wrote and asked if the idea had a name and there seemed to be no formal (or much of an informal) consences .  I had thought of ultra-prime right off the bat, but then I got a note from Chris Maslanka to suggest the idea of a Knockout Prime, and I knew I had found the term I wanted.  
There was still a problem about how to distinguish special cases.  Was one acceptable as a prime, what about those that were reversible.  

My next epipheny came in a tweet from @mathematicsprof who suggested the notation  C(3,3) is Combination Prime for the fact that the original 3-digit number (137) was prime, and C(3,2) is combination Prime for if all two digit pairs were prime ( 13, 17, 37)  .  Note that order is preserved in this notation, but we could easily add a notation if each (all) of these primes were permutable primes (as they are in this case since 31, 71 and 73 are all primes) then we could call 137 a permutable C(3,2) prime and a permutable C(3,3) Prime. 

I worried about using the C(m,n) notation when it might be confused with the use in combinations, so I decided to use CP(m,n) for Combination Prime... then I changed my mind again and decided to use Chris' name as part of the symbol and opted for KP(m,n)  as in Knockout Prime.  

So 137 is KP(3,3) and KP(3,2) but not KP(3,1)  (using the modern approach that 1 is not considered prime).    Eliminating one may well mean that there exists no KP(3,1) numbers as conjectured by the Math Prof.  Suddently it hit me, a lesser symbol for those allowing 1 as prime, Kp(3,1) .  So 137 is Kp(3,1) but not KP(3,1).  

I toyed with a symbol to differentiate 23 and 37 since both are KP(2,2) but 23 is not a prime when reversed and 37 is.  I decided to settle for just using reversible KP(2,2).  So a number like 137 would be permutable KP (3,2) and permutable  KP(3,3) since any two digits (three) remaining are KP in any order. If they are only prime both when reversed, they could be called reversible.

I haven't taken the time to do a computer search of all the 2,3,4 digit numbers to see how they qualify.  If anybody jumps on that before I get to it, send me a copy.  

I expect I will update this page as better ideas are contributed by others.  Thanks for comments 

I have examined the three digit primes by hand (and thus much prone to error) and believe the following are all KP(3,2):  113, 131, 137, 173, 179, 197, 311, 317, 431, 617, and 719.   Note that ALL of these have a 1 in them, so none of them are KP(3,1), but several are Kp(3,1).  None of the numbers composed of all prime digits, such as 223, 277, or 523  formed KP(3,2) numbers, mostly because of repeating digits.  Thus there are no three digit primes which are "Ultra-primes" KP(3, n) .  
Not sure I'm up to attacking the four digit numbers for a while.  Sounds like a job for a good programmer.

  "Anyone? Anyone? Bueller."

Derek Orr suggested the name Steong Prime with the symbol SP(m,n) for m digit primes in which any set of n digits is prime under any order. I prefer to stick with the notation Permutable Prime since it is already a well recognized term, created by H.-E. Richert, about 40 years ago, and use the symbol PP(m,n). So 113 would be PP(3,3) and PP(3,2) but not PP(3,1) (we might still allow the notation Pp(3,1) for unit digits accepted as primes. The OEIS lists the following PP(3,3) numbers 113, 131, 199, 311, 337, 373, 733, 919, 991 Note however that only 113, 131, and 311 are PP(3,2). The OEIS also points out that there are no numbers of 4,5,or 6 digits which are PP(n,n). Beyond six digits it seems that only repunits appear, such as 1111111111111111111. I have not tried to search out the possibility that there may be PP(4,3) or PP(4,2) numbers, but I think they will be very rare; any number with an even digit, a five digit, or double digits other than 1 will necessarily fail for PP(4,2) and I quickly scanned all the four digit primes less than 5000 and rejected them (certainly possible oversights, it was late and I can be careless).

While doing research about the idea of knockout primes I came across the term "deletable prime" at the Prime Curios web page by some folks just down the road at Un Tenn Martin(a JOY to wander around in): a deletable prime has been defined ([Caldwell87]) to be a prime that you can delete the digits one at a time in some order and get a prime at each step. One example is 410256793, because the following are (deletable) primes:

410256793
41256793
4125673
415673
45673
4567
467
67
7

It is conjectured that there are infinitely many of these primes (and this may be one of the easiest conjectures in this glossary to prove!)
That last statement hung me up. Why is that so easy to prove?

Tim Cieplowski took this idea well beyond what I had explored and determined the total number of KP(n,k) numbers there were.  Here is the table he created:
He has some additional results from his explorations posted here.  Thanks Tim.


Tim just sent me one more note about knockout prime. The number 3355522333 is another in more than one category; it remains prime after removing any one digit or removing all but one digit, the only such prime less than ten billion.

4 comments:

timteachesmath said...

Cute problem. We could be more specific and consider a number like 1973 or be more general. Theorem 1 here might suggest a strategy for me.

timteachesmath said...
This comment has been removed by the author.
timteachesmath said...

For n<7, h,k < n, KP(n, h) is disjoint from KP(n, k) except for the number 111731.


3137, 10733, 73331, and 733331 contain the most primes for their respective number of digits.


For n>4, KP(n,3) is empty. For 2 < k < n-1, I conjecture KP(n, k) is empty.

timteachesmath said...

KP(n, 1) is A019546. KP(n, 2) is now A226108. KP(n, n-1) is A051362. Here are some musings.