View source for Minimal prime (recreational mathematics)

{{pp-semi-indef|small=yes}}
In recreational [[Number theory|number theory]], a '''minimal prime''' is a [[Prime number|prime number]] for which there is no shorter [[Subsequence|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 (number)|11]], [[19 (number)|19]], [[41 (number)|41]], [[61 (number)|61]], [[89 (number)|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 number|composite number]]s 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<br/>minimal primes<br/>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,<ref>This value is only conjectured. For base 17, there are 1279 known minimal (probable) primes and one unsolved family: F1{9}</ref> 50, 3463,<ref>This value is only conjectured. For base 19, there are 3462 known minimal (probable) primes and one unsolved family: EE1{6}</ref> 651, 2601,<ref>This value is only conjectured. For base 21, there are 2600 known minimal (probable) primes and one unsolved family: G{0}FK</ref> 1242, 6021, 306, (17608 or 17609),<ref>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</ref> 5664,<ref>This value is only conjectured. For base 26, there are 5662 known minimal (probable) primes and two unsolved families: {A}6F and {I}GL</ref> 17215,<ref>This value is only conjectured. For base 27, there are 17210 known minimal (probable) primes and five unsolved families</ref> 5784,<ref>This value is only conjectured. For base 28, there are 5783 known minimal (probable) primes and one unsolved family: O{A}F</ref> (57296 or 57297),<ref>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</ref> 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/>

==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.&nbsp;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]

{{Prime number classes}}

[[Category:Classes of prime numbers]]
[[Category:Base-dependent integer sequences]]



{{Sourceattribution|Minimal prime (recreational mathematics)}}