Minimal prime (recreational mathematics)

{{for|the term in commutative algebra|Minimal prime (commutative algebra)}}

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 {{OEIS|id=A071062}}.

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 {{OEIS|id=A071070}}.

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, ... {{OEIS|id=A111055}}

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, ... {{OEIS|id=A111056}}

Other bases

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. Equivalently, every sufficiently large prime contains a shorter subsequence that forms a prime.

class="wikitable"

! b

! minimal primes in base b (written in base b, the letters A, B, C, ... represent values 10, 11, 12, ...)

! {{verth|nb=1|number of
minimal primes
in base b}}

style="text-align:right" | 1

| 11

| style="text-align:right" | 1

style="text-align:right" | 2

|10, 11

| style="text-align:right" | 2

style="text-align:right" | 3

|2, 10, 111

| style="text-align:right" | 3

style="text-align:right" | 4

|2, 3, 11

| style="text-align:right" | 3

style="text-align:right" | 5

|2, 3, 10, 111, 401, 414, 14444, 44441

| style="text-align:right" | 8

style="text-align:right" | 6

|2, 3, 5, 11, 4401, 4441, 40041

| style="text-align:right" | 7

style="text-align:right" | 7

|2, 3, 5, 10, 14, 16, 41, 61, 11111

| style="text-align:right" | 9

style="text-align:right" | 8

|2, 3, 5, 7, 111, 141, 161, 401, 661, 4611, 6101, 6441, 60411, 444641, 444444441

| style="text-align:right" | 15

style="text-align:right" | 9

|2, 3, 5, 7, 14, 18, 41, 81, 601, 661, 1011, 1101

| style="text-align:right" | 12

style="text-align:right" | 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

| style="text-align:right" | 26

style="text-align:right" | 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

| style="text-align:right" | 152

style="text-align:right" | 12

|2, 3, 5, 7, B, 11, 61, 81, 91, 401, A41, 4441, A0A1, AAAA1, 44AAA1, AAA0001, AA000001

| style="text-align:right" | 17

The base 12 minimal primes written in base 10 are listed in {{oeis|id=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,This value is only conjectured. For base 17, there are 1279 known minimal (probable) primes and one unsolved family: F1{9} 50, 3463,This value is only conjectured. For base 19, there are 3462 known minimal (probable) primes and one unsolved family: EE1{6} 651, 2601,This value is only conjectured. For base 21, there are 2600 known minimal (probable) primes and one unsolved family: G{0}FK 1242, 6021, 306, (17608 or 17609),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 5664,This value is only conjectured. For base 26, there are 5662 known minimal (probable) primes and two unsolved families: {A}6F and {I}GL 17215,This value is only conjectured. For base 27, there are 17210 known minimal (probable) primes and five unsolved families 5784,This value is only conjectured. For base 28, there are 5783 known minimal (probable) primes and one unsolved family: O{A}F (57296 or 57297),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 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) {{OEIS|id=A326609}}

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

References

Chris Caldwell, [http://primes.utm.edu/glossary/xpage/MinimalPrime.html The Prime Glossary: minimal prime], from the Prime Pages
[https://cs.uwaterloo.ca/~cbright/reports/mepn.pdf A research of minimal primes in bases 2 to 30]
[https://github.com/curtisbright/mepn-data/tree/master/data Minimal primes and unsolved families in bases 2 to 30]
[https://github.com/RaymondDevillers/primes Minimal primes and unsolved families in bases 28 to 50]
J. Shallit, [http://www.cs.uwaterloo.ca/~shallit/Papers/minimal5.ps Minimal primes], Journal of Recreational Mathematics, 30:2, pp. 113–117, 1999-2000.
[http://www.primenumbers.net/prptop/searchform.php?form=8*13%5En%2B183&action=Search PRP records, search by form 8*13^n+183 (primes of the form 8{0}111 in base 13), n=32020]
[http://www.primenumbers.net/prptop/searchform.php?form=%2851*21%5En-1243%29%2F4&action=Search PRP records, search by form (51*21^n-1243)/4 (primes of the form C{F}0K in base 21), n=479149]
[http://www.primenumbers.net/prptop/searchform.php?form=%28106*23%5En-7%29%2F11&action=Search PRP records, search by form (106*23^n-7)/11 (primes of the form 9{E} in base 23), n=800873]

Category:Classes of prime numbers

Category:Base-dependent integer sequences