WikiDer > Sieb von Legendre

In dem Zahlentheorie, eine Unterregion der Mathematik, ist der Sieb von Legendre (benannt nach Adrien-Marie Legendre) die einfachste Methode der modernen Siebtheorie. Es passt zum Konzept der Sieb von Eratosthenes zum obere oder untere Grenze der Zahl Primzahlen innerhalb einer gegebenen Sammlung von ganze Zahlen finden. Weil es eine einfache Erweiterung der Idee hinter der Sieb von Eratosthenes ist, wird es manchmal auch genannt Sieb von Eratosthenes-Legendre erwähnt.^[1]

Identität von Legendre

Die zentrale Idee der Methode drückt sich im Folgenden aus Identität was manchmal die Identität von Legendre wird genannt:

${displaystyle S(A,P)=sum _{ain A}sum _{dmid a;,dmid P}mu (d)=sum _{dmid P}mu (d)|A_{d}|,}$

wahr ein ist eine Menge von ganzen Zahlen, p es Produkt von den verschiedenen Primzahlen, ${Anzeigestil mu}$ das Möbius-Funktion, und ${Displaystil A_{d}}$ die Menge der ganzen Zahlen in ein ist teilbar durch d, und S(A, P) ist definiert als:

${Anzeigestil S(A,P)=|{n:nin A,(n,P)=1}|}$

das ist das so(ein, p) die Anzahl der Zahlen in ein ist ohne übliche Faktoren mit p.

Beachten Sie, dass im typischsten Fall A alle ganzen Zahlen kleiner oder gleich einer reellen Zahl X ist, P das Produkt aller Primzahlen kleiner oder gleich einer ganzen Zahl z < X ist, und dann wird die Legendre-Identität:

Beachten Sie, dass im typischsten Fall ein gleich der Anzahl der ganzen Zahlen kleiner oder gleich einer beliebigen reellen Zahl X, p ist das Produkt aller Primzahlen kleiner oder gleich einer ganzen Zahl z < X. Legendres Identität wird dann

${displaystyle { egin{aligned}S(A,P)&=sum _{dmid P}mu (d)leftlfloor {frac {X}{d}}ightfloor /&=[X]-sum _{p_{1}$

(wahr ${displaystyle lfloor Xfloor }$ das Bodenfunktion zeigt an). In diesem Beispiel leitet sich die Identität von Legendre aus der Sieb von Eratosthenes klar: der erste Term ist die Anzahl der ganzen Zahlen kleiner als X, der zweite Term entfernt die Vielfaches aller Primzahlen addiert der dritte Term wieder die Vielfachen von zwei Primzahlen (diese wurden fälschlicherweise "zweimal durchgestrichen") und so weiter, bis alle

${Displaystil 2^{pi(z)}}$

Kombinationen von Primzahlen sind beendet. (${displaystyle pi(z)}$ steht für die Anzahl der Primzahlen kleiner alsz)

Wann so(ein, p) für diesen speziellen Fall kann das Ergebnis verwendet werden, um zu finden ${displaystyle pi(X)}$ begrenzt werden, indem man die Ausdruck

${Anzeigestil S(A,P)geq pi (X)-pi (z) 1,,}$

was unmittelbar aus der Definition von folgt so(ein, p).

Einschränkungen

Leider hat das Sieb von Legendre ein Problem damit, dass sich Bruchteile von Termen mit großen Fehlern ansammeln. so dass das Sieb in den meisten Fällen nur sehr schwache Grenzen gibt. Deshalb wird das Legendre-Sieb in der Praxis fast nie verwendet. Es wurde durch andere Techniken ersetzt, wie z Sieb von Brun und Sieb von Selberg. Da diese stärkeren Siebe jedoch Erweiterungen der Grundideen des Siebs von Legendre sind, ist es hilfreich, zunächst zu verstehen, wie das Sieb von Legendre funktioniert.

Fußnoten

Zitat

• Dieser Artikel oder eine frühere Version ist eine (Teil-)Übersetzung des Artikels Legendre-Sieb auf der englischsprachigen Wikipedia, die unter der Creative Commons Namensnennung/Weitergabe unter gleichen Bedingungen Stürze. Siehe die Verlauf bearbeiten Dort.