In der Unterhaltungsmathematik ist eine minimale Primzahl eine Primzahl ${\displaystyle p\in \mathbb {P} }$, bei der keine Teilfolge ihrer Ziffern in einer gegebenen Basis eine Primzahl ist, solange man sie nicht miteinander vertauscht.

Beispiele im Dezimalsystem

• Die Zahl ${\displaystyle 109}$ ist keine minimale Primzahl, weil man aus ihren Ziffern die Primzahl ${\displaystyle 19}$ machen kann. Die einzelnen Ziffern der Teilfolgen müssen also in der ursprünglichen Zahl nicht zusammenhängend sein.
• Aus der Zahl ${\displaystyle 409}$ kann man folgende Teilfolgen ihrer Ziffern machen: ${\displaystyle 0,4,9,09,40,49}$. Keine dieser Zahlen ist eine Primzahl, somit ist ${\displaystyle 409}$ eine minimale Primzahl.
• Die Zahl ${\displaystyle 991}$ ist eine minimale Primzahl, weil man aus ihren Ziffern nur die Zahlen ${\displaystyle 1,9,91}$ und ${\displaystyle 99}$ machen kann und keine dieser Zahlen prim ist. Die einzelnen Ziffern der ursprünglichen Zahl dürfen aber nicht vertauscht werden (sonst wäre in diesem Fall die Teilfolge ${\displaystyle 19}$ sehr wohl eine Primzahl).
• Die einzigen minimalen Primzahlen für die Basis 10 (also im Dezimalsystem) sind die folgenden 26 Primzahlen:

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 (Folge A071062 in OEIS)

Beispiele mit Basis b

• Es folgt eine Tabelle, der man minimale Primzahlen in der Basis ${\displaystyle b}$ entnehmen kann (wobei aus Ermangelung an weiteren Ziffern A=10 und B=11 gesetzt wird). Es kann gezeigt werden, dass es nicht mehr minimale Primzahlen zur jeweiligen Basis geben kann:^[1][2]

Basis ${\displaystyle b}$	minimale Primzahlen zur Basis ${\displaystyle b}$, geschrieben zur Basis ${\displaystyle b}$
2	10, 11
3	2, 10, 111
4	2, 3, 11
5	2, 3, 10, 111, 401, 414, 14444, 44441 (insgesamt 8 minimale Primzahlen)
6	2, 3, 5, 11, 4401, 4441, 40041 (insgesamt 7 minimale Primzahlen)
7	2, 3, 5, 10, 14, 16, 41, 61, 11111 (insgesamt 9 minimale Primzahlen)
8	2, 3, 5, 7, 111, 141, 161, 401, 661, 4611, 6101, 6441, 60411, 444641, 444444441 (insgesamt 15 minimale Primzahlen)
9	2, 3, 5, 7, 14, 18, 41, 81, 601, 661, 1011, 1101 (insgesamt 12 minimale Primzahlen)
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 (insgesamt 26 minimale Primzahlen)
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 (insgesamt 152 minimale Primzahlen)
12	2, 3, 5, 7, B, 11, 61, 81, 91, 401, A41, 4441, A0A1, AAAA1, 44AAA1, AAA0001, AA000001 (insgesamt 17 minimale Primzahlen)

• Die einzigen minimalen Primzahlen für die Basis 12 (also im Duodezimalsystem) sind die obigen 17 Primzahlen. Im Dezimalsystem sind es die folgenden:

2, 3, 5, 7, 11, 13, 73, 97, 109, 577, 1489, 7537, 17401, 226201, 1097113, 32555521, 388177921 (Folge A110600 in OEIS)

Beispiel:

Die minimale Primzahl ${\displaystyle A41_{12))$ ist im Dezimalsystem die Zahl ${\displaystyle {\underline {10))\cdot 12^{2}+{\underline {4))\cdot 12^{1}+{\underline {1))\cdot 12^{0}=1440+48+1=1489_{10))$. Aus ihr kann man die Nicht-Primzahlen ${\displaystyle 1_{12}=1_{10},4_{12}=4_{10},A_{12}=10_{10},41_{12}=49_{10},A1_{12}=121_{10))$ und ${\displaystyle A4_{12}=124_{10))$ machen.

• Die Anzahl der minimalen (zum Teil PRP-) Primzahlen bei gegebener Basis ${\displaystyle b=2,3,\ldots }$ sind die folgenden:^[3]

2, 3, 3, 8, 7, 9, 15, 12, 26, 152, 17, 228, 240, 100, 483, 1279~1280,^[4] 50, 3462~3463,^[5] 651, 2600~2601,^[6] 1242, 6021, 306, 17597~17609,^[7] 5662~5664,^[8] 17210~17215,^[9] 5783~5784,^[10] 57283~57297,^[11] 220, 79182~79206,^[12] 45205~45283,^[13] 57676~57709,^[14] 56457~56490,^[15] 182378~182393,^[16] 6296~6297,^[17] ...

Beispiel:

An der 14. Stelle obiger Liste steht die Zahl ${\displaystyle 240}$. Es gibt also ${\displaystyle 240}$ minimale Primzahlen zur Basis ${\displaystyle b=14}$.

• Die Stellenanzahl der größten minimalen (zum Teil PRP-) Primzahlen bei gegebener Basis ${\displaystyle b=2,3,\ldots }$ sind die folgenden:^[1][3]

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, ≥9896, ≥9750, ≥9961, ≥9377, ≥9599, ≥81995, ...

Beispiel 1:

An der 13. Stelle obiger Liste steht die Zahl ${\displaystyle 32021}$. Die größte minimale (PRP-)Primzahl zur Basis ${\displaystyle b=13}$ hat also ${\displaystyle 32021}$ Stellen.

Beispiel 2:

An der 26. Stelle obiger Liste steht der Eintrag ${\displaystyle \geq 8773}$. Die größte minimale (PRP-)Primzahl zur Basis ${\displaystyle b=26}$ hat also ${\displaystyle 8773}$ Stellen, es gibt aber noch ungelöste Fälle, die mehr Stellen haben.

• Die größten minimalen (zum Teil PRP-) Primzahlen bei gegebener Basis ${\displaystyle b=2,3,\ldots }$ sind die folgenden, wenn man sie im Dezimalsystem schreibt:

3, 13, 5, 3121, 5209, 2801, 76695841, 811, 66600049, 29156193474041220857161146715104735751776055777, 388177921, 13³²⁰²⁰×8+183, 105424857819287798806418819113233738918727566030978473259776662287591943095417282958456246916612161, 436635814641280043127962407363407208906111673434962498607709751248805460292422544779495998033626489944124062146459306989397233, 16³⁵⁴⁴×9+145, ≥(17¹¹¹³³³×73−9)/16, 249069897374447078426903207266791381270529, ≥(19¹¹⁰⁹⁸⁴×904−1)/3, (20⁴⁴⁹×16−2809)/19, ≥(21⁴⁷⁹¹⁴⁹×51−1243)/4, 22⁷⁶³×20+7041, (23⁸⁰⁰⁸⁷³×106−7)/11, 973767003942195520947294504280890002680537875404412883659428819153939518991719953852457999342229586282557076411687300474817686178175693329, ≥(25¹³⁶⁹⁶⁶×37+63)/4, ≥(26⁸⁷⁷³×22+53)/25, ≥27¹⁰⁹⁰⁰⁵×10+697, ≥(28⁹⁴⁵³⁶×6092−143)/9, ≥29¹⁷⁴²³⁹×24+13361, 30¹⁰²³×12+1, ≥(31⁹⁸⁹⁴×4187−5)/6, ≥(32⁹⁷⁴⁹×898−309)/31, ≥(33⁹⁹⁶¹×21+7723)/32, ≥34⁹³⁷⁵×1048+27, ≥(35⁹⁵⁹⁷×13456−9)/17, ≥(36⁸¹⁹⁹⁵×5+821)/7, ...

Beispiel:

An der 12. Stelle obiger Liste steht die Zahl ${\displaystyle 388177921}$. Tatsächlich ist die größte minimale Primzahl zur Basis ${\displaystyle 12}$ die Zahl ${\displaystyle AA000001_{12}={\underline {10))\cdot 12^{7}+{\underline {10))\cdot 12^{6}+{\underline {1))\cdot 12^{0}=388177921_{10))$.

Verallgemeinerungen

• Es gibt genau 32 zusammengesetzte Zahlen im Dezimalsystem, welche aus Ziffern bestehen, deren Teilfolgen keine weiteren zusammengesetzten Zahlen ergeben:

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 (Folge A071070 in OEIS)

Beispiel:

Aus der Zahl ${\displaystyle 731}$ kann man die Zahlen ${\displaystyle 1,3,7,31,71}$ und ${\displaystyle 73}$ machen, welche allesamt Primzahlen und somit nicht zusammengesetzt sind. Diese Zahlen sind somit das genaue Gegenteil der minimalen Primzahlen.

• Es gibt im Dezimalsystem genau 146 Primzahlen ${\displaystyle p\equiv 1{\pmod {4))}$ (also der Form ${\displaystyle p=4k+1}$ mit ${\displaystyle k\in \mathbb {N} }$), welche aus Ziffern bestehen, deren Teilfolgen im Dezimalsystem keine weiteren Primzahlen der Form ${\displaystyle p\equiv 1{\pmod {4))}$ ergeben:

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, ..., 8888888888888888888888888888888888888888888888888888888888888888888888888888833 (Folge A111055 in OEIS)

Beispiel:

Aus der Primzahl ${\displaystyle 3169}$ kann man die Zahlen ${\displaystyle 1,3,6,9,16,19,31,36,39,69,169,316,319}$ und ${\displaystyle 369}$ machen, welche allesamt keine Primzahlen der Form ${\displaystyle p\equiv 1{\pmod {4))}$ sind.

• Es gibt im Dezimalsystem genau 113 Primzahlen ${\displaystyle p\equiv 3{\pmod {4))}$ (also der Form ${\displaystyle p=4k+3}$ mit ${\displaystyle k\in \mathbb {N} }$), welche aus Ziffern bestehen, deren Teilfolgen im Dezimalsystem keine weiteren Primzahlen der Form ${\displaystyle p\equiv 3{\pmod {4))}$ ergeben:

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, 22091, 22291, 66851, 80051, 80651, 84551, 85451, 86851, 88651, 92899, 98299, 98899, ..., (10¹⁹¹⁵³×2+691)/9 (Folge A111056 in OEIS)

Beispiel:

Aus der Primzahl ${\displaystyle 4051}$ kann man die Zahlen ${\displaystyle 0,1,4,5,01,05,40,41,45,51,051,401,405}$ und ${\displaystyle 451}$ machen, welche allesamt keine Primzahlen der Form ${\displaystyle p\equiv 3{\pmod {4))}$ sind.

• Es gibt im Dezimalsystem genau 77 Primzahlen ${\displaystyle p>10}$, welche aus Ziffern bestehen, deren Teilfolgen im Dezimalsystem keine weiteren Primzahlen der Form ${\displaystyle p>10}$ ergeben:

11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 227, 251, 257, 277, 281, 349, 409, 449, 499, 521, 557, 577, 587, 727, 757, 787, 821, 827, 857, 877, 881, 887, 991, 2087, 2221, 5051, 5081, 5501, 5581, 5801, 5851, 6469, 6949, 8501, 9001, 9049, 9221, 9551, 9649, 9851, 9949, 20021, 20201, 50207, 60649, 80051, 666649, 946669, 5200007, 22000001, 60000049, 66000049, 66600049, 80555551, 555555555551, 5000000000000000000000000000027

Beispiel:

Aus der Primzahl ${\displaystyle 857}$ kann man die Zahlen ${\displaystyle 8,5,7,85,87,57}$ und ${\displaystyle 857}$ machen, welche allesamt keine Primzahlen der Form ${\displaystyle p>10}$ sind.

• Die Anzahl der minimalen zusammengesetzten Zahlen bei gegebener Basis ${\displaystyle b=2,3,\ldots }$ sind die folgenden:^[18]

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, 147, 160, 163, 201, 169, 216, ...

• Die Stellenanzahl der größten minimalen zusammengesetzten Zahlen bei gegebener Basis ${\displaystyle b=2,3,\ldots }$ sind die folgenden:^[18]

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, 3, 3, 2, 3, 2, 4, ...

• Die größten minimalen zusammengesetzten Zahlen bei gegebener Basis sind die folgenden, wenn man sie im Dezimalsystem schreibt:^[18]

15, 9, 21, 27, 475, 49, 477, 70, 731, 123, 8797, 169, 1529, 208, 2899, 291, 99491, 361, 5423, 418, 9275, 529, 30995, 598, 15645, 644, 18511, 843, 795037, 961, 23779, 1054, 34311, 1116, 56129, ...