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 |
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.
No comments:
Post a Comment