Folge der Pimzahlen

Neue Frage »

Ninalein Auf diesen Beitrag antworten »
Folge der Pimzahlen
Ist es richtig, dass es kein Bildungsgesetz für die n te Primzahl gibt?

Dachte immer das wär so, aber beim googeln tauchten dann doch lauter Formeln auf...
IfindU Auf diesen Beitrag antworten »
RE: Folge der Pimzahlen
Es gibt keins, deswegen sind Primzahlen so interessant Augenzwinkern

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.
Huggy Auf diesen Beitrag antworten »
RE: Folge der Pimzahlen
Zitat:
Original von IfindU
Es gibt keins, deswegen sind Primzahlen so interessant Augenzwinkern

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.

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.
IfindU Auf diesen Beitrag antworten »
RE: Folge der Pimzahlen
Zitat:
Original von Huggy
Zitat:
Original von IfindU
Es gibt keins, deswegen sind Primzahlen so interessant Augenzwinkern

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.

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.


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.
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?
IfindU Auf diesen Beitrag antworten »
RE: Folge der Pimzahlen
Zitat:
Original von Huggy
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?


Danke für den Tipp, wenn ichs in einer Bibliothek seh, leih ichs mir direkt aus.
 
 
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?
AD Auf diesen Beitrag antworten »

Ist doch kein Problem - deine Vorstellung von "Funktion" ist vielleicht nur zu eingeengt.

für .

Big Laugh
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.
Huggy Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
Ist doch kein Problem - deine Vorstellung von "Funktion" ist vielleicht nur zu eingeengt.

für .

Big Laugh

Sehr schön Arthur! Big Laugh

Aber nein, so sind die im Ribenboim aufgeführten Funktionen nicht gemeint.
IfindU Auf diesen Beitrag antworten »

Zitat:
Original von Arthur Dent
Ist doch kein Problem - deine Vorstellung von "Funktion" ist vielleicht nur zu eingeengt.

für .

Big Laugh


Haha, eine der geilsten Sache die ich bisher gelesen habe.
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*
Huggy Auf diesen Beitrag antworten »

Zitat:
Original von Ninalein
...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*

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.
Ninalein Auf diesen Beitrag antworten »

Danke,

aber tut mir leid ich habs immer noch nicht verstanden...wieso widerspricht es sich nicht?
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 Big Laugh )
Huggy Auf diesen Beitrag antworten »

Zitat:
Original von Ninalein
Danke,

aber tut mir leid ich habs immer noch nicht verstanden...wieso widerspricht es sich nicht?

Die bekannten Formeln machen einfach die Struktur der Primzahlfolge nicht transparent. Und ihr Nutzen für die konkrete Berechnung geht gegen Null.
AD Auf diesen Beitrag antworten »

Zitat:
Original von Huggy
Und ihr Nutzen für die konkrete Berechnung geht gegen Null.

Was man auch gut an der Folge

Zitat:
Original von Huggy


mit



ergibt für jedes

eine Primzahl.

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? verwirrt

Jedenfalls kommt man mit den angegebenen 4 Nachkommastellen nur bis zu , etwas dürftig. Augenzwinkern

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... Big Laugh
Orbit Auf diesen Beitrag antworten »

Wenn wir schon dabei sind Augenzwinkern A la Wilson:



Darauf basierend kann man auch eine Formel für basteln.
Und natürlich gilt:

Zitat:
Und ihr Nutzen für die konkrete Berechnung geht gegen Null.

smile
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
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.
Orbit* Auf diesen Beitrag antworten »

Hallo Sp00kyFox,

Zitat:
also ob dieser bruch eine natürliche zahl ist.

Ja, das ist die Idee hinter der Formel und auch als Satz von Wilson (*) bekannt.

Zitat:

daraus kann man sich dann schon eine effiziente primzahl-funktion basteln

Nein, kann man nicht. Wilson ist kein effizienter Primzahlentest. smile

Orbit*

(*) de.wikipedia.org/wiki/Satz_von_Wilson
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.
Orbit* Auf diesen Beitrag antworten »

Hm..ok. Ich sollte mit dem Begriff Effizienz vielleicht nicht so leichtfertig umgehen. Augenzwinkern 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.

Zitat:
Wilson's theorem is useless as a primality test in practice, since computing (n-1)! modulo n for large n is hard.


Zitat:
it is probably one of the world's least efficient primality tests since computing (n-1)! takes so many steps.


(Wikipedia)
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:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
static int[] wilson(int n){
    BigInteger fak = BigInteger.ONE;
    int[] terms = new int[n-1];
    int count = 0;

    for(int m=2; m<=n; m++){
      fak = fak.multiply(BigInteger.valueOf(m-1));
      if(fak.add(BigInteger.ONE).mod(BigInteger.valueOf(m)).compareTo(BigInteger.ZERO)==0){
        terms[m-2] = 1;
        count++;
      }
    }

    int[] primes = new int[count];
    count = 0;
    
    for(int i=0; i<n-1; i++){
      if(terms[i]==1){
        primes[count] = i+2;
        count++;
      }
    }
    
    return primes;
  }


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.
mausi2225 Auf diesen Beitrag antworten »

In diesen kleinen Bereichen ist man mit dem Sieb des Eratosthenes noch deutlich schneller.
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.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »