Minimal prime (recreational mathematics)
In recreational number theory, a minimal prime is a prime number for which there is no shorter subsequence of its digits in a given base that form a prime. In base 10 there are exactly 26 minimal primes:
- 2, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 499, 881, 991, 6469, 6949, 9001, 9049, 9649, 9949, 60649, 666649, 946669, 60000049, 66000049, 66600049 (sequence A071062 in the OEIS).
For example, 409 is a minimal prime because there is no prime among the shorter subsequences of the digits: 4, 0, 9, 40, 49, 09. The subsequence does not have to consist of consecutive digits, so 109 is not a minimal prime (because 19 is prime). But it does have to be in the same order; so, for example, 991 is still a minimal prime even though a subset of the digits can form the shorter prime 19 by changing the order.
Similarly, there are exactly 32 composite numbers which have no shorter composite subsequence:
- 4, 6, 8, 9, 10, 12, 15, 20, 21, 22, 25, 27, 30, 32, 33, 35, 50, 51, 52, 55, 57, 70, 72, 75, 77, 111, 117, 171, 371, 711, 713, 731 (sequence A071070 in the OEIS).
There are 146 primes congruent to 1 mod 4 which have no shorter prime congruent to 1 mod 4 subsequence:
- 5, 13, 17, 29, 37, 41, 61, 73, 89, 97, 101, 109, 149, 181, 233, 277, 281, 349, 409, 433, 449, 677, 701, 709, 769, 821, 877, 881, 1669, 2221, 3001, 3121, 3169, 3221, 3301, 3833, 4969, 4993, 6469, 6833, 6949, 7121, 7477, 7949, 9001, 9049, 9221, 9649, 9833, 9901, 9949, ... (sequence A111055 in the OEIS)
There are 113 primes congruent to 3 mod 4 which have no shorter prime congruent to 3 mod 4 subsequence:
- 3, 7, 11, 19, 59, 251, 491, 499, 691, 991, 2099, 2699, 2999, 4051, 4451, 4651, 5051, 5651, 5851, 6299, 6451, 6551, 6899, 8291, 8699, 8951, 8999, 9551, 9851, ... (sequence A111056 in the OEIS)
Other bases[edit]
Minimal primes can be generalized to other bases. It can be shown that there are only a finite number of minimal primes in every base.
b | minimal primes in base b (written in base b, the letters A, B, C, ... represent values 10, 11, 12, ...) | |
---|---|---|
1 | 11 | 1 |
2 | 10, 11 | 2 |
3 | 2, 10, 111 | 3 |
4 | 2, 3, 11 | 3 |
5 | 2, 3, 10, 111, 401, 414, 14444, 44441 | 8 |
6 | 2, 3, 5, 11, 4401, 4441, 40041 | 7 |
7 | 2, 3, 5, 10, 14, 16, 41, 61, 11111 | 9 |
8 | 2, 3, 5, 7, 111, 141, 161, 401, 661, 4611, 6101, 6441, 60411, 444641, 444444441 | 15 |
9 | 2, 3, 5, 7, 14, 18, 41, 81, 601, 661, 1011, 1101 | 12 |
10 | 2, 3, 5, 7, 11, 19, 41, 61, 89, 409, 449, 499, 881, 991, 6469, 6949, 9001, 9049, 9649, 9949, 60649, 666649, 946669, 60000049, 66000049, 66600049 | 26 |
11 | 2, 3, 5, 7, 10, 16, 18, 49, 61, 81, 89, 94, 98, 9A, 199, 1AA, 414, 919, A1A, AA1, 11A9, 66A9, A119, A911, AAA9, 11144, 11191, 1141A, 114A1, 1411A, 144A4, 14A11, 1A114, 1A411, 4041A, 40441, 404A1, 4111A, 411A1, 44401, 444A1, 44A01, 6A609, 6A669, 6A696, 6A906, 6A966, 90901, 99111, A0111, A0669, A0966, A0999, A0A09, A4401, A6096, A6966, A6999, A9091, A9699, A9969, 401A11, 404001, 404111, 440A41, 4A0401, 4A4041, 60A069, 6A0096, 6A0A96, 6A9099, 6A9909, 909991, 999901, A00009, A60609, A66069, A66906, A69006, A90099, A90996, A96006, A96666, 111114A, 1111A14, 1111A41, 1144441, 14A4444, 1A44444, 4000111, 4011111, 41A1111, 4411111, 444441A, 4A11111, 4A40001, 6000A69, 6000A96, 6A00069, 9900991, 9990091, A000696, A000991, A006906, A040041, A141111, A600A69, A906606, A909009, A990009, 40A00041, 60A99999, 99000001, A0004041, A9909006, A9990006, A9990606, A9999966, 40000A401, 44A444441, 900000091, A00990001, A44444111, A66666669, A90000606, A99999006, A99999099, 600000A999, A000144444, A900000066, A0000000001, A0014444444, 40000000A0041, A000000014444, A044444444441, A144444444411, 40000000000401, A0000044444441, A00000000444441, 11111111111111111, 14444444444441111, 44444444444444111, A1444444444444444, A9999999999999996, 1444444444444444444, 4000000000000000A041, A999999999999999999999, A44444444444444444444444441, 40000000000000000000000000041, 440000000000000000000000000001, 999999999999999999999999999999991, 444444444444444444444444444444444444444444441 | 152 |
12 | 2, 3, 5, 7, B, 11, 61, 81, 91, 401, A41, 4441, A0A1, AAAA1, 44AAA1, AAA0001, AA000001 | 17 |
The base 12 minimal primes written in base 10 are listed in A110600.
Number of minimal (probable) primes in base n are
- 1, 2, 3, 3, 8, 7, 9, 15, 12, 26, 152, 17, 228, 240, 100, 483, 1280,^{[1]} 50, 3463,^{[2]} 651, 2601,^{[3]} 1242, 6021, 306, (17608 or 17609),^{[4]} 5664,^{[5]} 17215,^{[6]} 5784,^{[7]} (57296 or 57297),^{[8]} 220, ...
The length of the largest minimal (probable) prime in base n are
- 2, 2, 3, 2, 5, 5, 5, 9, 4, 8, 45, 8, 32021, 86, 107, 3545, (≥111334), 33, (≥110986), 449, (≥479150), 764, 800874, 100, (≥136967), (≥8773), (≥109006), (≥94538), (≥174240), 1024, ...
Largest minimal (probable) prime in base n (written in base 10) are
- 2, 3, 13, 5, 3121, 5209, 2801, 76695841, 811, 66600049, 29156193474041220857161146715104735751776055777, 388177921, ... (next term has 35670 digits)
Number of minimal composites in base n are
- 1, 3, 4, 9, 10, 19, 18, 26, 28, 32, 32, 46, 43, 52, 54, 60, 60, 95, 77, 87, 90, 94, 97, 137, 117, 111, 115, 131, 123, 207, ...
The length of the largest minimal composite in base n are
- 4, 4, 3, 3, 3, 4, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 3, 4, 3, 3, 2, 3, 3, 4, 2, 3, 2, 3, 3, 4, ...
Notes[edit]
- ^ This value is only conjectured. For base 17, there are 1279 known minimal (probable) primes and one unsolved family: F1{9}
- ^ This value is only conjectured. For base 19, there are 3462 known minimal (probable) primes and one unsolved family: EE1{6}
- ^ This value is only conjectured. For base 21, there are 2600 known minimal (probable) primes and one unsolved family: G{0}FK
- ^ This value is only conjectured. For base 25, there are 17597 known minimal (probable) primes and twelve unsolved families, but the smallest prime of one of these families (LO{L}8) may or may not be a minimal prime, since another unsolved family is O{L}8
- ^ This value is only conjectured. For base 26, there are 5662 known minimal (probable) primes and two unsolved families: {A}6F and {I}GL
- ^ This value is only conjectured. For base 27, there are 17210 known minimal (probable) primes and five unsolved families
- ^ This value is only conjectured. For base 28, there are 5783 known minimal (probable) primes and one unsolved family: O{A}F
- ^ This value is only conjectured. For base 29, there are 57283 known minimal (probable) primes and fourteen unsolved families, but the smallest prime of one of these families ({F}OPF) may or may not be a minimal prime, since another unsolved family is {F}OP
References[edit]
- Chris Caldwell, The Prime Glossary: minimal prime, from the Prime Pages
- A research of minimal primes in bases 2 to 30
- Minimal primes and unsolved families in bases 2 to 30
- Minimal primes and unsolved families in bases 28 to 50
- J. Shallit, Minimal primes, Journal of Recreational Mathematics, 30:2, pp. 113–117, 1999-2000.
- PRP records, search by form 8*13^n+183 (primes of the form 8{0}111 in base 13), n=32020
- PRP records, search by form (51*21^n-1243)/4 (primes of the form C{F}0K in base 21), n=479149
- PRP records, search by form (106*23^n-7)/11 (primes of the form 9{E} in base 23), n=800873
This number theory-related article is a stub. You can help Wikipedia by expanding it. |