Zirkulare Primzahl

In der Zahlentheorie ist eine zirkulare Primzahl (vom englischen circular prime) eine Primzahl, deren Ziffern man zyklisch vertauschen kann und die erhaltene Zahl trotzdem eine Primzahl bleibt.^[1]

Beispiele im Dezimalsystem

• Die Zahl ${\displaystyle p=1193}$ ist im Dezimalsystem eine zirkulare Primzahl, weil man durch zyklische Vertauschung ihrer Ziffern folgende Primzahlen erhält:

${\displaystyle p=1193\in \mathbb {P} \longrightarrow p_{2}=1931\in \mathbb {P} \longrightarrow p_{3}=9311\in \mathbb {P} \longrightarrow p_{4}=3119\in \mathbb {P} \longrightarrow p}$

• Es sind im Dezimalsystem folgende zirkulare Primzahlen bekannt (aus denen man durch zyklische Vertauschung weitere machen kann):

2, 3, 5, 7, 11, 13, 17, 37, 79, 113, 197, 199, 337, 1193, 3779, 11939, 19937, 193939, 199933, R₁₉=1111111111111111111, R₂₃=11111111111111111111111, R₃₁₇, R₁₀₃₁, R₄₉₀₈₁, R₈₆₄₅₃, R₁₀₉₂₉₇, R₂₇₀₃₄₃, R_5794777 und R_8177207 (Folge A016114 in OEIS)

Dabei ist ${\displaystyle R_{n}=11\ldots 11}$ mit insgesamt ${\displaystyle n}$ Einsen (sie hat also ${\displaystyle n}$ Stellen). Man nennt diese Zahlen Repunits. Die Indizes der primen Repunits kann man auch bei der Folge A004023 in OEIS ablesen. Die bisher letzten Repunits ${\displaystyle R_{49081},R_{86453},R_{109297},R_{270343},R_{5794777}}$ und ${\displaystyle R_{8177207}}$ sind PRP-Zahlen, es ist also noch nicht ganz gesichert, ob sie wirklich Primzahlen sind.^[2] Es gibt keine weiteren zirkularen Primzahlen, welche kleiner als ${\displaystyle 10^{23}}$ sind.^[3]

• Es sind im Dezimalsystem folgende 55 zirkulare Primzahlen bekannt (inklusive der durch zyklische Vertauschung erhaltenen; inklusive der vier einstelligen Trivialfälle ${\displaystyle 2,3,5}$ und ${\displaystyle 7}$ und der Repunit ${\displaystyle 11}$; ohne die größeren Repunits):

2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197, 199, 311, 337, 373, 719, 733, 919, 971, 991, 1193, 1931, 3119, 3779, 7793, 7937, 9311, 9377, 11939, 19391, 19937, 37199, 39119, 71993, 91193, 93719, 93911, 99371, 193939, 199933, 319993, 331999, 391939, 393919, 919393, 933199, 939193, 939391, 993319, 999331 (Folge A068652 in OEIS)

Wahrscheinlich gibt es, abgesehen von den Repunits, keine weiteren zirkularen Primzahlen.^[4]

Beispiele in anderen Basen

• Es sind im Duodezimalsystem (also mit Basis ${\displaystyle b=12}$) folgende zirkulare Primzahlen bekannt (aus die man durch zyklische Vertauschung weitere machen kann). Aus Ermangelung an weiteren Ziffern wird A=10 und B=11 gesetzt:

2, 3, 5, 7, B, 11, 15, 57, 5B, 111, 117, 11B, 175, 1B7, 157B, 555B, 11111, 115B77, R₁₇, R₈₁, R₉₁, R₂₂₅, R₂₅₅, R_4A5, R₅₇₇₇, R_879B, R_198B1, R₂₃₁₇₅ und R₃₁₁₄₀₇

Dabei ist wie vorher ${\displaystyle R_{n}=11\ldots 11}$ eine Repunit (zur Basis ${\displaystyle b=12}$) mit insgesamt ${\displaystyle n}$ Einsen (sie hat also ${\displaystyle n}$ Stellen). Es gibt bis ${\displaystyle 12^{12}}$ keine weiteren zirkularen Primzahlen im Duodezimalsystem.

Beispiel:

Es ist die Duodezimalzahl ${\displaystyle 157B_{12}={\underline {1}}\cdot 12^{3}+{\underline {5}}\cdot 12^{2}+{\underline {7}}\cdot 12^{1}+{\underline {11}}\cdot 12^{0}=2543\in \mathbb {P} }$ eine Primzahl. Vertauscht man ihre Ziffern zyklisch, erhält man drei weitere Primzahlen, nämlich ${\displaystyle 57B1_{12}=9781\in \mathbb {P} }$, ${\displaystyle 7B15_{12}=13697\in \mathbb {P} }$ und ${\displaystyle B157_{12}=19219\in \mathbb {P} }$.

Eigenschaften

• Im Dezimalsystem darf, bis auf ${\displaystyle p=2}$ und ${\displaystyle p=5}$ eine zirkulare Primzahl nur aus den Ziffern ${\displaystyle 1,3,7}$ oder ${\displaystyle 9}$ bestehen.

Beweis:

Wären bei einer zirkularen Primzahl auch die Ziffern ${\displaystyle 0,2,4,5,6}$ oder ${\displaystyle 8}$ erlaubt, so könnte man sie so lange zyklisch vertauschen, bis diese Ziffern an der Einerstelle stehen. Dann wären sie aber durch ${\displaystyle p=2}$ oder ${\displaystyle p=5}$ teilbar und somit keine Primzahlen mehr. ${\displaystyle \Box }$

• Jede prime Repunit ist eine zirkulare Primzahl.

Beweis:

Eine Repunit besteht ausschließlich aus Einsen (wie zum Beispiel ${\displaystyle R_{19}=1111111111111111111}$). Somit erhält man durch zyklische Vertauschung ihrer Ziffern keine andere Zahl, deswegen bleibt die „neu erhaltene“ Zahl eine Primzahl. ${\displaystyle \Box }$

• Sei ${\displaystyle n}$ eine zirkulare Primzahl im Dualsystem (also mit Basis ${\displaystyle b=2}$). Dann gilt:

${\displaystyle n}$ ist eine Mersenne-Primzahl.

Beweis:

Im Dualsystem gibt es nur die beiden Ziffern ${\displaystyle 0}$ und ${\displaystyle 1}$. Wenn in einer Dualzahl eine ${\displaystyle 0}$ vorkommt, würde man durch zyklische Vertauschung erreichen, dass die ${\displaystyle 0}$ an der Einerstelle ist. Dualzahlen mit einer ${\displaystyle 0}$ an der Einerstelle sind aber gerade Zahlen und somit keine Primzahlen (zum Beispiel ist ${\displaystyle 11110_{2}={\underline {1}}\cdot 2^{4}+{\underline {1}}\cdot 2^{3}+{\underline {1}}\cdot 2^{2}+{\underline {1}}\cdot 2^{1}+{\underline {0}}\cdot 2^{0}=16+8+4+2+0=30}$ eine gerade Zahl). Also darf eine zirkulare Primzahl zur Basis ${\displaystyle b=2}$ keine Nullen enthalten, muss also ausschließlich aus Einsen bestehen. Dualzahlen die nur aus Einsen bestehen, haben aber, umgerechnet ins Dezimalsystem, die Form ${\displaystyle n=2^{n}-1}$ (zum Beispiel ist ${\displaystyle 11111_{2}={\underline {1}}\cdot 2^{4}+{\underline {1}}\cdot 2^{3}+{\underline {1}}\cdot 2^{2}+{\underline {1}}\cdot 2^{1}+{\underline {1}}\cdot 2^{0}=16+8+4+2+1=31=2^{5}-1}$). Diese Zahlen sind Mersenne-Zahlen. Wenn sie prim sind, sind es Mersenne-Primzahlen. ${\displaystyle \Box }$

• Jede permutierbare Primzahl ist eine zirkulare Primzahl.

Beweis:

Eine permutierbare Primzahl ist eine Primzahl, bei der man ihre Ziffern beliebig neu anordnen kann und trotzdem wieder eine Primzahl entsteht. Bei zirkularen Primzahlen wird aber lediglich eine zyklische Vertauschung gefordert, welche bei permutierbaren Primzahlen natürlich auch erlaubt ist (zyklische Vertauschungen sind nur etwas speziellere Neuanordnungen ihrer Ziffern). Somit ist eine permutierbare Primzahl auch immer eine zirkulare Zahl. ${\displaystyle \Box }$

• Nicht jede zirkulare Primzahl ist eine permutierbare Primzahl.

Beweis:

Es genügt ein Gegenbeispiel: Wenn man bei der zirkularen Primzahl ${\displaystyle p=1193}$ die Ziffern geeignet vertauscht, erhält man die zusammengesetzte Zahl ${\displaystyle 1139=17\cdot 67}$. Somit ist ${\displaystyle p=1193}$ keine permutierbare Primzahl. ${\displaystyle \Box }$

Ungelöste Probleme

• Es wird vermutet, dass es unendlich viele zirkulare Primzahlen gibt, weil es wahrscheinlich unendlich viele prime Repunits gibt, welche allesamt gleichzeitig zirkulare Primzahlen sind.^[4]

• Es wird vermutet, dass es keine weiteren zirkularen Primzahlen gibt, welche nicht gleichzeitig Repunits sind.^[4]

• Es wird vermutet, dass die folgenden Zahlen, die nicht gleichzeitig Repunits sind (sogenannte Nicht-Repunits), die größten zirkularen Primzahlen sind (im Dezimalsystem angegeben; die Liste beginnt mit ${\displaystyle b=3}$, weil für ${\displaystyle b=2}$ (also im Dualsystem) jede zirkulare Primzahl eine Mersenne-Primzahl und somit in diesem Zahlensystem eine Repunit ist, wie bei den Eigenschaften weiter oben schon gezeigt wurde):^[5]

7, 1013, 3121, 211, 13143449029, 16244441, 4717103, 999331, 378470237117827, 2894561 … (Folge A293142 in OEIS)

Die obigen größten Nicht-Repunits, die wahrscheinlich zirkulare Primzahlen sind, werden im jeweiligen Stellenwertsystem wie folgt geschrieben (beginnend mit der Basis ${\displaystyle b=3}$):^[5]

21, 33311, 44441, 551, 643464321244, 75757331, 8778575, 999331, AA657365177398, B77115 …

Die Anzahl der zirkularen Primzahlen, die Nicht-Repunits sind, gibt die folgende Liste an (beginnend mit der Basis ${\displaystyle b=3}$, ohne die einstelligen Trivialfälle):^[5]

0, 3, 10, 24, 5, 141, 42, 50, 54, ?, 37 …

Beispiel:

Sei ${\displaystyle b=8}$. Dann gibt die erste obige Liste an, dass die Zahl ${\displaystyle p=16244441}$ wahrscheinlich die größte zirkulare Primzahl ist, die nicht aus allen Einsen besteht. Der zweiten Liste kann man entnehmen, dass man diese Zahl im Stellenwertsystem mit der Basis ${\displaystyle b=8}$ als ${\displaystyle p=75757331_{8}}$ schreibt. Aus der dritten Liste kann man ablesen, dass es insgesamt wahrscheinlich genau 141 zirkulare Primzahlen zur Basis ${\displaystyle b=8}$ gibt, die nicht gleichzeitig Repunits sind.

Einzelnachweise

1. ↑ Eric W. Weisstein: Circular Prime. In: MathWorld (englisch).
2. ↑ Henri Lifchitz, Renaud Lifchitz: PRP Records - Probable Primes Top 10000, Search for: (10^x-1)/9. PRP Records, abgerufen am 16. August 2021. 
3. ↑ Patrick De Geest: Circular Primes. World Of Numbers, abgerufen am 8. Juli 2018 (englisch). 
4. ↑ ^{a b c} Chris K. Caldwell: Circular Prime. Prime Pages, abgerufen am 8. Juli 2018 (englisch). 
5. ↑ ^{a b c} Mersenneforum: Type of primes in various bases

Weblinks

• Eric W. Weisstein: Circular Prime. In: MathWorld (englisch).
• Chris K. Caldwell: Circular Prime. Prime Pages, abgerufen am 8. Juli 2018 (englisch).