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
- last digit '9'
- last digits '97'
- first digit '4'
- first digit '6'
- some digit a '3'
- some digit a '7'
- first digit '4' and some digit a '3'
- first digit '4' and some digit a '7'
- first digit '6' and some digit a '7'
- one '3' and one '7'
- one '3' and one '7' with first digit '4'
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 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
Tim Cieplowski, May 27, 2013.