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:

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

Through 100,000,000, sets are disjoint except 111,731, which is in KP(6,2) and KP(6,5).

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 \rightarrow 1013 \rightarrow 113 \rightarrow \\ 10613 \rightarrow 1013 \rightarrow 113 \rightarrow \\ 19973 \rightarrow 1997 \rightarrow 197 \rightarrow \\ 37019 \rightarrow 7019 \rightarrow 719 \rightarrow \\ $$

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 containingm primes
131
232
1033
1134
1375
10139
137311
313712
1003719
1019320
1031321
1073322
10001923
10010329
10019338
10031339
10073340
10093741
22333942
50023343
73333145
100003348
100003770
100039772
100193375
100993777
333331183
733333189
10000079117
10000139119
10000379143
50000233154


Related sequences




See another problem
or go home.

Tim Cieplowski, May 27, 2013.