Lucas-Folge

Unter der Lucas-Folge versteht man zwei unterschiedliche Dinge:

• Einerseits die Folge der Lucas-Zahlen

2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, … (Folge A000032 in OEIS)

bei der jedes Folgenglied (ab dem dritten) die Summe der beiden vorhergehenden ist.

• Andererseits die beiden allgemeinen Lucas-Folgen ${\displaystyle U_{n}(P,Q)}$ und ${\displaystyle V_{n}(P,Q)}$, die abhängig von den Parametern ${\displaystyle P}$ und ${\displaystyle Q}$ als diejenigen Folgen definiert sind, die

${\displaystyle U_{0}=0,\quad U_{1}=1}$ bzw. ${\displaystyle V_{0}=2,\quad V_{1}=P}$

erfüllen und den Rekursionsformeln

${\displaystyle U_{n}=PU_{n-1}-QU_{n-2}\,}$ bzw. ${\displaystyle V_{n}=PV_{n-1}-QV_{n-2}\,}$

für ${\displaystyle n>1}$ genügen.

Die Lucas-Folgen sind nach dem französischen Mathematiker Édouard Lucas benannt, der sich als erster mit ihnen beschäftigt hat.

Beispiele

• Sei ${\displaystyle P=1}$ und ${\displaystyle Q=-1}$. Dann ist ${\displaystyle U_{n}(P,Q)=U_{n}(1,-1)}$ die folgende Folge:

${\displaystyle U_{0}=0,U_{1}=1,}$

${\displaystyle U_{2}=PU_{1}-QU_{0}=1\cdot 1-(-1)\cdot 0=1,}$

${\displaystyle U_{3}=PU_{2}-QU_{1}=1\cdot 1-(-1)\cdot 1=2,}$

${\displaystyle U_{4}=PU_{3}-QU_{2}=1\cdot 2-(-1)\cdot 1=3,}$

${\displaystyle U_{5}=PU_{4}-QU_{3}=1\cdot 3-(-1)\cdot 2=5,\ldots }$

Kurz geschrieben erhält man die Fibonacci-Folge:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, … (Folge A000045 in OEIS)

• Sei ${\displaystyle P=1}$ und ${\displaystyle Q=-1}$. Dann ist ${\displaystyle V_{n}(P,Q)=V_{n}(1,-1)}$ die folgende Folge:

${\displaystyle V_{0}=2,V_{1}=P=1,}$

${\displaystyle V_{2}=PV_{1}-QV_{0}=1\cdot 1-(-1)\cdot 2=3,}$

${\displaystyle V_{3}=PV_{2}-QV_{1}=1\cdot 3-(-1)\cdot 1=4,}$

${\displaystyle V_{4}=PV_{3}-QV_{2}=1\cdot 4-(-1)\cdot 3=7,}$

${\displaystyle V_{5}=PV_{4}-QV_{3}=1\cdot 7-(-1)\cdot 4=11,\ldots }$

Kurz geschrieben erhält man eine Folge, die man ebenfalls kurz spezielle Lucas-Folge (oder noch einfacher nur Lucas-Folge) nennt, nämlich:

2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, 24476, 39603, 64079, 103682, … (Folge A000032 in OEIS)

Die einzelnen Zahlen dieser Folge nennt man Lucas-Zahlen, auf die weiter unten näher eingegangen wird.

• In einer Tabelle zusammengefasst erhält man für gewisse Startwerte für ${\displaystyle P}$ und ${\displaystyle Q}$ die Tabelle im Abschnitt Spezialfälle.

Explizite Formeln

Vorbereitung

Zur Bestimmung der Folgenglieder der allgemeinen Lucas-Folge muss vorbereitend die zugeordnete quadratische Gleichung gelöst werden.

Für die expliziten Formeln werden die beiden Lösungen ${\displaystyle a}$ und ${\displaystyle b}$ der quadratischen Gleichung ${\displaystyle x^{2}-Px Q=0\ }$ benötigt. Es sind dies

${\displaystyle a={\frac {P}{2}} {\sqrt {{\frac {P^{2}}{4}}-Q}}={\frac {P {\sqrt {P^{2}-4Q}}}{2}}}$

und

${\displaystyle b={\frac {P}{2}}-{\sqrt {{\frac {P^{2}}{4}}-Q}}={\frac {P-{\sqrt {P^{2}-4Q}}}{2}}}$

Ist ${\displaystyle P^{2}-4Q<0}$, so ist eine der beiden komplexen Wurzeln zu wählen. Welche der beiden Zahlen ${\displaystyle a}$ und welche ${\displaystyle b}$ genannt wird, ist hierbei nicht von Belang.

Die Parameter ${\displaystyle P}$ und ${\displaystyle Q}$ und die Werte ${\displaystyle a}$ und ${\displaystyle b}$ sind voneinander abhängig, es gilt umgekehrt

${\displaystyle P=a b,\quad Q=a\cdot b.}$ (Satz von Vieta)

Die Formeln für ${\displaystyle a}$ und ${\displaystyle b}$ lassen sich in Bezug auf die Potenzen verallgemeinern. Und zwar gilt:

${\displaystyle a^{n}={\frac {V_{n} U_{n}{\sqrt {P^{2}-4Q}}}{2}}\,}$

${\displaystyle b^{n}={\frac {V_{n}-U_{n}{\sqrt {P^{2}-4Q}}}{2}}\,}$

Die allgemeinen Lucas-Folgen

Falls ${\displaystyle P^{2}-4Q\neq 0}$ gilt, oder äquivalent dazu: falls die Zahlen ${\displaystyle a}$ und ${\displaystyle b}$ verschieden sind, so berechnet sich das Glied der allgemeinen Lucas-Folge ${\displaystyle U_{n}(P,Q)\ }$ nach folgender Formel:

${\displaystyle U_{n}(P,Q)={\frac {a^{n}-b^{n}}{a-b}}}$

für alle ${\displaystyle n\geq 0}$. Im Spezialfall ${\displaystyle P^{2}-4Q=0}$ gilt stattdessen

${\displaystyle U_{n}(P,Q)=na^{n-1}=n\left({\frac {P}{2}}\right)^{n-1}.}$

Das Glied der allgemeinen Lucas-Folge ${\displaystyle V_{n}(P,Q)\ }$ berechnet sich nach folgender Formel:

${\displaystyle V_{n}(P,Q)=a^{n} b^{n}\ }$

für alle ${\displaystyle n\geq 0}$

Beziehungen zwischen den Folgegliedern

Eine Auswahl der Beziehungen zwischen den Folgengliedern ist:

• ${\displaystyle U_{2n}=U_{n}\cdot V_{n}\ }$
• ${\displaystyle V_{n}=U_{n 1}-QU_{n-1}\ }$
• ${\displaystyle V_{2n}=V_{n}^{2}-2Q^{n}\ }$
• ${\displaystyle \operatorname {ggT} (U_{m},U_{n})=U_{\operatorname {ggT} (m,n)}}$, falls ${\displaystyle \operatorname {ggT} (P,Q)=1}$
• ${\displaystyle m\mid n\implies U_{m}\mid U_{n}}$; für alle ${\displaystyle U_{m}\neq 1}$

Spezialfälle

Es folgen ein paar Spezialfälle, die zu Folgen führen, die in der Mathematik eine wichtige Rolle spielen und deswegen sogar eigene Namen haben:

Es gibt aber auch viele weitere Spezialfälle, die zu Folgen führen, die einen OEIS-Eintrag haben und somit in der Mathematik ebenfalls eine gewisse Rolle spielen. Es folgen ein paar Beispiele:

Die allgemeinen Lucas-Folgen U(P,Q), V(P,Q) und die Primzahlen

Die allgemeinen Lucas-Folgen ${\displaystyle U(P,Q)\,}$ und ${\displaystyle V(P,Q)\,}$ haben für ganzzahlige Parameter ${\displaystyle P}$ und ${\displaystyle Q}$ eine spezielle Eigenschaft hinsichtlich der Teilbarkeit durch Primzahlen. Diese Eigenschaft wurde für Verfahren zur Bestimmung der Primalität einer Zahl angewandt (siehe auch Lucas-Lehmer-Test).

Die Folgen U(P,Q)

Für alle Lucas-Folgen ${\displaystyle U_{n}(P,Q)={\frac {a^{n}-b^{n}}{a-b}}}$ gilt:

Ist p eine Primzahl, so ist ${\displaystyle U_{p}(P,Q)-\left({\frac {D}{p}}\right)}$ durch p teilbar.

Dabei ist ${\displaystyle \left({\frac {D}{p}}\right)}$ das Legendre-Symbol.

Es existieren auch zusammengesetzte Zahlen, die diese Bedingung erfüllen. Diese Zahlen nennt man Lucas-Pseudoprimzahlen.

Die Folgen V(P,Q)

Für alle Lucas-Folgen ${\displaystyle V_{n}(P,Q)=a^{n} b^{n}\ }$ gilt:

Ist p eine Primzahl, so ist ${\displaystyle V_{p}(P,Q)-P\ }$ durch ${\displaystyle p}$ teilbar.

Eine zusammengesetzte Zahl, die diese Bedingung (im Fall von ${\displaystyle P>0}$ und ${\displaystyle Q=\pm 1}$) erfüllt, heißt Fibonacci-Pseudoprimzahl.

Besonders interessant ist die Teilbarkeitsbedingung für die Folge ${\displaystyle V_{n}(3,2)=a^{n} b^{n}=2^{n} 1\ }$. Für diese Folge gilt nämlich:

Wenn ${\displaystyle n}$ eine Primzahl ist, dann gilt: ${\displaystyle n}$ teilt ${\displaystyle 2^{n} 1-3=2^{n}-2\ }$.

Dies ist eine spezielle Form des kleinen Fermatschen Satz.

Analog zu ${\displaystyle a^{p}\equiv a\mod p}$ gilt hier ${\displaystyle V_{p}(a 1,a)\equiv V_{1}(a 1,a)\mod p}$.

Die spezielle Lucas-Folge

Die allgemein als Lucas-Folge bekannte Folge ${\displaystyle L_{n}}$ der Lucas-Zahlen 2, 1, 3, 4, 7, 11, 18, 29, … lässt sich außer durch die Rekursion ${\displaystyle L_{n}=L_{n-1} L_{n-2}}$ mit den Anfangswerten ${\displaystyle L_{0}=2}$ und ${\displaystyle L_{1}=1}$ auch wie folgt erzeugen:

1. Wie im allgemeinen Fall für die Folgen ${\displaystyle V_{n}}$ erwähnt, über die Formel von Binet (nach Jacques Philippe Marie Binet):

   ${\displaystyle L_{n}=\left({\frac {1 {\sqrt {5}}}{2}}\right)^{n} \left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}}$, da ${\displaystyle a={\frac {1 {\sqrt {5}}}{2}}}$ und ${\displaystyle b={\frac {1-{\sqrt {5}}}{2}}}$ gilt. a ist übrigens die goldene Zahl ${\displaystyle \Phi }$.

2. Eine andere rekursive Formel (mit Gaußklammer):

   ${\displaystyle L_{n 1}=\left\lfloor {\frac {L_{n}(1 {\sqrt {5}}) 1}{2}}\right\rfloor }$

3. Als Summe zweier Glieder der Fibonacci-Folge:

   ${\displaystyle L_{n}=f_{n-1} f_{n 1}\ }$ .

Nach 1) lässt sich alternativ auch ${\displaystyle L_{n}=\Phi ^{n} (1-\Phi )^{n}}$ schreiben. Da für ${\displaystyle n>1}$ der Betrag von ${\displaystyle (1-\Phi )^{n}}$ stets kleiner 0,5 ist, ergibt sich die Eigenschaft, dass die ${\displaystyle n}$-te (${\displaystyle n>1}$) Lucaszahl dem gerundeten Wert der Golden Zahl zur Potenz ${\displaystyle n}$ entspricht: ${\displaystyle L_{n}=\left\lfloor {\Phi ^{n} {\frac {1}{2}}}\right\rfloor }$.

Reziproke Reihe

Der Grenzwert der absolut konvergierenden reziproken Reihe spezieller Lucas-Zahlen

• ${\displaystyle \sum _{n=0}^{\infty }{\frac {1}{L_{2^{n}}}}}$

ist irrational.

Lucas-Primzahlen

Eine Lucas-Primzahl ist eine Lucas-Zahl, die prim ist. Die kleinsten Lucas-Primzahlen lauten:

2, 3, 7, 11, 29, 47, 199, 521, 2207, 3571, 9349, 3010349, 54018521, 370248451, 6643838879, 119218851371, 5600748293801, 688846502588399, 32361122672259149, 412670427844921037470771, … (Folge A005479 in OEIS)

Für diese Lucas-Primzahlen ist der Index ${\displaystyle n}$ von ${\displaystyle L_{n}}$ der folgende:

0, 2, 4, 5, 7, 8, 11, 13, 16, 17, 19, 31, 37, 41, 47, 53, 61, 71, 79, 113, 313, 353, 503, 613, 617, 863, 1097, 1361, 4787, 4793, 5851, 7741, 8467, 10691, 12251, 13963, 14449, 19469, 35449, 36779, 44507, 51169, 56003, 81671, 89849, 94823, 140057, 148091, 159521, 183089, 193201, 202667, 344293, 387433, 443609, 532277, 574219, 616787, 631181, 637751, 651821, 692147, 901657, 1051849, … (Folge A001606 in OEIS)

Beispiel:

Es ist ${\displaystyle L_{6}=18}$ und ${\displaystyle L_{5}=11}$. Somit ist ${\displaystyle L_{7}=L_{6} L_{5}=18 11=29\in \mathbb {P} }$ eine Primzahl. Tatsächlich taucht der Index ${\displaystyle n=7}$ in obiger Liste an der 5. Stelle auf, weil er zur fünftkleinsten Lucas-Primzahl ${\displaystyle L_{7}=29}$ führt.

Es gelten folgende zwei Eigenschaften für Lucas-Primzahlen:

• Wenn ${\displaystyle L_{n}}$ eine Primzahl ist, dann ist der Index ${\displaystyle n}$ entweder gleich ${\displaystyle 0}$ oder eine selbst Primzahl oder eine Zweierpotenz.
• ${\displaystyle L_{2^{m}}}$ ist eine Primzahl für ${\displaystyle m\in \{1,2,3,4\}}$. Für keine anderen bekannten Werte von ${\displaystyle m}$ erhält man weitere Primzahlen.

Es wird vermutet, dass es unendlich viele Lucas-Primzahlen gibt.

Zusammenhang zur Artinschen Konstante

Die Artinsche Konstante, benannt nach Emil Artin, ist definiert durch

${\displaystyle C_{\mathrm {Artin} }=\prod _{p\ {\text{Primzahl}}}\left(1-{\frac {1}{p(p-1)}}\right)=\left(1-{\frac {1}{2\cdot 1}}\right)\left(1-{\frac {1}{3\cdot 2}}\right)\left(1-{\frac {1}{5\cdot 4}}\right)\cdots =0{,}3739558136\ldots .}$

Dabei bezeichnet ${\displaystyle \textstyle \prod }$ das Produktsymbol, wobei sich das Produkt über alle Primzahlen erstreckt. Die Konstante ${\displaystyle C_{\mathrm {Artin} }}$ taucht in einer tiefen Vermutung von Artin über die asymptotische Dichte von Primzahlen, die Primitivwurzeln zu einer gegebenen Zahl sind, auf. Eine Primitivwurzel zu einer Primzahl ${\displaystyle p}$ ist eine ganze Zahl, deren Potenzen, bis auf Vielfache von ${\displaystyle p}$, alle Zahlen zwischen ${\displaystyle 1\leq n\leq p-1}$ erzeugen können. Zum Beispiel ist ${\displaystyle 3}$ eine Primitivwurzel bezüglich ${\displaystyle p=5}$, denn die ersten echten Potenzen der ${\displaystyle 3}$ sind ${\displaystyle 3,9,27,81}$ und bis auf Vielfache von ${\displaystyle 5}$ entspricht dies den Zahlen ${\displaystyle 3,4,2,1}$. Die Artinsche Vermutung besagt, grob gesprochen, dass zu festem ${\displaystyle a}$ die Menge der Primzahlen, so dass ${\displaystyle a}$ eine Primitivwurzel zu ${\displaystyle p}$ ist, die asymptotische Dichte ${\displaystyle C_{\mathrm {Artin} }}$ innerhalb aller Primzahlen hat. Also haben ca. 37 % der Primzahlen diese Eigenschaft, unabhängig von ${\displaystyle a}$. Jedoch muss ${\displaystyle a}$ dafür bestimmte Voraussetzungen erfüllen.

Bezeichnet ${\displaystyle L_{n}}$ die ${\displaystyle n}$-te Lucas-Zahl, so gilt die Formel

${\displaystyle C_{\mathrm {Artin} }=\prod _{n=2}^{\infty }\zeta (n)^{-{\frac {1}{n}}\sum _{k|n}L_{k}\mu \left({\frac {n}{k}}\right)}={\frac {1}{\zeta (2)\zeta (3)\zeta (4)\zeta (5)^{2}\zeta (6)^{2}\zeta (7)^{4}\zeta (8)^{5}\zeta (9)^{8}\cdots }}.}$

Dabei bedeutet ${\displaystyle k|n}$ in der Summe, dass ${\displaystyle k>0}$ die Zahl ${\displaystyle n}$ teilt, und es ist ${\displaystyle \mu }$ die Möbiusfunktion sowie ${\displaystyle \zeta }$ die Riemannsche Zeta-Funktion.

Siehe auch

• lineare Differenzengleichung

Literatur

• Paulo Ribenboim: Die Welt der Primzahlen. Springer Verlag, 1996

Weblinks

• Eric W. Weisstein: Lucas Number. In: MathWorld (englisch).
• Eric W. Weisstein: Lucas Sequence. In: MathWorld (englisch).

Einzelnachweise