If you're seeing this message, it means we're having trouble loading external resources on our website.

Wenn du hinter einem Webfilter bist, stelle sicher, dass die Domänen *. kastatic.org und *. kasandbox.org nicht blockiert sind.

Hauptinhalt

Primzahlsatz

Wie können wir die Anzahl der Primzahlen bis zu x abschätzen? Erstellt von Brit Cruise

Willst du an der Diskussion teilnehmen?

Noch keine Beiträge.
Verstehst du Englisch? Klick hier, um weitere Diskussionen auf der englischen Khan Academy Seite zu sehen.

Video-Transkript

Stell dir vor, wir listen alle ganzen Zahlen in einer wachsenden Spirale auf und färben die Primzahlen blau. Derweil lassen wir Nicht-Primzahlen schwarz. Eine interessante Frage, die wir stellen könnten, ist: "Wie viele Primzahlen gibt es im Vergleich zu den Nicht-Primzahlen?" Zunächst einmal zoomen wir heraus, um es als großes Bild zu sehen. Man merkt, dass die Primzahlenfarbe im Zentrum dichter ist und in der Ferne langsam abnimmt, aber niemals zu enden scheint. Das kann man wie folgt betrachten: Stelle dir vor, es gibt in der MItte einen Baum, der unendlich hoch ist. Die Blätter, die von diesem Baum fallen, repräsentieren die Primzahlen. Sie sind unten unvorhersehbar verstreut. Alles dicht beisammen am Fuß des Baums. Wenn wir uns von diesem Baum entfernen, finden wir weniger Blätter, obwohl wir sie immer finden. Dies ist genau das, was passiert, wenn wir uns immer größere ganze Zahlen ansehen. Wir finden immer mehr Primzahlen, obwohl die Anzahl allmählich abnimmt, je weiter wir suchen. Also kehren wir zu unserer Frage zurück. Wie viele Primzahlen gibt es kleiner als eine bestimmte ganze Zahl x? Wenn wir eine Tabelle erstellen, sehen wir, dass die Anzahl der Primzahlen immer zunimmt. Obwohl wir, wenn wir weiter suchen, immer weniger finden. Lass uns die Anzahl der gefundenen Primzahlen auf der vertikalen Achse und die Suchgröße x auf der horizontalen Achse darstellen. Wenn wir herauszoomen, um Milliarden von Zahlen zu inkludieren, bemerken wir, dass die Kurve nie flach verläuft. Sie steigt immer, wenn auch allmählich. Zunächst denken wir über die Dichte der Primzahlen kleiner als eine bestimmte ganze Zahl x nach. Wir können die Dichte finden, indem wir die Anzahl der gefundenen Primzahlen durch die Suchgröße teilen. Für die ersten 100 ganzen Zahlen finden wir 25 Primzahlen. Es gibt also 25% Primzahlen. Von den ersten 10'000 ganzen Zahlen finden wir 1229 Primzahlen. Hier haben wir 12,29% Primzahlen. Von den ersten 1 Million ganzen Zahlen sind 7,84% Primzahlen. Und die ersten 100 Millionen Ganzzahlen enthalten 5,76% Primzahlen. Wenn wir weiter suchen, nimmt diese Dichte weiter ab, obwohl die Geschwindigkeit, mit der sie abnimmt, nachlässt. Hier ist ein Diagramm der Suchgröße auf der horizontalen Achse und der Primzahldichte auf der vertikalen. Beachte, dass wenn wir herauszoomen, die Primzahlen einen verschwindenden Anteil aller Ganzzahlen ausmachen. Erstaunlicherweise finden wir diese Formel in der Natur. Wir sehen sie in Galaxien, Stürmen, Blumen und sogar in unseren Körpern als das Design des geringsten Widerstands, bekannt als die logarithmische Spirale. Beachte, dass sich die Spirale bei der Drehung immer weiter vom Zentrum entfernt. Unglaublicherweise ist die Drehgeschwindigkeit einer logarithmischen Spirale wie folgt mit der Dichte der Primzahlen verbunden: Wir haben die Anzahl der Umdrehungen, nennen wir sie Phi, und den Abstand vom Zentrum, nennen wir ihn r. Wenn wir Phi im Verhältnis zu r darstellen und herauszoomen, sehen wir, dass sie gemäß dem natürlichen Logarithmus miteinander in Beziehung stehen. Das bedeutet, dass der natürliche Logarithmus der Distanz in Beziehung steht zur Anzahl der Umdrehungen. Der Graph des natürlichen Logarithmus wird normalerweise unter Verwendung der Variablennamen y und x geschrieben. So dass y gleich dem natürlichen Logarithmus von x ist. Man sieht, dass der Graph auf die gleiche Weise abflacht, wie die Dichte der Primzahlen allmählich abnimmt. Der letzte Schritt besteht darin, dies zu invertieren, indem die y-Achse zu 1 geteilt durch den natürlichen Logarithmus von x geändert wird. Und wenn wir herauszoomen, finden wir die exakt gleiche Kurve, die generiert wird, wenn wir die Dichte der Primzahlen aufzeichnen. Bestätigen wir dies, indem wir die beiden Plots überlagern. In Grün ist eine Graphik der Linie y gleich 1 über dem natürlichen Logarithmus von x. Und in Rot ist die Darstellung der Primzahldichte bis x. Wenn wir herauszoomen, nähern sie sich einander. Je weiter wir herauszoomen, desto genauer wird die grüne Schätzung. Dies ist bekannt als das asymptotische Gesetz der Verteilung von Primzahlen. Wir haben nun eine Formel, die uns genau die Dichte der Primzahlen angibt, ohne zählen zu müssen. Die Dichte der Primzahlen bis zu einer bestimmten Ganzzahl x beträgt ungefähr 1 geteilt durch den natürlichen Logarithmus von x oder ln x. Angenommen, wir müssen die Dichte der Primzahlen zwischen 1 und 100 Billionen kennen. Das ist einfach. 1 geteilt durch ln von 100 Billionen ergibt 3,1%. Verglichen mit dem tatsächlichen Ergebnis aus der Zählung aller Primzahlen, das 3,2% beträgt. Das ist eine Abweichung von 0,1 %. Und je größer die Zahlen, die wir überprüfen, desto näher kommt man zum Unterschied Null. Bedenke, dass wir diese Formel für die Primzahldichte verwenden können, um die Anzahl der Primzahlen bis x zu schätzen. Die Anzahl der Primzahlen ist die Fläche unter der Dichtekurve, die wir vereinfachen können, indem wir annehmen, dass die Dichte konstant ist. Also ist die Anzahl der Primzahlen gleich Größe mal Dichte, oder x geteilt durch ln x. Dies ist der Primzahlsatz. Hier ist ein Graph von y gleich x geteilt durch ln x in Blau, und in Gelb ist eine Darstellung der tatsächlichen Zählung von Primzahlen. Beachte, dass diese Linien schließlich übereinstimmen, wenn wir in die Unendlichkeit schauen. Und das war's. Wir haben eine Formel, die uns ungefähr sagt, wie viele Primzahlen es bis zu einem beliebigen Wert gibt, ohne zählen zu müssen. Zum Beispiel, nehmen wir an, wir müssen wissen, wie viele Primzahlen kleiner als 100 Billionen sind. 100 Billionen geteilt durch den natürlichen Logarithmus von 100 Billionen ergibt 3,1 Billionen. Vergleiche dies mit der tatsächlichen Zählung, die 3,2 Billionen beträgt. Das ist über 99,99% genau, sogar bei dieser relativ kleinen Skala. Um zusammenzufassen: Gegeben eine Suchgröße bis zu einer bestimmten Ganzzahl x, ist die Primzahldichte etwa 1 geteilt durch ln x. Und die Anzahl der Primzahlen ist etwa x geteilt durch ln x. Dies ist der Primzahlsatz.