Trapezoids

Knockout Primes

Knockout primes

Definition

This is another problem that came to me via Pat Ballew. He defines a knockout prime KP(n, k) as an n-digit prime number where you can remove any n - k digits and obtain a prime number. For example, 137 is KP(3, 2) because 13, 17, and 37 are all prime.

Frequency

How many knockout primes are there?

	choose 1	2	3	4	5	6	7	8	9
1 digit length	4
2	4	21
3	15	11	143
4	38	3	14	1061
5	128	20	0	16	8363
6	389	23	0	0	18	68906
7	1325	4	0	0	0	13	586081
8	4643	31	0	0	0	0	14	5096876
9	16623	27	0	0	0	0	0	18	45086079

. . .
The main diagonal is just the frequency of primes, A006879.

The subdiagonal counts 23, 37, 53, 73, 113 . . . which is A051362.*
The first column counts 2, 3, 5, 7, 23, 37, 53, 73, 223, . . . which is A019546.
The second column counts 11, 13, 17, . . . , 113, 131, 137, . . . which I proposed as A226108.

* Do we allow zeroes? If not, we might want A034302 in place of A051362, but if so, we might add numbers like 307, 503, 2003, and 2027 to A019546.

Producing A226108

This is my first integer sequence on OEIS! It's much faster to find primes among those with all pairs of digits prime than the other way around. Why? Well, consider all two-digit primes:

Digits:	1	3	7	9
10 X 1	1	3	7	9
2		3		9
3	1		7
4	1	3	7
5		3		9
6	1		7
7	1	3		9
8		3		9
9			7

By studying this table, some patterns emerge. For example, the digit '2' can only be followed by '3' or '9', but a second digit of '3' can only be followed by '1' and '7' without creating 33 or 35 and '1' creates '21', and second digit '9' can only be followed by '7', which would create 27, so any prime greater than 29 in A226108 doesn't begin with a '2'.
This leads to a list of rules, focusing our search for KP(n,2) to testing primality of 2n^2 +2n+3 numbers, much better than examining n - 1 knockouts on O(10^n / n ) primes. Here's my list:

A string of all ones except:
• well, just all ones
• first digit '4'
• first digit '4' and some digit a '3'
• first digit '4' and some digit a '7'
• first digit '4', some digit '3', and some digit '7'
• first digit '6'
• first digit '6' and some digit a '7'
• some digit a '3'
• some digit a '7'
• some digit '3' and some digit '7'
• last digit '9'
• some digit a '7' and last digit '9'
• last digits '97'
• and exceptions for 23, 29, 53, 59, 83, and 89.

Empty sets

Theorem: For n > 4, KP(n, 3) is empty.
Proof: Given five (or more) digits, we will show that some choice of three is divisible by 3. Consider the residue of each digit modulo 3. If there is a representative of each residue class, choose those three digits and the resulting three digit number is divisible by 3. Else, there are only 2 residue classes represented, so by the pigeonhole principle there are at least 3 of one class. The three digit number with 3 of those digits is divisible by 3.

Conjecture: For 2 < k < n-1, KP(n, k) is empty.

Observations

Up to 10 billion, sets are disjoint except 111,731, which is in KP(6,2) and KP(6,5); and 3,355,522,333, which is in KP(10,1) and KP(10,9).

There are some paths through sets. For example, you can remove any digit from 19973 and obtain another prime, but if you choose the last one, you can remove any digit from 1997 and obtain another prime, but if you choose a 9, you can remove any digit from 197 and obtain another prime. These are listed below. 

10192 -> 1013 -> 113 ->

10613 -> 1013 -> 113 ->

19973 -> 1997 -> 197 ->

37019 -> 7019 -> 719 ->

Most primes

A prime with n digits could contain at most 2^n-1 primes, but by the theorem in "Empty sets" above, it probably doesn't, and by the frequency table, rarely do we find a prime that contains all k-digit primes. Nevertheless, we still could wonder how many primes are contained.
On the low end, primes containing no primes via knockouts are called minimal primes. The derivation of this set is easy to follow.
Well then, which primes contain the most primes?

Smallest prime containing	m primes
13	1
23	2
103	3
113	4
137	5
1013	9
1373	11
3137	12
10037	19
10193	20
10313	21
10733	22
100019	23
100103	29
100193	38
100313	39
100733	40
100937	41
223339	42
500233	43
733331	45
1000033	48
1000037	70
1000397	72
1001933	75
1009937	77
3333311	83
7333331	89
10000079	117
10000139	119
10000379	143
50000233	154

Related sequences

• We could be more specific and allow permutations of digits, resulting in the primeval numbers.
• Or, we could require all possible permutations to be prime, resulting in the permutable primes.
• The deletable primes are more general, where you can traverse through primes by deleting some digit.
• Here, knockouts occur only from the left and right, which allows for more possible lengths.