Programmieren - alles kontrollieren 4.941 Themen, 20.715 Beiträge

Verfolgung starten Optionen

Primzahlen und Wahrscheinlichkeit

Olaf19 / 6 Antworten / Baumansicht Nickles

Hallo zusammen.

Streng genommen hat dieser Thread mehr mit Zahlen-Theorie zu tun als mit Programmierung - und doch finde ich ihn hier besser aufgehoben als auf "Allgemeines".

Folgende Überlegung: Einerseits gibt es unendlich viele Primzahlen, andererseits werden die Abstände zwischen benachbarten Primzahlen mit zunehmender Größe immer weiter. Logisch, denn je höher eine Zahl, desto mehr potentielle "echte Teiler" (=Teiler der Zahl mit Ausnahme ihrer selbst und der 1) gibt es. Anders ausgedrückt: Die Wahrscheinlichkeit, daß eine "sehr, sehr hohe Zahl" (was immer man darunter versteht ;-) eine Primzahl ist, wird immer geringer. Doch wie gering kann sie werden - gegen Null tendierend? Das kann nicht sein, denn es ist ja erwiesen, daß es unendlich viele Primzahlen gibt.

Gibt es also einen endlichen Grenzwert für die Wahrscheinlichkeit von Primzahlen?

Um dieser Frage auf den Grund zu gehen, hatte ich in den späten Achtziger Jahren auf dem Atari in Omikron Basic ein Programm geschrieben, daß ich jetzt noch einmal entwickeln möchte - höchstwahrscheinlich mit QBasic (mal gucken). Dieses Programm basierte auf folgendem Prinzip: Eine Primzahl ist eine Zahl, die durch keine andere Primzahl teilbar ist - sie läßt sich nicht durch 2, nicht durch 3, nicht durch 5, nicht durch 7 usw. teilen. Die Formel für die prozentuale Wahrscheinlichkeit W lautet demnach:

W = 100% * 1/2 * 2/3 * 4/5 * 6/7 * 10/11 * ...

Diese Zahl W wird also mit zunehmender Dauer der Berechnung immer kleiner; für jede neu entdeckte Primzahl P wird sie mit (P-1) / P multipliziert. Mein Atari hat damals Tage und Nächte ununterbrochen durchgerechnet - ich weiß schon gar nicht mehr, bis zu welchem Zahlenbereich ich vorgedrungen bin. Irgendwann habe ich die Rechnerei dann abgebrochen - der Wert für die Wahrscheinlichkeit W lag zu der Zeit bei 2,98%, Tendenz immer langsamer sinkend.

Okay - das alles z.B. mit QBasic wieder neu zu Programmieren, dürfte kein Problem darstellen. Aber vielleicht weiß darüber hinaus jemand von Euch eine mathematisch-logische Antwort auf die Frage: Geht die Wahrscheinlichkeit gegen Null, daß es sich bei einer beliebigen natürlichen Zahl um eine Primzahl handelt, oder gibt es dafür einen endlichen Grenzwert?

Sorry an alle, die's gelangweilt hat. Nächstes Mal poste ich wieder was Bodenständigeres - ich versprech's ;-)))

CU
Olaf19

Die Welt ist ein Jammertal ohne Musik. Doch zum Glueck gab es Bach, Beethoven, Haendel und Goethe (Helge Schneider)
bei Antwort benachrichtigen
Borlander Olaf19 „Primzahlen und Wahrscheinlichkeit“
Optionen

Hallo Olaf,
die Wahrscheinlichkeit strebt gegen asymptotisch gegen 0, wird jedoch nie 0 werden.

Das ganz sieht ähnlich aus wie die Funktion
f(x)=1/x

Bei f(unendlich) könnte man sich allerdings drüber streiten ob der Funktionswert =0 ist. Müsste ich evtl. mal nachschlagen...

W = 100% * 1/2 * 2/3 * 4/5 * 6/7 * 10/11 * ...
Mit der Fomel kann ich mich nicht so recht anfreunden, da fehlt mir die Zahl (n) deren Primzahlwahrscheinlichkeit bestimmt werden soll

Ich dachte da eher an sowas:
w(n) = a(n)/n
w(n): Primzahlwahrscheinlichkeit der Zahl n
a(n): Anzahl der Primzahlen

CU Borlander

bei Antwort benachrichtigen
Olaf19 Borlander „Hallo Olaf, die Wahrscheinlichkeit strebt gegen asymptotisch gegen 0, wird...“
Optionen

Hi Borlander,

hat dieses Mal nicht geklappt mit der Antwort-Benachrichtigung :-((
Deswegen sehe ich Deine Antwort leider erst zwei Tage später - ich hoffe, Du liest noch mit.

> Bei f(unendlich) könnte man sich allerdings drüber streiten ob der Funktionswert =0 ist.

Genau, das ist eben das spannende an der Sache. Null darf eigentlich deswegen nicht sein, weil das hieße, daß es irgendwann keine Primzahl mehr gäbe. Was meine Formel angeht: Das war durchaus beabsichtigt, daß ich keine konkrete Zahl n angegeben habe. Mir ging es ja gerade um die Frage: Wie wahrscheinlich ist es, daß eine beliebig große, aus der Menge N der Natürlichen Zahlen gezogene Zahl eine Primzahl ist?

Ich bin mal gespannt, ob ein Programm für diese Berechnung am PC auch mehrere Tage brauchen wird, um unter drei Prozent zu kommen. Ehrlich gesagt: wundern würde mich das nicht. Atari mit 8 MHz vs. PIV 1,8 GHz - das riecht nach David gegen Goliath. Nun, in der Bibel ist David Sieger geblieben, und am Computer? Ich bin mir ziemlich sicher, mein XP Home wie auch jedes andere Windows wird es verstehen, die überschüssigen System-Ressourcen so kahlzufressen, daß nicht mehr allzu viel bleibt von der zunächst gigantisch anmutenden Mehrleistung.

CU
Olaf

Die Welt ist ein Jammertal ohne Musik. Doch zum Glueck gab es Bach, Beethoven, Haendel und Goethe (Helge Schneider)
bei Antwort benachrichtigen
Borlander Olaf19 „Hi Borlander, hat dieses Mal nicht geklappt mit der Antwort-Benachrichtigung :-...“
Optionen
ich hoffe, Du liest noch mit.
Dank Antwortbenachrichtigung ja.

Null darf eigentlich deswegen nicht sein
Wird es auch nie, nähert sich nur asymtotisch.

Ich bin mal gespannt, ob ein Programm für diese Berechnung am PC auch mehrere Tage brauchen wird, um unter drei Prozent zu kommen
Wenn Du mit BASIC arbeitest stehen die Chanchen auf jeden Fall nicht schlecht, dass es länger dauert. Wenn Du rechnest wirst Du irgendwann auch auf 0 kommen, das der Computer nicht beliebig genau rechner.


CU Borlander
bei Antwort benachrichtigen
Olaf19 Borlander „ Dank Antwortbenachrichtigung ja. Wird es auch nie, nähert sich nur...“
Optionen

Komisch, jetzt habe auch ich eine Antwort-Benachrichtigung bekommen - doch noch...
Ja, Basic ist schon ein wenig langsamer - das war es damals am Atari aber auch. Ich hatte zu der Zeit sogar noch nicht einmal die Version mit dem Compiler, was später einen ordentlichen Schub brachte. Na, ich werd's ja sehen. Danke!

Die Welt ist ein Jammertal ohne Musik. Doch zum Glueck gab es Bach, Beethoven, Haendel und Goethe (Helge Schneider)
bei Antwort benachrichtigen
Mrs. Software Olaf19 „Primzahlen und Wahrscheinlichkeit“
Optionen

Ausschnitt aus Encarta 2003, bitte alles lesen:

Primzahlen, eine Klasse von ganzen Zahlen größer als 1, die nur durch sich selbst und durch 1 teilbar sind.

Die ersten Primzahlen sind 2, 3, 5, 7, 11, 13, 17, 19, 23, … Die bisher längste Primzahl mit über vier Millionen Stellen entdeckte der kanadische Mathematiker Michael Cameron 2001. Mit Hilfe weltumspannender Netzwerke von Personalcomputern gelang es Cameron, die Primzahl folgendermaßen zu berechnen:

2^13 466 917 -1.


Im Sommer 2002 stellten die drei indischen Mathematiker Manindra Agrawal, Neeraj Kayal und Nitin Saxena (Indian Institute of Technology, Kanpur) der Fachwelt einen leistungsfähigen Algorithmus vor, mit dessen Hilfe Computer erkennen können, ob es sich bei einer Zahl um eine Primzahl handelt oder nicht

Die Berechnung der Primfaktorzerlegung wird immer aufwendiger, je größer die Zahlen sind. Schon Carl Friedrich Gauß sagt in §329 seiner Disquisitiones Arithmeticae, „dass die Aufgabe, die Primzahlen von den zusammengesetzten zu unterscheiden und Letztere in Primfaktoren zu zerlegen, zu den wichtigsten und nützlichsten der gesamten Arithmetik gehört und die Bemühungen und den Scharfsinn sowohl der alten wie auch der neueren Geometer in Anspruch genommen hat”. Dieser Satz des Mathematikers ist auch heute noch uneingeschränkt richtig, wie auch seine weitere Aussage, dass die bisher angegebenen Methoden „mühsam und aufwendig” seien. Zwar lässt sich heute relativ schnell erkennen, ob eine Zahl eine Primzahl oder zusammengesetzt ist, doch ist bis heute kein Verfahren bekannt, das ähnlich schnell wie der euklidische Algorithmus die Primfaktorzerlegung selbst herstellen könnte. So kann man relativ leicht, sozusagen industriell in Minutenschnelle, 100-stellige Primzahlen p und q herstellen. Bildet man aber das Produkt m = pq zweier solcher Zahlen, so erhält man eine 200-stellige Zahl, für deren Zerlegung in die ursprünglichen Faktoren selbst die besten Computer etwa ein Milliarde Jahre rechnen müssten.

Microsoft® Encarta® Enzyklopädie Professional 2003 © 1993-2002 Microsoft Corporation. Alle Rechte vorbehalten.

bei Antwort benachrichtigen
Olaf19 Mrs. Software „Die Arbeit kannst du dir glaube ich sparen“
Optionen

Hallo Mrs. Software.

Zuerst einmal vielen Dank für die ausführliche Information.

Diese Rekordversuche mit den Zwei-hoch-schießmichtot-minus-eins-Primzahlen sind mir bekannt; darüber wird hin und wieder ja sogar in Presse, Funk und Fernsehen berichtet - wenn mal wieder jemand die nächste Zahl "geknackt" hat. Aber diese Schneller-Höher-Weiter-Geschichten berühren mich ehrlich gesagt nicht so sehr. Wenn ich das richtig sehe, werden die Zahlen zwischen der letzten und vorletzten Primzahl nicht ermittelt. Also gibt es keine lückenlose Kette. Immer noch größere Primzahlen zu entdecken, finde ich insofern nicht so spannend, weil mathematisch ohnehin bewiesen ist, daß es unendliche viele davon gibt. Deswegen sehe ich das eher als eine Art "Muskelspiel" ohne allzu großen Tiefgang.

Viel spannender finde ich den von Dir erwähnten "euklidischen Algorithmus". Danach werde ich mal googlen. Das klingt so, als gäbe es verschiedene Algorithmen zur Zerlegung in Primfaktoren. Mir war nur die ganz geradlinige Methode bekannt: Man prüft, ob die Zahl gerade ist - wenn ja, teilt man (ggfs. mehrmals) durch 2 und prüft anschließend die Teilbarkeit durch 3, 5, 7 usf. Etwas im verborgenen bleibt mir noch, wie man anhand eines Primfaktor-Zerlegungs-Algorithmus neue Primzahlen "selber machen" kann.

CU
Olaf

Die Welt ist ein Jammertal ohne Musik. Doch zum Glueck gab es Bach, Beethoven, Haendel und Goethe (Helge Schneider)
bei Antwort benachrichtigen