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 $p=1193$ ist im Dezimalsystem eine zirkulare Primzahl, weil man durch zyklische Vertauschung ihrer Ziffern folgende Primzahlen erhält:

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

R_{n}=11\ldots 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 Folge A004023 in 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.[2] Es gibt keine weiteren zirkularen Primzahlen, welche kleiner als

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 $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 (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 $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\ldots 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}={\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

57B1_{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.

\Box

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.

\Box

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}={\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

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}={\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.

\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.

\Box

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.

\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 $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):[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

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

b=3

, ohne die einstelligen Trivialfälle):[5]

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.

Einzelnachweise

Eric W. Weisstein: Circular Prime. In: MathWorld (englisch).
Henri Lifchitz, Renaud Lifchitz: PRP Records - Probable Primes Top 10000, Search for: (10^x-1)/9. PRP Records, abgerufen am 16. August 2021.
Patrick De Geest: Circular Primes. World Of Numbers, abgerufen am 8. Juli 2018 (englisch).
Chris K. Caldwell: Circular Prime. Prime Pages, abgerufen am 8. Juli 2018 (englisch).
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).

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Eric W. Weisstein: Circular Prime. In: MathWorld (englisch).

[PRP-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).

[PrimePages-4] Chris K. Caldwell: Circular Prime. Prime Pages, abgerufen am 8. Juli 2018 (englisch).

[Mersenneforum-5] Mersenneforum: Type of primes in various bases


formelbasiert	Carol ((2ⁿ − 1)² − 2) \| Doppelte Mersenne (2^{2^p − 1} − 1) \| Fakultät (n! ± 1) \| Fermat (2^2ⁿ + 1) \| Kubisch (x³ − y³)/(x − y) \| Kynea ((2ⁿ + 1)² − 2) \| Leyland (x^y + y^x) \| Mersenne (2^p − 1) \| Mills (A^3ⁿ) \| Pierpont (2^u⋅3^v + 1) \| Primorial (p_n# ± 1) \| Proth (k⋅2ⁿ + 1) \| Pythagoreisch (4n + 1) \| Quartisch (x⁴ + y⁴) \| Thabit (3⋅2ⁿ − 1) \| Wagstaff ((2^p + 1)/3) \| Williams ((b-1)⋅bⁿ − 1) \| Woodall (n⋅2ⁿ − 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
basisabhängig	Belphegor \| Champernowne \| Dihedral \| Einzigartig \| Fröhlich \| Keith \| Lange \| Minimal \| Mirp \| Permutierbar \| Primeval \| Palindrom \| Repunit-Primzahl ((10ⁿ − 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)