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.

Beispiele im Dezimalsystem

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

$p=1193\in \mathbb{P}⟶p_2=1931\in \mathbb{P}⟶p_3=9311\in \mathbb{P}⟶p_4=3119\in \mathbb{P}⟶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 (Vorlage:OEIS)

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

• Es sind im Dezimalsystem folgende 55 zirkulare Primzahlen bekannt (inklusive der durch zyklische Vertauschung erhaltenen; inklusive der vier einstelligen Trivialfälle $2,3,5$ und $7$ und der Repunit $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 (Vorlage:OEIS)

Wahrscheinlich gibt es, abgesehen von den Repunits, keine weiteren zirkularen Primzahlen.

Beispiele in anderen Basen

• Es sind im Duodezimalsystem (also mit Basis $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 $R_n=11\dots 11$ eine Repunit (zur Basis $b=12$) mit insgesamt $n$ Einsen (sie hat also $n$ Stellen). Es gibt bis $12^{12}$ keine weiteren zirkularen Primzahlen im Duodezimalsystem.

Beispiel:

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

Eigenschaften

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

Beweis:

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

• Jede prime Repunit ist eine zirkulare Primzahl.

Beweis:

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

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

$n$ ist eine Mersenne-Primzahl.

Beweis:

Im Dualsystem gibt es nur die beiden Ziffern $0$ und $1$. Wenn in einer Dualzahl eine $0$ vorkommt, würde man durch zyklische Vertauschung erreichen, dass die $0$ an der Einerstelle ist. Dualzahlen mit einer $0$ an der Einerstelle sind aber gerade Zahlen und somit keine Primzahlen (zum Beispiel ist $11110_2=\underset{\_}{1}\cdot 2^4+\underset{\_}{1}\cdot 2^3+\underset{\_}{1}\cdot 2^2+\underset{\_}{1}\cdot 2^1+\underset{\_}{0}\cdot 2^0=16+8+4+2+0=30$ eine gerade Zahl). Also darf eine zirkulare Primzahl zur Basis $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 $n=2^n-1$ (zum Beispiel ist $11111_2=\underset{\_}{1}\cdot 2^4+\underset{\_}{1}\cdot 2^3+\underset{\_}{1}\cdot 2^2+\underset{\_}{1}\cdot 2^1+\underset{\_}{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. $◻$

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

• Nicht jede zirkulare Primzahl ist eine permutierbare Primzahl.

Beweis:

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

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.

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

• 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 $b=3$, weil für $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):

7, 1013, 3121, 211, 13143449029, 16244441, 4717103, 999331, 378470237117827, 2894561 … (Vorlage:OEIS)

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

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 $b=3$, ohne die einstelligen Trivialfälle):

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

Beispiel:

Sei $b=8$. Dann gibt die erste obige Liste an, dass die Zahl $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 $b=8$ als $p=75757331_8$ schreibt. Aus der dritten Liste kann man ablesen, dass es insgesamt wahrscheinlich genau 141 zirkulare Primzahlen zur Basis $b=8$ gibt, die nicht gleichzeitig Repunits sind.

Weblinks

• Vorlage:MathWorld
• Vorlage:Internetquelle