Minimale Primzahl
# Minimale Primzahl

In der Unterhaltungsmathematik ist eine minimale Primzahl eine Primzahl $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 $109$ ist keine minimale Primzahl, weil man aus ihren Ziffern die Primzahl $19$ machen kann. Die einzelnen Ziffern der Teilfolgen müssen also in der ursprünglichen Zahl nicht zusammenhängend sein.
* Aus der Zahl $409$ kann man folgende Teilfolgen ihrer Ziffern machen: $0,4,9,09,40,49$. Keine dieser Zahlen ist eine Primzahl, somit ist $409$ eine minimale Primzahl.
* Die Zahl $991$ ist eine minimale Primzahl, weil man aus ihren Ziffern nur die Zahlen $1,9,91$ und $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 $19$ sehr wohl eine Primzahl).
* Die einzigen minimalen Primzahlen für die Basis $10$ (also im Dezimalsystem) sind die folgenden 26 Primzahlen (Folge A071062 in OEIS):
    $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$

## Beispiele mit Basis b

* Folgende Tabelle zeigt die minimalen Primzahlen in der Basis $b$ (wobei aus Ermangelung an weiteren Ziffern $A=10$ und $B=11$ gesetzt wird). Es gibt zur jeweiligen Basis nicht mehr minimale Primzahlen.
| Basis $b$ | minimale Primzahlen zur Basis $b$, geschrieben zur Basis $b$ |
| 12 | 10, 11 |
| 13 | 2, 10, 111 |
| 14 | 2, 3, 11 |
| 15 | 2, 3, 10, 111, 401, 414, 14.444, 44.441 (insgesamt 8 minimale Primzahlen) |
| 16 | 2, 3, 5, 11, 4.401, 4.441, 40.041 (insgesamt 7 minimale Primzahlen) |
| 17 | 2, 3, 5, 10, 14, 16, 41, 61, 11.111 (insgesamt 9 minimale Primzahlen) |
| 18 | 2, 3, 5, 7, 111, 141, 161, 401, 661, 4.611, 6.101, 6.441, 60.411, 444.641, 444.444.441 (insgesamt 15 minimale Primzahlen) |
| 19 | 2, 3, 5, 7, 14, 18, 41, 81, 601, 661, 1.011, 1.101 (insgesamt 12 minimale Primzahlen) |
| 10 | 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 (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, 1.1A9, 6.6A9, A.119, A.911, A.AA9, 11.144, 11.191, 11.41A, 11.4A1, 14.11A, 14.4A4, 14.A11, 1A.114, 1A.411, 40.41A, 40.441, 40.4A1, 41.11A, 41.1A1, 44.401, 44.4A1, 44.A01, 6A.609, 6A.669, 6A.696, 6A.906, 6A.966, 90.901, 99.111, A0.111, A0.669, A0.966, A0.999, A0.A09, A4.401, A6.096, A6.966, A6.999, A9.091, A9.699, A9.969, 401.A11, 404.001, 404.111, 440.A41, 4A0.401, 4A4.041, 60A.069, 6A0.096, 6A0.A96, 6A9.099, 6A9.909, 909.991, 999.901, A00.009, A60.609, A66.069, A66.906, A69.006, A90.099, A90.996, A96.006, A96.666, 1.111.14A, 1.111.A14, 1.111.A41, 1.144.441, 1.4A4.444, 1.A44.444, 4.000.111, 4.011.111, 4.1A1.111, 4.411.111, 4.444.41A, 4.A11.111, 4.A40.001, 6.000.A69, 6.000.A96, 6.A00.069, 9.900.991, 9.990.091, A.000.696, A.000.991, A.006.906, A.040.041, A.141.111, A.600.A69, A.906.606, A.909.009, A.990.009, 40.A00.041, 60.A99.999, 99.000.001, A0.004.041, A9.909.006, A9.990.006, A9.990.606, A9.999.966, 400.00A.401, 44A.444.441, 900.000.091, A00.990.001, A44.444.111, A66.666.669, A90.000.606, A99.999.006, A99.999.099, 6.000.00A.999, A.000.144.444, A.900.000.066, A0.000.000.001, A0.014.444.444, 4.000.000.0A0.041, A.000.000.014.444, A.044.444.444.441, A.144.444.444.411, 40.000.000.000.401, A0.000.044.444.441, A00.000.000.444.441, 11.111.111.111.111.111, 14.444.444.444.441.111, 44.444.444.444.444.111, A1.444.444.444.444.444, A9.999.999.999.999.996, 1.444.444.444.444.444.444, 40.000.000.000.000.00A.041, A.999.999.999.999.999.999.999, A44.444.444.444.444.444.444.444.441, 40.000.000.000.000.000.000.000.000.041, 440.000.000.000.000.000.000.000.000.001, 999.999.999.999.999.999.999.999.999.999.991, 444.444.444.444.444.444.444.444.444.444.444.444.444.444.441 (insgesamt 152 minimale Primzahlen) |
| 12 | 2, 3, 5, 7, B, 11, 61, 81, 91, 401, A41, 4.441, A.0A1, AA.AA1, 44.AAA1, A.AA0.001, AA.000.001 (insgesamt 17 minimale Primzahlen) |
* 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):
       $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 $A41_{12}$ ist im Dezimalsystem die Zahl ${\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 $1_{12}=1_{10},4_{12}=4_{10},A_{12}=10_{10},41_{12}=49_{10},A1_{12}=121_{10}$ und $A4_{12}=124_{10}$ machen.
* Die Anzahl der minimalen (zum Teil PRP-) Primzahlen bei gegebener Basis $b=2,3,\dotsc$ sind die folgenden:
       2, 3, 3, 8, 7, 9, 15, 12, 26, 152, 17, 228, 240, 100, 483, 1.279~1.280, 50, 3.462~3.463, 651, 2600~2601, 1.242, 6.021, 306, 17.597~17.609, 5.662~5.664, 17.210~17.215, 5.783~5.784, 57.283~57.297, 220, 79.182~79.206, 45.205~45.283, 57.676~57.709, 56.457~56.490, 182378~182393, 6.296~6.297, …
       Beispiel:
          An der 14. Stelle obiger Liste steht die Zahl $240$. Es gibt also $240$ minimale Primzahlen zur Basis $b=14$.
* Die Stellenanzahl der größten minimalen (zum Teil PRP-) Primzahlen bei gegebener Basis $b=2,3,\dotsc$ sind die folgenden:
       ${\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 $32\,021$. Die größte minimale (PRP-)Primzahl zur Basis $b=13$ hat also $32\,021$ Stellen.
       Beispiel 2:
          An der 26. Stelle obiger Liste steht der Eintrag $\geq 8\,773$. Die größte minimale (PRP-)Primzahl zur Basis $b=26$ hat also $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 $b=2,3,\dotsc$ sind die folgenden, wenn man sie im Dezimalsystem schreibt:
       ${\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 $388\,177\,921$. Tatsächlich ist die größte minimale Primzahl zur Basis $12$ die Zahl $AA\,000\,001_{12}={\underline {10}}\cdot 12^{7}+{\underline {10}}\cdot 12^{6}+{\underline {1}}\cdot 12^{0}=388\,177\,921_{10}$.

## Verallgemeinerungen

* Es gibt genau 32 zusammengesetzte Zahlen im Dezimalsystem, die 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 $731$ kann man die Zahlen $1,3,7,31,71$ und $73$ machen, die alle nicht zusammengesetzt sind. Diese Zahlen sind somit das genaue Gegenteil der minimalen Primzahlen.
* Es gibt im Dezimalsystem genau 146 Primzahlen $p\equiv 1{\pmod {4}}$ (also der Form $p=4k+1$ mit $k\in \mathbb {N}$), die aus Ziffern bestehen, deren Teilfolgen im Dezimalsystem keine weiteren Primzahlen der Form $p\equiv 1{\pmod {4}}$ ergeben:
       ${\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 $3\,169$ kann man die Zahlen $1,3,6,9,16,19,31,36,39,69,169,316,319$ und $369$ machen, die alle keine Primzahlen der Form $p\equiv 1{\pmod {4}}$ sind.
* Es gibt im Dezimalsystem genau 113 Primzahlen $p\equiv 3{\pmod {4}}$ (also der Form $p=4k+3$ mit $k\in \mathbb {N}$), die aus Ziffern bestehen, deren Teilfolgen im Dezimalsystem keine weiteren Primzahlen der Form $p\equiv 3{\pmod {4}}$ ergeben (Folge A111056 in OEIS):
       ${\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 $4051$ kann man die Zahlen $0,1,4,5,01,05,40,41,45,51,051,401,405$ und $451$ machen, die allesamt keine Primzahlen der Form $p\equiv 3{\pmod {4}}$ sind.
* Die Anzahl der minimalen zusammengesetzten Zahlen bei gegebener Basis $b=2,3,\ldots$ sind die folgenden:
       $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 $b=2,3,\dotsc$ sind die folgenden:
       $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:
       ${\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}}$