Permutierbare Primzahl

Eine permutierbare Primzahl (auch absolute Primzahl) ist eine Primzahl, bei der eine beliebige Neuanordnung ihrer Ziffern ebenfalls eine Primzahl ergibt. Zum Beispiel ist 113 eine permutierbare Primzahl, da 131 und 311 ebenfalls prim sind. Ob diese Bedingung erfüllt ist, hängt dabei auch vom verwendeten Stellenwertsystem ab. Als sich erstmals der Mathematiker Hans-Egon Richert in einem Aufsatz mit diesen Zahlen befasste, nannte er sie permutierbare Primzahlen.[1] Spätere Autoren verwendeten auch den Begriff der absoluten Primzahl.[2]

Permutierbare Primzahlen im Dezimalsystem

Die ersten permutierbaren Primzahlen im Dezimalsystem sind die folgenden:

2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 199, 311, 337, 373, 733, 919, 991, R₁₉ (= 1111111111111111111), R₂₃, R₃₁₇, R₁₀₃₁, R₄₉₀₈₁, R₈₆₄₅₃, R₁₀₉₂₉₇ und R₂₇₀₃₄₃ (Folge A003459 in OEIS)

Da in obiger Liste die Zahlen 113, 131 und 311 enthalten sind, aber durch Permutation der Ziffern ineinander übergeführt werden können, ist es sinnvoll, nur jeweils die kleinste Zahl dieser Permutationsklasse anzugeben:

2, 3, 5, 7, 11, 13, 17, 37, 79, 113, 199, 337, R₁₉, R₂₃, R₃₁₇, R₁₀₃₁, R₄₉₀₈₁, R₈₆₄₅₃, R₁₀₉₂₉₇ und R₂₇₀₃₄₃ (Folge A258706 in OEIS)

991 ist die größte bekannte permutierbare Primzahl, die aus unterschiedlichen Ziffern besteht. Alle weiteren bekannten permutierbaren Primzahlen sind Repunits, d. h. Zahlen, die nur die Ziffer 1 enthalten. Bewiesen wurde dies für alle n-stelligen Zahlen 3 < n < 6 × 10^175,[1] es wird jedoch vermutet, dass es auch darüber hinaus keine weiteren permutierbaren Primzahlen gibt, die aus unterschiedlichen Ziffern bestehen.[3] Demnach wären 2, 3, 5, 7, 13, 17, 37, 79, 113, 199, 337 und ihre Permutationen die einzigen permutierbaren Primzahlen, die keine Einserfolgen sind (und nach einer alternativen Definition, die unterschiedliche Ziffern für zwei- oder mehrstellige Zahlen verlangt[4], die einzigen überhaupt). Die Indizes der primen Repunits kann man auch bei der Folge A004023 in OEIS ablesen. Die bisher letzten Repunits ${\displaystyle R_{86453},R_{109297}}$ und ${\displaystyle R_{270343}}$ sind PRP-Zahlen, es ist also noch nicht ganz gesichert, ob sie wirklich Primzahlen sind.[5]

Eigenschaften

• Alle mehrstelligen permutierbaren Primzahlen können notwendigerweise nur die Ziffern 1, 3, 7 und 9 enthalten, da das Vorkommen einer geraden Zahl oder einer 5 bedeuten würde, dass mindestens eine Permutation durch 2 oder durch 5 teilbar und somit nicht prim wäre.
• Eine permutierbare Primzahl kann nicht alle vier der oben genannten möglichen Ziffern 1, 3, 7 und 9 gleichzeitig enthalten[6]; auch mit drei verschiedenen aus diesen vier Ziffern ist keine permutierbare Primzahl möglich.
• Nur eine von den maximal zwei unterschiedlichen Ziffern kann doppelt oder mehrfach auftauchen.[7]
• Alle permutierbaren Primzahlen, die kein Primzahlpalindrom darstellen, sind auch Mirpzahlen.

Permutierbare Primzahlen mit anderen Basen

Beispiele

• Die ersten permutierbare Primzahlen mit Basis 12 sind die folgenden (wobei aus Ermangelung an weiteren Ziffern A=10 und B=11 gesetzt wird):

2, 3, 5, 7, B, 11, 15, 57, 5B, 111, 117, 11B, 555B, R₅, R₁₇, R₈₁, R₉₁, R₂₂₅, R₂₅₅, R_4A5, …

Es gibt keine weiteren permutierbare Primzahlen mit Basis 12 mit weniger als 9739 Stellen. Es gibt auch keine n-stelligen permutierbaren Primzahlen mit Basis 12 mit 4<n<12^144, welche keine Repunit ist.

• Die kleinsten permutierbare Primzahlen mit Basis b mit mehr als zwei verschiedenen Ziffern sind die folgenden (wobei aus Ermangelung an weiteren Ziffern A=10, B=11, …, E=14, … gesetzt wird):

139₁₁, 36A₁₁, 247₁₃, 78A₁₃, 29E₁₉

Es gibt keine weiteren Zahlen dieser Form, welche kleiner als 10^9 sind (M. Fiorentini, 2015).

Eigenschaften

• Permutierbare Primzahlen mit Basis 2 müssen Repunits sein, dürfen also nur Einser enthalten.

(Wäre ein Null dabei, könnte man durch Permutation ihrer Stellen die Null an die Einerstelle geben und die Zahl wäre gerade und nicht prim.)

• Permutierbare Primzahlen mit Basis 2 sind die Mersenne-Zahlen.
• Primzahlen, die im betrachteten Stellenwertsystem einstellig sind, sind aus trivialen Gründen permutierbare Primzahlen, z. B. 13₁₀ = D₁₆ im Hexadezimalsystem.
• Permutierbare Primzahlen mit mehr als einer Stelle, unabhängig von der Basis, dürfen nur Ziffern besitzen, die teilerfremd zur Basis sind.

(Im Dezimalsystem, also mit Basis 10, dürfen die Ziffern 0, 2, 4, 5, 6 und 8 nicht vorkommen, weil sie zu 10 nicht teilerfremd sind.)

• Permutierbare Primzahlen mit Basis 10 oder Basis 12 sind entweder Repunits oder Beinahe-Repunits. Wenn diese Primzahl n Stellen hat, steht also entweder an allen n Stellen immer dieselbe Ziffer, oder an n-1 Stellen steht dieselbe Ziffer und nur an einer Stelle eine andere (zum Beispiel xxxxxy). Sie besteht somit aus maximal zwei verschiedenen Ziffern.
• Permutierbare Primzahlen mit Basis 10 oder Basis 12 haben nur Ziffern, welche teilerfremd sind.

(Wenn eine Primzahl p existieren würde, die beide verschiedenen Ziffern teilt, würde diese Primzahl die gesamte Zahl teilen.)

• Permutierbare Primzahlen mit Basis 10 oder Basis 12, bei der alle Ziffern gleich sind (also Repunits sind), bestehen immer aus Einsern.
• Jede permutierbare Primzahl ist auch gleichzeitig eine zirkulare Primzahl.
• Nicht jede zirkulare Primzahl ist eine permutierbare Primzahl.

Ungelöste Probleme

• Gibt es weitere permutierbare Primzahlen mit Basis 12, welche keine Repunits sind und die sich nicht in der folgenden Liste befinden:

2, 3, 5, 7, B, 15, 57, 5B, 117, 11B, 555B

Man vermutet, dass es keine weiteren gibt.

Siehe auch

• Liste besonderer Zahlen
• Zirkulare Primzahl

Einzelnachweise

1. H.E. Richert: Om permutable primtall. In: Norsk Matematisk Tidsskrift. Nr. 33, 1951, S. 50 ff.
2. T. Bhargava, P. Doyle: On the existence of absolute primes. In: Mathematics Magazine. Nr. 47, 1974, S. 233.
3. Chris K. Caldwell: The Prime Glossery: Permutable Prime. Abgerufen am 11. August 2020.
4. OEIS: Absolute primes, alternative definition. Abgerufen am 24. Februar 2014.
5. Henri Lifchitz, Renaud Lifchitz: PRP Records - Probable Primes Top 10000, Search for: (10^x-1)/9. PRP Records, abgerufen am 8. Juli 2018. 
6. A. Slinko: Absolute primes. Abgerufen am 24. Februar 2014.
7. A.W. Johnson: Absolute primes. In: Mathematics Magazine. Nr. 50, 1977, S. 100 ff.

V – D

Primzahl­mengen

formelbasiert	Carol ((2^n − 1)^2 − 2) | Doppelte Mersenne (2^2p − 1 − 1) | Fakultät (n! ± 1) | Fermat (2^2n + 1) | Kubisch (x^3 − y^3)/(x − y) | Kynea ((2^n + 1)^2 − 2) | Leyland (x^y + y^x) | Mersenne (2^p − 1) | Mills (A^3n) | Pierpont (2^u⋅3^v + 1) | Primorial (pn# ± 1) | Proth (k⋅2^n + 1) | Pythagoreisch (4n + 1) | Quartisch (x^4 + y^4) | Thabit (3⋅2^n − 1) | Wagstaff ((2^p + 1)/3) | Williams ((b-1)⋅b^n − 1) | Woodall (n⋅2^n − 1)
Primzahlfolgen	Bell | Fibonacci | Lucas | Motzkin | Pell | Perrin
eigenschaftsbasiert	Elitär | Fortunate | Gut | Glücklich | Higgs | Hochkototient | Isoliert | Pillai | Ramanujan | Regulär | Stark | Stern | Wall–Sun–Sun | Wieferich | Wilson
basis­abhängig	Belphegor | Champernowne | Dihedral | Einzigartig | Fröhlich | Keith | Lange | Minimal | Mirp | Permutierbar | Primeval | Palindrom | Repunit-Primzahl ((10^n − 1)/9) | Schwach | Smarandache–Wellin | Strobogrammatisch | Tetradisch | Trunkierbar | Zirkular
basierend auf Tupel	Ausbalanciert (p − n, p, p + n) | Chen | Cousin (p, p + 4) | Cunningham (p, 2p ± 1, …) | Drilling (p, p + 2 oder p + 4, p + 6) | Konstellation | Sexy (p, p + 6) | Sichere (p, (p − 1)/2) | Sophie Germain (p, 2p + 1) | Vierling (p, p + 2, p + 6, p + 8) | Zwilling (p, p + 2) | Zwillings-Bi-Kette (n ± 1, 2n ± 1, …)
nach Größe	Titanisch (1.000+ Stellen) | Gigantisch (10.000+ Stellen) | Mega (1.000.000+ Stellen) | Beva (1.000.000.000+ Stellen)