Minimale Primzahl

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]

• 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.

• 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, ...

Siehe auch

• Trunkierbare Primzahl
• Permutierbare Primzahl
• Zirkulare Primzahl

Einzelnachweise

1. ↑ ^{a b} Minimale Primzahlen und ungelöste Fälle („Familien“) mit Basen von 2 bis 30 (englisch)
2. ↑ Minimal Elements for the Prime Numbers (englisch)
3. ↑ ^{a b} Curtis Bright, Raymond Devillers, Jeffrey Shallit: Minimal Elements for the Prime Numbers. University of Waterloo, 2015, S. 15, abgerufen am 4. Juli 2018. 
4. ↑ Für die Basis b=17 gibt es 1279 bekannte minimale (PRP-)Primzahlen und einen ungelösten Fall: F1{9}
5. ↑ Für die Basis b=19 gibt es 3462 bekannte minimale (PRP-)Primzahlen und einen ungelösten Fall: EE1{6}
6. ↑ Für die Basis b=21 gibt es 2600 bekannte minimale (PRP-)Primzahlen und einen ungelösten Fall: G{0}FK
7. ↑ Für die Basis b=25 gibt es 17597 bekannte minimale (PRP-)Primzahlen und 12 ungelöste Fälle
8. ↑ Für die Basis b=26 gibt es 5662 bekannte minimale Primzahlen und zwei ungelöste Fälle: {A}6F und {I}GL
9. ↑ Für die Basis b=27 gibt es 17210 bekannte minimale (PRP-)Primzahlen und 5 ungelöste Fälle
10. ↑ Für die Basis b=28 gibt es 5783 bekannte minimale (PRP-)Primzahlen und einen ungelösten Fall: O{A}F
11. ↑ Für die Basis b=29 gibt es 57283 bekannte minimale (PRP-)Primzahlen und 14 ungelöste Fälle
12. ↑ Für die Basis b=31 gibt es 79182 bekannte minimale (PRP-)Primzahlen und 24 ungelöste Fälle
13. ↑ Für die Basis b=32 gibt es 45205 bekannte minimale (PRP-)Primzahlen und 78 ungelöste Fälle
14. ↑ Für die Basis b=33 gibt es 57676 bekannte minimale (PRP-)Primzahlen und 33 ungelöste Fälle
15. ↑ Für die Basis b=34 gibt es 56457 bekannte minimale (PRP-)Primzahlen und 33 ungelöste Fälle
16. ↑ Für die Basis b=35 gibt es 182378 bekannte minimale (PRP-)Primzahlen und 15 ungelöste Fälle
17. ↑ Für die Basis b=36 gibt es 6296 bekannte minimale (PRP-)Primzahlen und einen ungelösten Fall: O{L}Z
18. ↑ ^{a b c} Curtis Bright, Raymond Devillers, Jeffrey Shallit: Minimal Elements for the Prime Numbers. University of Waterloo, 2015, S. 20, abgerufen am 4. Juli 2018. 

Weblinks

• Chris K. Caldwell: minimal prime. Prime Pages - The Prime Glossary, abgerufen am 4. Juli 2018. 

• Minimale Primzahlen und ungelöste Familien mit Basen von 2 bis 30 (englisch)
• Minimale Primzahlen und ungelöste Familien mit Basen von 28 bis 50 (englisch)