Leylandsche Zahl

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Leylandsche Primzahl)
Zur Navigation springen Zur Suche springen

In der Zahlentheorie ist eine Leylandsche Zahl eine positive ganze Zahl [1] der Form

mit und und ,

Würde man auf die Bedingung und verzichten, könnte man jede natürliche Zahl in der Form darstellen, womit jede Zahl eine Leylandsche Zahl wäre.

Mitunter verlangt man noch die zusätzliche Bedingung , damit man eine eindeutige Darstellung der Leylandschen Zahlen erhält (sonst hätte man mit zwei leicht unterschiedliche Darstellungen).

Eine prime Leylandsche Zahl nennt man Leylandsche Primzahl.

Die Leylandschen Zahlen wurden nach dem Mathematiker Paul Leyland benannt.

  • Die ersten Leylandschen Zahlen sind die folgenden:
8, 17, 32, 54, 57, 100, 145, 177, 320, 368, 512, 593, 945, 1124, 1649, 2169, 2530, 4240, 5392, 6250, 7073, 8361, 16580, 18785, 20412, 23401, 32993, 60049, 65792, 69632, 93312, 94932, 131361, 178478, 262468, 268705, 397585, 423393, 524649, 533169, … (Folge A076980 in OEIS)
In der obigen OEIS-Folge A076980 wird auch noch die Zahl angegeben, welche die Darstellung hat. Nur ist wegen diese Zahl keine Leylandsche Zahl.
Die ersten Leylandschen Zahlen haben die folgende Darstellung:
, , , , , , , , …
  • Die ersten Leylandschen Primzahlen sind die folgenden (die Primzahl gehört wieder nicht dazu):
17, 593, 32993, 2097593, 8589935681, 59604644783353249, 523347633027360537213687137, 43143988327398957279342419750374600193, 4318114567396436564035293097707729426477458833, 5052785737795758503064406447721934417290878968063369478337, … (Folge A094133 in OEIS)
Dabei haben die ersten Leylandschen Primzahlen die folgende Darstellung:[2]
, , , , , , , , …
  • Wenn man die zweite Basis fix lässt, erhält man für die erste Basis genau dann eine Leylandsche Primzahl, wenn eine der folgenden Zahlen ist:
3, 9, 15, 21, 33, 2007, 2127, 3759, 29355, 34653, 57285, 99069, … (Folge A064539 in OEIS)
Diese Primzahlen haben somit alle die Form . Wieder gehört die Primzahl eigentlich nicht dazu, weil sie wegen keine Leylandsche Primzahl ist.
  • Die bis zum November 2012 größte bekannte Leylandsche Primzahl war . Sie wurde am 15. Oktober 2010 als Primzahl mit dem Programm fastECPP erkannt. Als mögliche Primzahl (probable prime, PRP) war sie schon länger bekannt. Sie hat Stellen.[3][4] Sie war bei ihrer Entdeckung die bis dahin größte Primzahl, die mit elliptischen Kurven gefunden wurde (daher der Name des Programms: Elliptic Curve Primality Proving - ECPP).
  • Am 11. Dezember 2012 wurde die momentan (Stand: 15. Juni 2018) größte bekannte Leylandsche Primzahl entdeckt, nämlich . Sie hat Stellen. Als mögliche Primzahl (PRP) wurde sie von Anatoly F. Selevich entdeckt, als Primzahl erkannt wurde sie mit dem Programm CIDE (von J. Franke, T. Kleinjung, A. Decker, J. Ecknig und A. Großwendt).[5][6]
  • Es gibt noch mindestens 2495 größere mögliche Primzahlen mit mehr als 10000 Stellen, welche Leyland-Primzahlen sein könnten. Die momentan größte ist mit Stellen, die von Ryan Propper im Mai 2023 entdeckt wurde (Stand: 21. Juni 2023).[7] Als mögliche Primzahl (PRP) wurde sie schon erkannt, man muss aber noch beweisen, dass sie tatsächlich eine Primzahl ist.

Leylandsche Primzahlen haben keine geeignete Form, mittels der man mit einfachen (bekannten) Algorithmen feststellen kann, ob sie prim sind oder nicht. Wie schon weiter oben erwähnt, ist es relativ leicht, festzustellen, dass sie mögliche Primzahlen sind (PRP), aber die Primalität definitiv zu beweisen, ist sehr schwierig. Deswegen sind Leylandsche Primzahlen ideale Testfälle für allgemeine Primalitätsnachweise. Zum Beispiel gibt es zum Prüfen von Fermat-Zahlen mit der Form den Lucas-Test und den Pépin-Test, welche genau solche Zahlen besonders schnell auf ihre Primalität testen können. Bei Leylandschen Primzahlen gibt es keine solchen speziell auf sie zugeschneiderten Tests.

Leylandsche Zahlen der 2. Art

[Bearbeiten | Quelltext bearbeiten]

In der Zahlentheorie ist eine Leylandsche Zahl der 2. Art eine positive ganze Zahl der Form

mit und und ,

Eine prime Leylandsche Zahl der 2. Art nennt man Leylandsche Primzahl der 2. Art.

  • Die ersten Leylandschen Zahlen der 2. Art sind die folgenden:
0, 1, 7, 17, 28, 79, 118, 192, 399, 431, 513, 924, 1844, 1927, 2800, 3952, 6049, 7849, 8023, 13983, 16188, 18954, 32543, 58049, 61318, 61440, 65280, 130783, 162287, 175816, 255583, 261820, 357857, 523927, 529713, 1038576, 1048176, … (Folge A045575 in OEIS)
Die ersten Leylandschen Zahlen der 2. Art haben die folgende Darstellung:
, , , , , , , , , …
  • Die ersten Leylandschen Primzahlen der 2. Art sind die folgenden:
7, 17, 79, 431, 58049, 130783, 162287, 523927, 2486784401, 6102977801, 8375575711, 13055867207, 83695120256591, 375700268413577, 2251799813682647, 9007199254738183, 79792265017612001, 1490116119372884249, … (Folge A123206 in OEIS)
Die ersten Leylandschen Primzahlen der 2. Art haben die folgende Darstellung:
, , , , , , , , …
  • Die kleinsten Leylandschen Primzahlen der 2. Art, also der Form mit wachsendem sind die folgenden (dabei ist der Wert , falls es keine solche Primzahl gibt):
1, 7, 17, 1, 6102977801, 162287, 79792265017612001, 8375575711, 2486784401, … (Folge A122735 in OEIS)
Die dazugehörenden -Werte sind die folgenden
0, 5, 4, 0, 14, 7, 20, 11, 10, 273, 14, 13, 38, 89, 68, 0, … (Folge A128355 in OEIS)
Beispiele: An der jeweils fünften Stelle der beiden oberen Zahlenfolgen steht bzw. , das heißt . An der vierten Stelle steht bzw. , das heißt, es gibt keine Leylandsche Primzahl der Form (weil per Definition keine Leylandsche Primzahl ist).
Ungelöstes Problem: Ab der 17. Stelle der -Werte der OEIS-Folge A128355 kennt man gewisse -Werte noch nicht. An folgenden Stellen sind die -Werte noch unbekannt:
17, 18, 22, 25, 26, 27, 28, …
Beispiel: Es ist noch unbekannt, ob es Primzahlen der Form oder der Form etc. gibt.
  • Es gibt mindestens 1679 mögliche Primzahlen mit mehr als 10000 Stellen, welche Leyland-Primzahlen der 2. Art sein könnten, die also derzeit einen PRP-Status haben. Die momentan größte ist mit Stellen, die von Henri Lifchitz im Januar 2021 entdeckt wurde.[8] Als mögliche Primzahl (PRP) wurde sie schon erkannt, man muss aber noch beweisen, dass sie tatsächlich eine Primzahl ist.
  • Sei die Anzahl der Leylandschen Zahlen der 2. Art kleiner oder gleich . Dann gilt:[9][10]

Es gibt ein Projekt mit dem Namen „XYYXF“, das sich mit der Faktorisierung von möglicherweise zusammengesetzten Leylandschen Zahlen beschäftigt.[7] Dasselbe Projekt beschäftigt sich auch mit Faktorisierung von möglicherweise zusammengesetzten Leylandschen Zahlen der 2. Art.[8]

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Siehe dazu Element (Mathematik).
  2. Paul Leyland: Primes and Strong Pseudoprimes of the form xy + yx. Archiviert vom Original (nicht mehr online verfügbar) am 10. Februar 2007; abgerufen am 14. Juni 2018.
  3. Chris K.Caldwell: The Largest Known Primes! 6753^5122+5122^6753. Prime Pages, abgerufen am 14. Juni 2018.
  4. Chris K.Caldwell: The Top Twenty: Elliptic Curve Primality Proof. Prime Pages, abgerufen am 14. Juni 2018.
  5. Mihailescu's CIDE. mersenneforum.org, abgerufen am 14. Juni 2018.
  6. Andrey Kulsha: Factorizations of xy + yx for 1<y<x<151. mersenneforum.org, abgerufen am 14. Juni 2018.
  7. a b Henri Lifchitz, Renaud Lifchitz: PRP Top Records - Search for : xy + yx. PRP Records, abgerufen am 21. Juni 2023.
  8. a b Henri Lifchitz, Renaud Lifchitz: PRP Top Records - Search for : xy – yx. PRP Records, abgerufen am 19. September 2022.
  9. Neil J. A. Sloane: Comments zu “Nonnegative numbers of the form x^y - y^x, for x,y > 1.” OEIS, abgerufen am 15. Juni 2018.
  10. Michael Waldschmidt: Perfect Powers: Pillai’s works and their developments. OEIS, abgerufen am 15. Juni 2018.