Leylandsche Zahl
# Leylandsche Zahl

In der Zahlentheorie ist eine Leylandsche Zahl eine positive ganze Zahl $n\in \mathbb {N}$ der Form

    $n=x^{y}+y^{x}$ mit $x\in \mathbb {N}$ und $y\in \mathbb {N}$ und $x>1$, $y>1$

Würde man auf die Bedingung $x>1$ und $y>1$ verzichten, könnte man jede natürliche Zahl $n\in \mathbb {N}$ in der Form $n=(n-1)^{1}+1^{n-1}$ darstellen, womit jede Zahl eine Leylandsche Zahl wäre.

Mitunter verlangt man noch die zusätzliche Bedingung $x\geq y>1$, damit man eine eindeutige Darstellung der Leylandschen Zahlen erhält (sonst hätte man mit $17=3^{2}+2^{3}=2^{3}+3^{2}$ zwei leicht unterschiedliche Darstellungen).

Eine prime Leylandsche Zahl nennt man Leylandsche Primzahl.

Die Leylandschen Zahlen wurden nach dem Mathematiker Paul Leyland benannt.

## Beispiele

* 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 $3$ angegeben, welche die Darstellung $3=2^{1}+1^{2}$ hat. Nur ist wegen $y=1\not >1$ diese Zahl keine Leylandsche Zahl.
    Die ersten Leylandschen Zahlen haben die folgende Darstellung:
       $8=2^{2}+2^{2}$, $17=3^{2}+2^{3}$, $32=4^{2}+2^{4}$, $54=3^{3}+3^{3}$, $57=5^{2}+2^{5}$, $100=6^{2}+2^{6}$, $145=4^{3}+3^{4}$, $177=7^{2}+2^{7}$, …
* Die ersten Leylandschen Primzahlen sind die folgenden (die Primzahl $3$ 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:
       $17=3^{2}+2^{3}$, $593=9^{2}+2^{9}$, $32993=15^{2}+2^{15}$, $2097593=21^{2}+2^{21}$, $8589935681=33^{2}+2^{33}$, $59604644783353249=24^{5}+5^{24}$, $523347633027360537213687137=56^{3}+3^{56}$, $43143988327398957279342419750374600193=32^{15}+15^{32}$, …
* Wenn man die zweite Basis $y=2$ fix lässt, erhält man für die erste Basis $x$ genau dann eine Leylandsche Primzahl, wenn $x$ 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 $p=x^{2}+2^{x}$. Wieder gehört die Primzahl $3=1^{2}+2^{1}$ eigentlich nicht dazu, weil sie wegen $x=1\not >1$ keine Leylandsche Primzahl ist.
* Die bis zum November 2012 größte bekannte Leylandsche Primzahl war $6753^{5122}+5122^{6753}$. 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 $25050$ Stellen. 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 $8656^{2929}+2929^{8656}$. Sie hat $30008$ 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).
* 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 $1343238^{19}+19^{1343238}$ mit $1717671$ Stellen, die von Ryan Propper im Mai 2023 entdeckt wurde (Stand: 21. Juni 2023). Als mögliche Primzahl (PRP) wurde sie schon erkannt, man muss aber noch beweisen, dass sie tatsächlich eine Primzahl ist.

### Anwendung

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 $2^{2^{n}}+1$ 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

In der Zahlentheorie ist eine Leylandsche Zahl der 2. Art eine positive ganze Zahl $n\in \mathbb {N}$ der Form

    $n=x^{y}-y^{x}$ mit $x\in \mathbb {N}$ und $y\in \mathbb {N}$ und $x>1$, $y>1$

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

### Beispiele

* 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:
       $0=2^{2}-2^{2}$, $1=3^{2}-2^{3}$, $7=2^{5}-5^{2}$, $17=3^{4}-4^{3}$, $28=2^{6}-6^{2}$, $79=2^{7}-7^{2}$, $118=3^{5}-5^{3}$, $192=2^{8}-8^{2}$, $399=4^{5}-5^{4}$, …
* 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:
       $7=2^{5}-5^{2}$, $17=3^{4}-4^{3}$, $79=2^{7}-7^{2}$, $431=2^{9}-9^{2}$, $58049=3^{10}-10^{3}$, $130783=2^{17}-17^{2}$, $162287=6^{7}-7^{6}$, $523927=2^{19}-19^{2}$, …
* Die kleinsten Leylandschen Primzahlen der 2. Art, also der Form $x^{y}-y^{x}$ mit wachsendem $x=1,2,\ldots$ sind die folgenden (dabei ist der Wert $1$, falls es keine solche Primzahl gibt):

       1, 7, 17, 1, 6102977801, 162287, 79792265017612001, 8375575711, 2486784401, … (Folge A122735 in OEIS)
    Die dazugehörenden $y$-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 $6102977801$ bzw. $14$, das heißt $6102977801=5^{14}-14^{5}$. An der vierten Stelle steht $1$ bzw. $0$, das heißt, es gibt keine Leylandsche Primzahl der Form $4^{y}-y^{4}$ (weil $4^{1}-1^{4}=3$ per Definition keine Leylandsche Primzahl ist).
    Ungelöstes Problem: Ab der 17. Stelle der $y$-Werte der OEIS-Folge A128355 kennt man gewisse $y$-Werte noch nicht. An folgenden Stellen sind die $y$-Werte noch unbekannt:
       17, 18, 22, 25, 26, 27, 28, …
          Beispiel: Es ist noch unbekannt, ob es Primzahlen der Form $x^{17}-17^{x}$ oder der Form $x^{26}-26^{x}$ 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 $2^{954127}-954127^{2}$ mit $287221$ Stellen, die von Henri Lifchitz im Januar 2021 entdeckt wurde. Als mögliche Primzahl (PRP) wurde sie schon erkannt, man muss aber noch beweisen, dass sie tatsächlich eine Primzahl ist.

### Eigenschaften

* Sei $N(x)$ die Anzahl der Leylandschen Zahlen der 2. Art kleiner oder gleich $x$. Dann gilt:

       $N(x)\approx {\frac {(\log x)^{2}}{2\cdot (\log \log x)^{2}}}$

## Sonstiges

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

