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.

• 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 ${\displaystyle 10}$ (also im Dezimalsystem) sind die folgenden 26 Primzahlen (Folge A071062 in OEIS):

${\displaystyle 2,3,5,7,11,19,41,61,89,409,449,499,881,991,6\,469,6\,949,9\,001,9\,049,9\,649,9\,949,60\,649,666\,649,946\,669,60\,000\,049,66\,000\,049,66\,600\,049}$

• Folgende Tabelle zeigt die minimalen Primzahlen in der Basis ${\displaystyle b}$ (wobei aus Ermangelung an weiteren Ziffern ${\displaystyle A=10}$ und ${\displaystyle B=11}$ gesetzt wird). Es gibt zur jeweiligen Basis nicht mehr minimale Primzahlen.^[1][2]

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

Im Dezimalsystem geschrieben lauten sie wie folgt (Folge A110600 in OEIS):

${\displaystyle 2,3,5,7,11,13,73,97,109,577,1\,489,7\,537,17\,401,226\,201,1\,097\,113,32\,555\,521,388\,177\,921}$

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,\dotsc }$ sind die folgenden:^[3]

2, 3, 3, 8, 7, 9, 15, 12, 26, 152, 17, 228, 240, 100, 483, 1.279~1.280,^[4] 50, 3.462~3.463,^[5] 651, 2600~2601,^[6] 1.242, 6.021, 306, 17.597~17.609,^[7] 5.662~5.664,^[8] 17.210~17.215,^[9] 5.783~5.784,^[10] 57.283~57.297,^[11] 220, 79.182~79.206,^[12] 45.205~45.283,^[13] 57.676~57.709,^[14] 56.457~56.490,^[15] 182378~182393,^[16] 6.296~6.297,^[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,\dotsc }$ sind die folgenden:^[1][3]

${\displaystyle {\begin{aligned}&2,3,2,5,5,5,9,4,8,45,8,32\,021,86,107,3\,545,\geq 111\,334,33,\geq 110\,986,449,\geq 479\,150,764,800\,874,100,\geq 136\,967,\\&\geq 8\,773,\geq 109\,006,\geq 94\,538,\geq 174\,240,1\,024,\geq 9\,896,\geq 9\,750,\geq 9\,961,\geq 9\,377,\geq 9\,599,\geq 81\,995,\dotsc \end{aligned}}}$

Beispiel 1:

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

Beispiel 2:

An der 26. Stelle obiger Liste steht der Eintrag ${\displaystyle \geq 8\,773}$. Die größte minimale (PRP-)Primzahl zur Basis ${\displaystyle b=26}$ hat also ${\displaystyle 8\,773}$ 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,\dotsc }$ sind die folgenden, wenn man sie im Dezimalsystem schreibt:

${\displaystyle {\begin{aligned}&3,13,5,3\,121,5\,209,2\,801,76\,695\,841,811,66\,600\,049,29\,156\,193\,474\,041\,220\,857\,161\,146\,715\,104\,735\,751\,776\,055\,777,388\,177\,921,13^{32\,020}\cdot 8+183,\\&105\,424\,857\,819\,287\,798\,806\,418\,819\,113\,233\,738\,918\,727\,566\,030\,978\,473\,259\,776\,662\,287\,591\,943\,095\,417\,282\,958\,456\,246\,916\,612\,161,\\&436\,635\,814\,641\,280\,043\,127\,962\,407\,363\,407\,208\,906\,111\,673\,434\,962\,498\,607\,709\,751\,248\,805\,460\,292\,422\,544\,779\,495\,998\,033\,626\,489\,944\,124\,062\,146\,459\,306\,989\,397\,233,\\&16^{3\,544}\cdot 9+145,\geq (17^{111\,333}\cdot 73-9)/16,249\,069\,897\,374\,447\,078\,426\,903\,207\,266\,791\,381\,270\,529,\geq (19^{110\,984}\cdot 904-1)/3,\\&(20^{449}\cdot 16-2\,809)/19,\geq (21^{479\,149}\cdot 51-1\,243)/4,22^{763}\cdot 20+7\,041,(23^{800\,873}\cdot 106-7)/11,\\&973\,767\,003\,942\,195\,520\,947\,294\,504\,280\,890\,002\,680\,537\,875\,404\,412\,883\,659\,428\,819\,153\,939\,518\,991\,719\,953\,852\,457\,999\,342\,229\,586\,282\,557\,076\,411\,687\,300\,474\,817\,686\,178\,175\,693\,329,\\&\geq (25^{136\,966}\cdot 37+63)/4,\geq (26^{8773}\cdot 22+53)/25,\geq 27^{109\,005}\cdot 10+697,\geq (28^{94\,536}\cdot 6\,092-143)/9,\geq 29^{174\,239}\cdot 24+13\,361,30^{1\,023}\cdot 12+1,\\&\geq (31^{9\,894}\cdot 4\,187-5)/6,\geq (32^{9\,749}\cdot 898-309)/31,\geq (33^{9\,961}\cdot 21+7\,723)/32,\geq 34^{9\,375}\cdot 1\,048+27,\geq (35^{9\,597}\cdot 13\,456-9)/17,\geq (36^{81\,995}\cdot 5+821)/7,\dotsc \end{aligned}}}$

Beispiel:

An der 12. Stelle obiger Liste steht die Zahl ${\displaystyle 388\,177\,921}$. Tatsächlich ist die größte minimale Primzahl zur Basis ${\displaystyle 12}$ die Zahl ${\displaystyle AA\,000\,001_{12}={\underline {10}}\cdot 12^{7}+{\underline {10}}\cdot 12^{6}+{\underline {1}}\cdot 12^{0}=388\,177\,921_{10}}$.

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

${\displaystyle 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, die alle 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} }$), die aus Ziffern bestehen, deren Teilfolgen im Dezimalsystem keine weiteren Primzahlen der Form ${\displaystyle p\equiv 1{\pmod {4}}}$ ergeben:

${\displaystyle {\begin{aligned}&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,1\,669,2\,221,3\,001,3\,121,3\,169,3\,221,3\,301,3\,833,\\&4\,969,4\,993,6\,469,6\,833,6\,949,7\,121,7\,477,7\,949,9\,001,9\,049,9\,221,9\,649,9\,833,\dotsc ,\\&8\,888\,888\,888\,888\,888\,888\,888\,888\,888\,888\,888\,888\,888\,888\,888\,888\,888\,888\,888\,888\,888\,888\,888\,888\,888\,833\end{aligned}}}$ (Folge A111055 in OEIS)

Beispiel:

Aus der Primzahl ${\displaystyle 3\,169}$ kann man die Zahlen ${\displaystyle 1,3,6,9,16,19,31,36,39,69,169,316,319}$ und ${\displaystyle 369}$ machen, die alle 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} }$), die aus Ziffern bestehen, deren Teilfolgen im Dezimalsystem keine weiteren Primzahlen der Form ${\displaystyle p\equiv 3{\pmod {4}}}$ ergeben (Folge A111056 in OEIS):

${\displaystyle {\begin{aligned}&3,7,11,19,59,251,491,499,691,991,2\,099,2\,699,2\,999,4\,051,4\,451,4\,651,5\,051,5\,651,5\,851,6\,299,6\,451,6\,551,6\,899,8\,291,8\,699,8\,951,\\&8\,999,9\,551,9\,851,22\,091,22\,291,66\,851,80\,051,80\,651,84\,551,85\,451,86\,851,88\,651,92\,899,98\,299,98\,899,\dotsc ,(10^{19\,153}\cdot 2+691)/9\end{aligned}}}$

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, die 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]

${\displaystyle 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,\dotsc }$

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

${\displaystyle 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,\dotsc }$

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

${\displaystyle {\begin{aligned}&15,9,21,27,475,49,477,70,731,123,8797,169,1\,529,208,2\,899,291,99\,491,361,5\,423,418,9\,275,\\&529,30\,995,598,15\,645,644,18\,511,843,795\,037,961,23\,779,1054,34\,311,1\,116,56\,129,\dotsc \end{aligned}}}$

• Trunkierbare Primzahl
• Permutierbare Primzahl
• Zirkulare Primzahl

1. ↑ ^{a b} Curtis Bright: Minimale Primzahlen und ungelöste Fälle („Familien“) mit Basen von 2 bis 30. In: Github.com. Abgerufen am 9. Juni 2024 (englisch).
2. ↑ Curtis Bright, Jeffrey Shallit, Raymond Devillers: Minimal Elements for the Prime Numbers. (PDF; 0,3 MB). In: cs.uwaterloo.ca. University of Waterloo, Université libre de Bruxelles, 7. Dezember 2016, abgerufen am 9. Juni 2024 (englisch).
3. ↑ ^{a b} Curtis Bright, Raymond Devillers, Jeffrey Shallit: Minimal Elements for the Prime Numbers. (PDF) In: cs.uwaterloo.ca. University of Waterloo, 11. Juni 2015, S. 15, abgerufen am 9. Juni 2024. 
4. ↑ Curtis Bright: Für die Basis ${\displaystyle b=17}$ gibt es 1.279 bekannte minimale (PRP-)Primzahlen und einen ungelösten Fall: F1{9}. In: Github.com. Abgerufen am 9. Juni 2024 (englisch).
5. ↑ Curtis Bright: Für die Basis ${\displaystyle b=19}$ gibt es 3.462 bekannte minimale (PRP-)Primzahlen und einen ungelösten Fall: EE1{6}. In: Github.com. Abgerufen am 9. Juni 2024 (englisch).
6. ↑ Curtis Bright: Für die Basis ${\displaystyle b=21}$ gibt es 2.600 bekannte minimale (PRP-)Primzahlen und einen ungelösten Fall: G{0}FK. In: Github.com. Abgerufen am 9. Juni 2024 (englisch).
7. ↑ Curtis Bright: Für die Basis ${\displaystyle b=25}$ gibt es 17.597 bekannte minimale (PRP-)Primzahlen und 12 ungelöste Fälle. In: Github.com. Abgerufen am 9. Juni 2024 (englisch).
8. ↑ Curtis Bright: Für die Basis ${\displaystyle b=26}$ gibt es 5.662 bekannte minimale Primzahlen und zwei ungelöste Fälle: {A}6F und {I}GL. In: Github.com. Abgerufen am 9. Juni 2024 (englisch).
9. ↑ Curtis Bright: Für die Basis ${\displaystyle b=27}$ gibt es 17.210 bekannte minimale (PRP-)Primzahlen und 5 ungelöste Fälle. In: Github.com. Abgerufen am 9. Juni 2024 (englisch).
10. ↑ Curtis Bright: Für die Basis ${\displaystyle b=28}$ gibt es 5.783 bekannte minimale (PRP-)Primzahlen und einen ungelösten Fall: O{A}F. In: Github.com. Abgerufen am 9. Juni 2024 (englisch).
11. ↑ Curtis Bright: Für die Basis ${\displaystyle b=29}$ gibt es 57.283 bekannte minimale (PRP-)Primzahlen und 14 ungelöste Fälle. In: raw.githubusercontent.com. Abgerufen am 9. Juni 2024 (englisch).
12. ↑ RaymondDevillers: Für die Basis ${\displaystyle b=31}$ gibt es 79.182 bekannte minimale (PRP-)Primzahlen und 24 ungelöste Fälle. In: raw.githubusercontent.com. Abgerufen am 9. Juni 2024 (englisch).
13. ↑ RaymondDevillers: Für die Basis ${\displaystyle b=32}$ gibt es 45.205 bekannte minimale (PRP-)Primzahlen und 78 ungelöste Fälle. In: raw.githubusercontent.com. Abgerufen am 9. Juni 2024 (englisch).
14. ↑ RaymondDevillers: Für die Basis ${\displaystyle b=33}$ gibt es 57.676 bekannte minimale (PRP-)Primzahlen und 33 ungelöste Fälle. In: raw.githubusercontent.com. Abgerufen am 9. Juni 2024 (englisch).
15. ↑ RaymondDevillers: Für die Basis ${\displaystyle b=34}$ gibt es 56.457 bekannte minimale (PRP-)Primzahlen und 33 ungelöste Fälle. In: raw.githubusercontent.com. Abgerufen am 9. Juni 2024 (englisch).
16. ↑ RaymondDevillers: Für die Basis ${\displaystyle b=35}$ gibt es 182.378 bekannte minimale (PRP-)Primzahlen und 15 ungelöste Fälle. In: raw.githubusercontent.com. Abgerufen am 9. Juni 2024 (englisch).
17. ↑ RaymondDevillers: Für die Basis ${\displaystyle b=36}$ gibt es 6.296 bekannte minimale (PRP-)Primzahlen und einen ungelösten Fall: O{L}Z. In: Github.com. Abgerufen am 9. Juni 2024 (englisch).
18. ↑ ^{a b c} Curtis Bright, Raymond Devillers, Jeffrey Shallit: Minimal Elements for the Prime Numbers. In: cs.uwaterloo.ca. University of Waterloo, 11. Juni 2015, S. 20, abgerufen am 9. Juni 2024. 

• Chris K. Caldwell: minimal prime. In: t5k.org. Prime Pages – The Prime Glossary; abgerufen am 9. Juni 2024 

• Curtis Bright: Minimale Primzahlen und ungelöste Fälle („Familien“) mit Basen von 2 bis 30. In: Github.com.
• RaymondDevillers: Minimale Primzahlen und ungelöste Familien mit Basen von 28 bis 50. In: Github.com.