Leylandsche Zahl

In der Zahlentheorie ist eine Leylandsche Zahl eine positive ganze Zahl ${\displaystyle n\in \mathbb {N} }$^[1] der Form

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

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

Mitunter verlangt man noch die zusätzliche Bedingung ${\displaystyle x\geq y>1}$, damit man eine eindeutige Darstellung der Leylandschen Zahlen erhält (sonst hätte man mit ${\displaystyle 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 (en) 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 ${\displaystyle 3}$ angegeben, welche die Darstellung ${\displaystyle 3=2^{1}+1^{2}}$ hat. Nur ist wegen ${\displaystyle y=1\not >1}$ diese Zahl keine Leylandsche Zahl.

Die ersten Leylandschen Zahlen haben die folgende Darstellung:

${\displaystyle 8=2^{2}+2^{2}}$, ${\displaystyle 17=3^{2}+2^{3}}$, ${\displaystyle 32=4^{2}+2^{4}}$, ${\displaystyle 54=3^{3}+3^{3}}$, ${\displaystyle 57=5^{2}+2^{5}}$, ${\displaystyle 100=6^{2}+2^{6}}$, ${\displaystyle 145=4^{3}+3^{4}}$, ${\displaystyle 177=7^{2}+2^{7}}$, …

• Die ersten Leylandschen Primzahlen sind die folgenden (die Primzahl ${\displaystyle 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:^[2]

${\displaystyle 17=3^{2}+2^{3}}$, ${\displaystyle 593=9^{2}+2^{9}}$, ${\displaystyle 32993=15^{2}+2^{15}}$, ${\displaystyle 2097593=21^{2}+2^{21}}$, ${\displaystyle 8589935681=33^{2}+2^{33}}$, ${\displaystyle 59604644783353249=24^{5}+5^{24}}$, ${\displaystyle 523347633027360537213687137=56^{3}+3^{56}}$, ${\displaystyle 43143988327398957279342419750374600193=32^{15}+15^{32}}$, …

• Wenn man die zweite Basis ${\displaystyle y=2}$ fix lässt, erhält man für die erste Basis ${\displaystyle x}$ genau dann eine Leylandsche Primzahl, wenn ${\displaystyle 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 ${\displaystyle p=x^{2}+2^{x}}$. Wieder gehört die Primzahl ${\displaystyle 3=1^{2}+2^{1}}$ eigentlich nicht dazu, weil sie wegen ${\displaystyle x=1\not >1}$ keine Leylandsche Primzahl ist.

• Die bis zum November 2012 größte Leylandsche Primzahl war ${\displaystyle 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 ${\displaystyle 25050}$ 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 ${\displaystyle 8656^{2929}+2929^{8656}}$. Sie hat ${\displaystyle 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).^[5][6]
• Es gibt noch mindestens 594 größere mögliche Primzahlen, welche Leyland-Primzahlen sein könnten. Die momentan größten sind ${\displaystyle 314738^{9}+9^{314738}}$ mit ${\displaystyle 300337}$ Stellen (von Anatoly F. Selevich entdeckt) und ${\displaystyle 328574^{15}+15^{328574}}$ mit ${\displaystyle 386434}$ Stellen (von Serge Batalov entdeckt).^[6][7] Als mögliche Primzahlen (PRP) wurden sie schon erkannt, man muss aber noch beweisen, dass sie tatsächlich Primzahlen sind.

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 ${\displaystyle 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 ${\displaystyle n\in \mathbb {N} }$ der Form

${\displaystyle n=x^{y}-y^{x}}$ mit ${\displaystyle x\in \mathbb {N} }$ und ${\displaystyle y\in \mathbb {N} }$ und ${\displaystyle x>1}$, ${\displaystyle 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:

${\displaystyle 0=2^{2}-2^{2}}$, ${\displaystyle 1=3^{2}-2^{3}}$, ${\displaystyle 7=2^{5}-5^{2}}$, ${\displaystyle 17=3^{4}-4^{3}}$, ${\displaystyle 28=2^{6}-6^{2}}$, ${\displaystyle 79=2^{7}-7^{2}}$, ${\displaystyle 118=3^{5}-5^{3}}$, ${\displaystyle 192=2^{8}-8^{2}}$, ${\displaystyle 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:

${\displaystyle 7=2^{5}-5^{2}}$, ${\displaystyle 17=3^{4}-4^{3}}$, ${\displaystyle 79=2^{7}-7^{2}}$, ${\displaystyle 431=2^{9}-9^{2}}$, ${\displaystyle 58049=3^{10}-10^{3}}$, ${\displaystyle 130783=2^{17}-17^{2}}$, ${\displaystyle 162287=6^{7}-7^{6}}$, ${\displaystyle 523927=2^{19}-19^{2}}$, …

• Die kleinsten Leylandschen Primzahlen der 2. Art, also der Form ${\displaystyle x^{y}-y^{x}}$ mit wachsendem ${\displaystyle x=1,2,\ldots }$ sind die folgenden (dabei ist der Wert ${\displaystyle 1}$, falls es keine solche Primzahl gibt):

1, 7, 17, 1, 6102977801, 162287, 79792265017612001, 8375575711, 2486784401, … (Folge A122735 in OEIS)

Die dazugehörenden ${\displaystyle 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 ${\displaystyle 6102977801}$ bzw. ${\displaystyle 14}$, das heißt ${\displaystyle 6102977801=5^{14}-14^{5}}$. An der vierten Stelle steht ${\displaystyle 1}$ bzw. ${\displaystyle 0}$, das heißt, es gibt keine Leylandsche Primzahl der Form ${\displaystyle 4^{y}-y^{4}}$ (weil ${\displaystyle 4^{1}-1^{4}=3}$ per Definition keine Leylandsche Primzahl ist).

Ungelöstes Problem: Ab der 17. Stelle der ${\displaystyle y}$-Werte der OEIS-Folge A128355 kennt man gewisse ${\displaystyle y}$-Werte noch nicht. An folgenden Stellen sind die ${\displaystyle y}$-Werte noch unbekannt:

17, 18, 22, 25, 26, 27, 28, …

Beispiel: Es ist noch unbekannt, ob es Primzahlen der Form ${\displaystyle x^{17}-17^{x}}$ oder der Form ${\displaystyle x^{26}-26^{x}}$ etc. gibt.

• Es gibt mindestens 1255 mögliche Primzahlen, welche Leyland-Primzahlen der 2. Art sein könnten, die also derzeit einen PRP-Status haben. Die momentan größten sind ${\displaystyle 14^{161089}-161089^{14}}$ mit ${\displaystyle 184629}$ Stellen (von Serge Batalov entdeckt) und ${\displaystyle 2^{608541}+608541^{2}}$ mit ${\displaystyle 183190}$ Stellen (von Henri Lifchitz entdeckt).^[8] Als mögliche Primzahlen (PRP) wurden sie schon erkannt, man muss aber noch beweisen, dass sie tatsächlich Primzahlen sind.

Eigenschaften

• Sei ${\displaystyle N(x)}$ die Anzahl der Leylandschen Zahlen der 2. Art kleiner oder gleich ${\displaystyle x}$. Dann gilt:^[9][10]

${\displaystyle 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.^[7] Dasselbe Projekt beschäftigt sich auch mit Faktorisierung von möglicherweise zusammengesetzten Leylandschen Zahlen der 2. Art.^[8]

Einzelnachweise

1. ↑ Siehe dazu Element (Mathematik).
2. ↑ Paul Leyland: Primes and Strong Pseudoprimes of the form x^y + y^x. (Nicht mehr online verfügbar.) Archiviert vom Original am 10. Februar 2007; abgerufen am 14. Juni 2018.  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/www.leyland.vispa.com 
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. ↑ ^{a b} Andrey Kulsha: Factorizations of x^y + y^x for 1<y<x<151. mersenneforum.org, abgerufen am 14. Juni 2018. 
7. ↑ ^{a b} Henri Lifchitz, Renaud Lifchitz: PRP Top Records - Search for : x^y + y^x. PRP Records, abgerufen am 14. Juni 2018. 
8. ↑ ^{a b} Henri Lifchitz, Renaud Lifchitz: PRP Top Records - Search for : x^y – y^x. PRP Records, abgerufen am 15. Juni 2018. 
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. 

Weblinks

• Leyland number. In: PlanetMath. (englisch)
• Leyland Numbers - Numberphile auf YouTube