Folge der Pimzahlen |
04.04.2009, 17:19 | Ninalein | Auf diesen Beitrag antworten » | |||||
Folge der Pimzahlen Dachte immer das wär so, aber beim googeln tauchten dann doch lauter Formeln auf... |
|||||||
04.04.2009, 17:50 | IfindU | Auf diesen Beitrag antworten » | |||||
RE: Folge der Pimzahlen Es gibt keins, deswegen sind Primzahlen so interessant Die Riemannsche Vermutung sagte etwas über Primzahlen aus, allerdings bin ich mir nicht sicher auf was die sich genau bezog, dafür bin ich mir ziemlich sicher dass es keine bewiesene Formel für das Ausspucken von Primzahlen gibt. |
|||||||
04.04.2009, 18:03 | Huggy | Auf diesen Beitrag antworten » | |||||
RE: Folge der Pimzahlen
Immer diese voreiligen Behauptungen. Es gibt solche Funktionen! Z. B. gibt es eine Funktion, in die steckt man die ersten n - 1 Primzahlen und dann spuckt sie die nte Primzahl aus. Auch gibt es diverse Funktionen f(n), die für jede natürliche Zahl n eine Primzahl ausspucken. |
|||||||
04.04.2009, 18:06 | IfindU | Auf diesen Beitrag antworten » | |||||
RE: Folge der Pimzahlen
Kannst du mir ein paar Beispiele für solche Funktionen geben? Hab ehrlich noch nie von so welchen gehört und es klang auch immer so als seien Primzahlen etwa so unberechenbar wie die welche Stelle bei Pi an n-ter Stelle kommt (klar ist das berechenbar, wurde aber hin und wieder gerne als Zufallswert bezeichnet, da bei denen Milliarden Stellen wo sie untersucht wurde alle Ziffern gleichmäßig auftauchten). Und auch bei Primzahlen hab ich überall nur Nährungen gesehen wie z.b. dass es mehr Primzahlen als Quadratzahlen gibt. |
|||||||
04.04.2009, 18:12 | Huggy | Auf diesen Beitrag antworten » | |||||
RE: Folge der Pimzahlen Leih dir mal folgendes Buch aus: Paolo Ribenboim The new book of prime number records und lies dort Kapitel 3: Are there functions defining prime numbers? |
|||||||
04.04.2009, 18:18 | IfindU | Auf diesen Beitrag antworten » | |||||
RE: Folge der Pimzahlen
Danke für den Tipp, wenn ichs in einer Bibliothek seh, leih ichs mir direkt aus. |
|||||||
Anzeige | |||||||
|
|||||||
04.04.2009, 18:29 | Ninalein | Auf diesen Beitrag antworten » | |||||
Hmm, ich bin immer noch verunsichert, da ich eigentlich auch immer dachte es gäbe keine solche Funktion... woher kommt denn dieses Gerücht? |
|||||||
04.04.2009, 18:35 | AD | Auf diesen Beitrag antworten » | |||||
Ist doch kein Problem - deine Vorstellung von "Funktion" ist vielleicht nur zu eingeengt. für . |
|||||||
04.04.2009, 18:38 | Huggy | Auf diesen Beitrag antworten » | |||||
RE: Folge der Pimzahlen Ein Beispiel: mit ergibt für jedes eine Primzahl. Funktionen für die nte Primzahl sind ein Stück komplizierter. |
|||||||
04.04.2009, 18:41 | Huggy | Auf diesen Beitrag antworten » | |||||
Sehr schön Arthur! Aber nein, so sind die im Ribenboim aufgeführten Funktionen nicht gemeint. |
|||||||
04.04.2009, 18:49 | IfindU | Auf diesen Beitrag antworten » | |||||
Haha, eine der geilsten Sache die ich bisher gelesen habe. |
|||||||
04.04.2009, 18:57 | Ninalein | Auf diesen Beitrag antworten » | |||||
...Ihre gesetzmäßige Aufeinanderfolge ist noch nicht bekannt. Die Verteilung der Primzahlen unter den natürlichen Zahlen ist äußerst unregelmäßig.... Hab ich auf primzahl.de gefunden *verwirrtbin* |
|||||||
04.04.2009, 19:11 | Huggy | Auf diesen Beitrag antworten » | |||||
Das ist richtig, widerspricht aber nicht der Tatsache, dass es Formeln für Primzahlen gibt. Habe mir jetzt die Mühe gemacht, eine Formel für die nte Primzahl abzuschreiben: Sei die ite Primzahl. Sei Dann gilt: Dabei ist die zahlentheoretische Möbiusfunktion. |
|||||||
04.04.2009, 21:42 | Ninalein | Auf diesen Beitrag antworten » | |||||
Danke, aber tut mir leid ich habs immer noch nicht verstanden...wieso widerspricht es sich nicht? |
|||||||
04.04.2009, 21:42 | Elvis | Auf diesen Beitrag antworten » | |||||
Primzahlen Es gibt Formeln, Funktionen, Polynome (in vielen Variablen von hohem Grad), die Primzahlen darstellen. Das hilft aber nicht ganz so viel bei der Suche nach (großen) Primzahlen, wenn das Berechnen dieser Formeln länger dauert als das Suchen, oder wenn die Funktionen nicht berechenbar oder nicht effektiv berechenbar sind. Kleine Primzahlen kennt man schon alle (ich definiere : eine Primzahl p heißt kleine Primzahl, wenn man alle Primzahlen q<=p kennt ) |
|||||||
04.04.2009, 23:13 | Huggy | Auf diesen Beitrag antworten » | |||||
Die bekannten Formeln machen einfach die Struktur der Primzahlfolge nicht transparent. Und ihr Nutzen für die konkrete Berechnung geht gegen Null. |
|||||||
05.04.2009, 09:34 | AD | Auf diesen Beitrag antworten » | |||||
Was man auch gut an der Folge
demonstrieren kann. Die ist wohl so zu verstehen, dass man zwar bewiesen hat, dass es so ein gibt, aber in der praktischen Berechnung die Bestimmung von nur für die ersten paar möglich ist, weil der Aufwand zur Bestimmung einer größeren Stellenzahl von irgendwie astronomisch steigt? Jedenfalls kommt man mit den angegebenen 4 Nachkommastellen nur bis zu , etwas dürftig. Eine kleine Abschätzung ergibt, dass man berechnen müsste, um den derzeitigen Mersenne-Stellenrekord zu gefährden. Dazu braucht man dann allerdings auf ungefähr 15 Millionen Nachkommastellen genau... |
|||||||
05.04.2009, 10:12 | Orbit | Auf diesen Beitrag antworten » | |||||
Wenn wir schon dabei sind A la Wilson: Darauf basierend kann man auch eine Formel für basteln. Und natürlich gilt:
|
|||||||
05.04.2009, 10:59 | Huggy | Auf diesen Beitrag antworten » | |||||
Hier noch ein gut lesbarer Artikel zu dem Thema: http://www.stud.uni-hannover.de/user/478...ende_folgen.pdf |
|||||||
22.02.2010, 14:26 | Sp00kyFox | Auf diesen Beitrag antworten » | |||||
@Orbit wobei die von dir genannte formel von Wilson, relativ effektiv zu berechnen ist. die fakultäten in dem term muss man zB nicht jedesmal neu berechnen, da du eh alle fakultäten für m=2 bis n berechnen musst. ergo kannst du dir eine liste basteln, wobei der erste eingtrag a[2]=1 und a[m]=a[m-1]*(m-1). wenn man sich jetzt noch die cosinus-fkt quadriert anschaut, sieht man, dass diese bei allen vielfachen von pi 1 ist und nur dann. da durch das abrunden eh alle anderen werte auf 0 fallen, kann man bei der berechnung den cosinus und den faktor pi getrost ignorieren und nur betrachten, ob (m-1)!+1 und 0 kongruent mod m sind. also ob dieser bruch eine natürliche zahl ist. wenn dies der fall ist, ergibt der ganze term 1, ansonsten 0. daraus kann man sich dann schon eine effiziente primzahl-funktion basteln, allerdings sind priemzahlsiebe, selbst wenn man nur eine primzahl bestimmen möchte, immer noch weitaus effektiver. |
|||||||
22.02.2010, 14:57 | Orbit* | Auf diesen Beitrag antworten » | |||||
Hallo Sp00kyFox,
Ja, das ist die Idee hinter der Formel und auch als Satz von Wilson (*) bekannt.
Nein, kann man nicht. Wilson ist kein effizienter Primzahlentest. Orbit* (*) de.wikipedia.org/wiki/Satz_von_Wilson |
|||||||
23.02.2010, 18:35 | Sp00kyFox | Auf diesen Beitrag antworten » | |||||
da muss ich dir widersprechen. beide verfahren, also der ansatz von wilson und das sieb von eratosthenes, haben dieselbe zeitkomplexität. denn um die einzelnen fakultäten zu berechnen, brauchst du nur n multiplikationen. für das +1 brauchst du in jedem reihenglied eine addition und weiterhin eine modulo-operation. schlussendlich musst du nur noch durch die einzelnen glieder der reihe gehen und die gewünschte primzahl durch mitzählen der einsen ermitteln. ergo ergibt sich eben eine laufzeit von O(n) und das sieb von eratosthenes hat dieselbe laufzeitkomplexität. |
|||||||
24.02.2010, 01:29 | Orbit* | Auf diesen Beitrag antworten » | |||||
Hm..ok. Ich sollte mit dem Begriff Effizienz vielleicht nicht so leichtfertig umgehen. Daher bleibe ich bei meiner ursprünglichen Aussage: Und ihr Nutzen für die konkrete Berechnung geht gegen Null. Für praktische Berechnungen kann ich nämlich nicht so recht dran glauben.
(Wikipedia) |
|||||||
25.02.2010, 00:21 | Sp00kyFox | Auf diesen Beitrag antworten » | |||||
ja gut, da würfelst du aber auch zwei sachen zusammen. wilson für n primzahltest zu nutzen ist natürlich unsinnig, aufgrund der fakultätsberechnung die auch bei fortgeschritten algorithmen wie zB primeswing immer noch aufwendig ist. allerdings ging es ja um eine primzahlfunktion, und da will man ja eigentlich bis zu einem gewissen n die funktion berechnen. und da reduziert sich der aufwand entsprechend, weil du bei der reihenberechnung die fakultät des letzten gliedes jeweils nutzen kannst. ergo berechnest du in jedem schritt ja auch gar keine fakultät sondern nutzt die fakultät aus dem letzten schritt und mult. sie mit (m-1). bei nem wilsonprimzahl-test allerdings würdest du ja praktisch dasselbe machen allerdings nur mit dem ziel die primzahlfunktion für ein besitmmtes n zu berechnen, was dann natürlich lächerlich ineffizient wäre, da du dann für diesen einen test einen aufwand von O(n) hättest, obwohl du diesen zB mit einem primsieb auch in O(sqrt(n)) machen könntest (indem man alle primzahlen bis sqrt(n) berechnet und testet ob diese n teilen). ich hab mal kurz in java die reihenberechnung nach wilson implementiert, wie folgt:
damit kann ich die primzahlen im intervall [1, 10000] in 1,6 sekunden berechnen (athlon64 x2 4400+). für größere zu untersuchende intervalle steigt aber der zeitbedarf zu sehr an, da die multiplikationen und modulo-operationen mit solchen großen zahlen immer aufwendiger werden. |
|||||||
25.02.2010, 00:53 | mausi2225 | Auf diesen Beitrag antworten » | |||||
In diesen kleinen Bereichen ist man mit dem Sieb des Eratosthenes noch deutlich schneller. |
|||||||
25.02.2010, 01:11 | Sp00kyFox | Auf diesen Beitrag antworten » | |||||
für den selben bereich brauch ich mit dem primsieb von eratosthenes etwa 0,0015 sekunden. ich wollte nur darauf hinweisen, dass man sehr wohl den satz von wilson auch praktisch nutzen kann für die berechnung von primzahlen. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
|
Die Neuesten » |
|