Primzahl-Algorithmus gesucht

03.09.2007, 19:17

michifold

Primzahl-Algorithmus gesucht

Hallo,

meine Internetsuche hat schon einiges ergeben zum Thema p(n).
Wobei p(n), die n-te Primzahl liefert. Ich wüsste jetzt gerne, ob es da auch schnelleres gibt als die Methode, die hier beschrieben wird. Hier muss man nämlich 2^n mal pi(n) berechnen, was sehr lange dauert (siehe Gleichung 10). Da dauert es wahrscheinlich nicht viel länger p(n) auszurechnen, indem ich alle Vorgänger berechne.

Wenn jemand von euch einen guten Algorithmus kennt oder sogar ein kleines c++-Programm hat, nur her damit. Freude

Ich würde nämlich gerne (numerisch) überprüfen, ob folgende Vermutung von mir stimmt:

$\begin{eqnarray*} \sum_{n=1}^{\inf}\frac{1}{p(p(n))}=1 \end{eqnarray*}$

Dass die Reihe konvergiert, wurde (ich glaube sogar hier) schon geklärt. Mathematica hat sich schon mal einen ganzen Tag abgemüht ums bis n=500000 auszurechnen da kamen 0.988 raus. Leider weiß ich nicht wie man bei Mathematica sich den Status einer Berechnung anzeigen lassen kann (falls das überhaupt möglich ist). Und deswegen kann ich nicht einfach mal 1 000 000 Summanden nehmen, weil ich nicht weiß, wie lange das brauchen würde (Wochen? Monate?)

Deswegen will ich ein Programm schreiben, das effizient und für beliebig große Zahlen (zumindest eben dass p(p(10^7) berechnet werden kann) p(p(n)) berechnet.

Da ja n von 1 ab läuft, wäre es natürlich sinnvoll, die vorigen Werte irgendwie zu verwenden. Und ich brauche eben nicht p(n), sondern p(p(n)). Vielleicht kan mir ja jemand von euch helfen. smile

03.09.2007, 19:21

Dual Space

Auf diesen Beitrag antworten »

RE: Primzahl-Algorithmus gesucht
Es gibt keine explizite Formel, mit der man die n-te Primzahl berechnen kann!

03.09.2007, 19:25

therisen

Auf diesen Beitrag antworten »

Doch, Chuck Norris kennt sie

SCNR

03.09.2007, 19:31

Auf diesen Beitrag antworten »

Ich kann allenfalls einen Weg skizzieren, wie du mit einfachen Mitteln ein schnelles Programm auf einem handelsüblichen PC für deine Summe über alle Primzahlen, sagen wir mal, kleiner als $\begin{eqnarray*} N\approx 10^9 \end{eqnarray*}$ schreiben kannst:

Bitfeld anlegen für alle ungeraden Zahlen $\begin{eqnarray*} <N \end{eqnarray*}$ (d.h. ein Byte enthält Flags für 8 aufeinanderfolgende ungerade Zahlen), dann Sieb des Eratosthenes drüberjagen, die übrigbleibenden Primzahlen in einem Feld aufsammeln und schließlich deine (Partial-)Summen berechnen. Ist bei der genannten Größenordnung ein Speicherbedarf von ein paar Hundert MByte, aber das hat man ja heutzutage übrig. Big Laugh

03.09.2007, 21:04

WebFritzi

Auf diesen Beitrag antworten »

Chuck Norris macht das im Kopf. Big Laugh

03.09.2007, 21:05

michifold

Auf diesen Beitrag antworten »

Danke, Arthur Dent, für deine ernst gemeinte Anwort.
Und alle, die meinen einen solchen Alghorithmus gibt es nicht, sollten sich vielleicht mal den obigen Link anschauen. Den hab ich nicht umsonst angegeben.

Und leider ist der Sieb des Eratothenes nicht das, was ich brauche. Da ich ja nicht nur 1/p(n) summieren will, sondern 1/p(p(n)). Hat vielleicht jemand eine Idee?

03.09.2007, 21:08

WebFritzi

Auf diesen Beitrag antworten »

Zitat:

Original von michifold
Und alle, die meinen einen solchen Alghorithmus gibt es nicht, sollten sich vielleicht mal den obigen Link anschauen.

Es wurde hier gesagt, dass es keine allgemeine Formel gibt, um die n-te Primzahl zu ermitteln. Ob du es willst oder nicht: das stimmt.

03.09.2007, 22:01

Lazarus

Auf diesen Beitrag antworten »

Kannst dir zumindest das Primzahlerzeugen sparen, wenn du da mal reinschauen willst. Das spart dir des aussieben.

03.09.2007, 22:41

michifold

Auf diesen Beitrag antworten »

@Lazarus
Vielen Dank für den Link, schaut genau danach aus, wonach ich gesucht habe. Nur leider ist keine Dokumentation dabei, zumindest sehe ich keine.

@WebFritzi
Ich habe auch nie von einer Formel, sondern von einem Algorithmus bzw. Methode gesprochen. Und solche Posts ala "Es gibt keine explizite Formel, mit der man die n-te Primzahl berechnen kann!" sagen mir nur, dass derjenige sich nicht oder genau meine Frage durchgelesen hat. Diese Antwort wäre vielleicht sinnvoll für die Frage: "gibt es eine Formel mit der ich alle Primzahlen ausrechnen kann?".

zum Thema:
da ich kein allzu großer Programmierer bin, wäre mir sehr geholfen, wenn mir jemand sagen könnte, wie ich die Bibliothek nutzen kann. Ich benutze dev c++ für windows.

Vielen Dank schon mal!

03.09.2007, 22:43

Dual Space

Auf diesen Beitrag antworten »

RE: Primzahl-Algorithmus gesucht

Zitat:

Original von michifold
Und solche Posts ala "Es gibt keine explizite Formel, mit der man die n-te Primzahl berechnen kann!" sagen mir nur, dass derjenige sich nicht oder genau meine Frage durchgelesen hat.

Zitat:

Original von michifold
meine Internetsuche hat schon einiges ergeben zum Thema p(n).
Wobei p(n), die n-te Primzahl liefert.

Eine solche Funktion p gibt es nicht!

03.09.2007, 23:05

Auf diesen Beitrag antworten »

Zitat:

Original von michifold
Und leider ist der Sieb des Eratothenes nicht das, was ich brauche.

Weil du nicht gründlich gelesen bzw. drüber nachgedacht hast!

Zitat:

Original von Arthur Dent
Bitfeld anlegen für alle ungeraden Zahlen $\begin{eqnarray*} <N \end{eqnarray*}$ (d.h. ein Byte enthält Flags für 8 aufeinanderfolgende ungerade Zahlen), dann Sieb des Eratosthenes drüberjagen, die übrigbleibenden Primzahlen in einem Feld aufsammeln und schließlich deine (Partial-)Summen berechnen.

Da ist es dann sch... egal, ob du p(n), p(p(n)) oder auch p(p(p(n))) berechnest - ist alles damit möglich.

03.09.2007, 23:06

michifold

Auf diesen Beitrag antworten »

Ich erlaube mir mal von der verlinkten Seite zu zitieren:

"Explicit formulas exist for the nth prime both as a function of n and in terms of the primes 2, ..., p_(n-1) (Hardy and Wright 1979, pp. 5-6, 344-345, and 414; Guy 1994, pp. 36-41), a number of which are given below. However, it should again be emphasized that these formulas are extremely inefficient, and in many (if not all) cases, simply performing an efficient sieving would yield the primes much more quickly and efficiently."

$\begin{eqnarray*} p(n)=1+\sum_{j=1}^{2^n}f(n,\pi(j)) \end{eqnarray*}$ für n>3

wobei $\begin{eqnarray*} f(x,y)=1/2 (1+\frac{x-y}{|x-y|}) \end{eqnarray*}$ bzw. f(x,y)=0 für x=y

und $\begin{eqnarray*} \pi(n)=-1+\sum_{i=3}^n ((i-2)!-i \lfloor( \frac{(i-2)!}{i}) \rfloor) \end{eqnarray*}$

Ich will mich ja hier nicht über sinnlose Dinge streiten. Aber hier steht,1. dass es eine Formel gibt und 2. die explizite Formel.
Ob ihr das jetzt Formel oder Algorithmus oder sonstwie nennt ist ja relativ egal.

Vielleicht kann mir ja doch jemand mit dem (jetzt nur c++) Problem helfen?

Ich habe übrigens obige Formel [ Lehrer

] mit Mathematica getestet. Sie ist wirklich extrem langsam. p(9) zu berechnen hat geschlagene 7 Sekunden gedauert. Also nix für mein Vorhaben.

@Arthur Dent:

ja, da hab ich wohl nicht näher drüber nachgedacht. Aber jetzt hätte ich ja im Grunde schon eine fertige c++ Funktion

03.09.2007, 23:20

Auf diesen Beitrag antworten »

$\begin{eqnarray*} \sum_{n=1}^{11250482} \frac{1}{p(p(n))} \approx 0.994092770 \end{eqnarray*}$

mit $\begin{eqnarray*} p(11250482) = 203280157 \end{eqnarray*}$ und $\begin{eqnarray*} p(203280157) = 4294965767 \end{eqnarray*}$ (knapp unterhalb von $\begin{eqnarray*} 2^{32} \end{eqnarray*}$ ) als "letzte" Werte in der Summe.

Berechnet mit obiger Methode, Rechendauer 67 Sekunden auf einem Athlon64X2 mit 2GByte RAM - letzteres ist entscheidend! Mit der Vorgabe von dwSize (s.u. im Quelltext) werden tatsächlich temporär 1,1 GByte gebraucht... Big Laugh

03.09.2007, 23:32

michifold

Auf diesen Beitrag antworten »

super, danke! Mit Zunge

das ist ja wirklich unglaublich, dass meine Vermutung immer noch möglich ist! ich bin gerade richtig aus dem Häuschen Big Laugh

könntest du mir vielleicht dein Programm mailen?
3.141592653589793238 ätt gmx.net

Wie könnte man da weiter rechnen? ich will noch eine 9 sehen, dann flipp ich vollends aus LOL Hammer

03.09.2007, 23:35

Mazze

Auf diesen Beitrag antworten »

Seit 2002 gibt es einen Algorithmus der den Primzahltest in polynomieller Zeit schaft ohne auf unbewiesenen Hypothesen zu beruhen (wie etwa die Riemansche Vermutung). Die asymptotische Laufzeit ist in dem Wikipedia link als

$\begin{eqnarray*} O(ln(n)^{3 + \epsilon}) \end{eqnarray*}$

angegeben. Sollte dies jetzt stimmen (ich hab mich so spät nicht mehr damit auseinander gesetzt) könnte man einen Algorithmus für die ersten n Primzahlen so implementieren:

Seien $\begin{eqnarray*} p_1,...,p_n \end{eqnarray*}$ die ersten n Primzahlen und die $\begin{eqnarray*} d_1,...,d_{n-1} \end{eqnarray*}$ die Anzahlen der nicht Primzahlen zwischen den Primzahlen, setze $\begin{eqnarray*} d = \sum_{i=1}^{n-1}d_i \end{eqnarray*}$ . Nun mache folgendes

code:
1: 2: 3: 4:	solange die Anzahl der Primzahlen nicht n ist berechne if Primzahl von n dann variable + 1 usw

Wenn ich mich recht erinnere brauchst Du für deine Formel sowieso jede Primzahl bis n+1. Nun aber zum Aufwand. Um die ersten n Primzahlen zu berechnen brauchst Du

$\begin{eqnarray*} O((d+n)log(n)^{3 + \epsilon}) \end{eqnarray*}$

Jetzt müsste man nur noch wissen wie sich d im Verhältnis zu n ändert. Ich würde an der Stelle aber exponentielles Wachstum erwarten weshalb ich vorsichtig mit der Idee wäre. Mir fehlt da ein wenig das mathematische Knowhow um d abschätzen zu können, bzw. ist es mir jetzt einfach zu spät. Eine sinnvolle Idee hat Arthur dir ja sowieso gegeben, aber ich wollte mal die Idee des AKS vorschlagen.

04.09.2007, 11:41

KnightMove

Auf diesen Beitrag antworten »

Wenn diese Vermutung wirklich richtig sein sollte, dann Gratulation! Wow, ist das aufregend, bei der Entdeckung eines mathematischen Satzes dabei zu sein. Augenzwinkern

04.09.2007, 12:06

Auf diesen Beitrag antworten »

Ich zweifle stark an, dass der Reihenwert genau gleich Eins ist - vielleicht liegt er nur sehr nahe dran...

Und falls er doch gleich 1 ist, dann müsste es schon mit dem Teufel zugehen, dass das noch niemand entdeckt hat. So "verwegen" konstruiert ist die Reihe ja nun nicht. Augenzwinkern

04.09.2007, 12:56

Airblader

Auf diesen Beitrag antworten »

RE: Primzahl-Algorithmus gesucht

Zitat:

Original von michifold
Ich würde nämlich gerne (numerisch) überprüfen, ob folgende Vermutung von mir stimmt:

Ich will mir weder Numerikerfeinde machen noch an der Wichtigkeit der Numerik zweifeln, aber numerisch wirst du hier wohl nur einen Verdacht erwecken und immer mehr stärken können.

Beweisen würdest du so imho nichts, denn außer Chuck Norris hat noch keiner wirklich bis unendlich gezählt Big Laugh

Wie praktisch immer, wenn es um Primzahlen geht, fehlen hier wohl nicht wichtige Erkenntnisse wie z.B. etwas über die Verteilung der Primzahlen.

Kann natürlich auch sein, dass ich die Numerik hier unterschätze Tanzen

Aber bei Fermat's (letztem) Satz hätte es auch nichts gebracht Big Laugh

air

04.09.2007, 13:15

Auf diesen Beitrag antworten »

Zitat:

Original von Airblader
Ich will mir weder Numerikerfeinde machen noch an der Wichtigkeit der Numerik zweifeln, aber numerisch wirst du hier wohl nur einen Verdacht erwecken und immer mehr stärken können.

Nun, sofern die Partialsumme eventuell irgendwann die 1 signifikant (d.h. Rundungsfehler berücksichtigt) übersteigt, dann könnte man es schon als nachgewiesen ansehen, dass die Behauptung falsch ist.

Sollte die Behauptung richtig sein, kann man sie numerisch aber in der Tat nicht beweisen.

04.09.2007, 13:48

Airblader

Auf diesen Beitrag antworten »

Ja, (wiederlegen) [Für WebFritzi:] widerlegen ist numerisch natürlich machbar Augenzwinkern

Ich bezog mich nur aufs Beweisen.

Tante Edith will noch, dass ich sage, dass dies übrigens ein sehr großes Problem ist. Numerisch kann man auch viel zur Vermutung von Lagrange oder Riemann oder zur Primzahlverteilung sagen. Numerisch konnte man damals auch viel zum Fermatschen Satz sagen.
Aber wen juckt es, was man über ein paar Millionen Zahlen von unendlich vielen sagen kann unglücklich

Und wenn du deine Annahme wiederlegst ist es nicht wirklich eine große Entdeckung (sonst würde ich für den Satz "Pi ist nicht drei" berühmt werden Big Laugh

) - es sei denn, es kommt eine andere erstaunliche Zahl heraus (z.B. $\begin{eqnarray*} \pi/3 \end{eqnarray*}$ oder so...)

air

edit (AD): Freunde der Orthographiediskussion machen bitte hier weiter.

04.09.2007, 17:00

michifold

Auf diesen Beitrag antworten »

Als Physiker ist mir natürlich klar, dass ein numerischer "Beweis", dass da 1 rauskommt, genauso wenig ein Beweis ist, wie jedes andere Experiment, dass eine These zu bestätigen scheint. Ich sehe die numerische Berechnung der Reihe einfach als ein Experiment an, das sehr wohl meine These widerlegen könnte, aber bisher schauts sehr gut aus. Bei 3 9en wäre ich bereit ziemlich viel Geld zu wetten, dass ich recht habe Big Laugh

Aber ich war mir ja, warum auch immer, schon nach 500000 und einem Wert von 0,98 schon ziemlich sicher, dass ich da was tolles andeckt hab. Und jetzt nach 11 Mio Reihengliedern bin ich weder übers Ziel (die 1) hinausgeschossen, noch ist es bei 0,98 geblieben.

Hier ist übrigens der alte Thread:
spezielle Funktion gesucht

dort wurde geklärt, dass die Reihe konvergiert.

Mal schaun, ob wir der Reihe noch ein paar Neuner entlocken können!

04.09.2007, 17:19

Airblader

Auf diesen Beitrag antworten »

Wie damals gesagt: Die langsame Konvergenz ist ein großes Hindernis.
Theoretisch könnte der Reihenwert $\begin{eqnarray*} 1 + 10^{-30} \end{eqnarray*}$ betragen o.ä.

Die Konvergenz selbst hat sich ja auch nur beweisen lassen, da man gut abschätzen kann. Mit einer Abschätzung kannst du den Reihenwert selbst allerdings nicht herausbekommen.
Und ohne die wichtigen Erkenntnisse über Primzahlen, nach denen noch immer geforscht wird, kannst du viel vermuten - aber nicht beweisen.

Natürlich kannst du weiterrechnen wie du lieb bist und hoffen, dass du nie über 1 kommst Augenzwinkern

Eine interessante Vermutung ist es ja.
Und ehrlich gesagt habe ich keinerlei Einschätzungsgefühl was als Reihenwert herauskommen könnte.

Interessant wäre natürlich auch, ob und wo Unterschiede liegen zwischen $\begin{eqnarray*} \sum_{n=1}^\infty \frac{1}{p(p(n))}\text{, }\sum_{n=1}^\infty \frac{1}{p(p(p(n)))}\text{, } \ldots \end{eqnarray*}$

04.09.2007, 17:24

Auf diesen Beitrag antworten »

Meine Vermutung geht dahin, dass der Reihenwert echt kleiner als Eins ist - aber wie gesagt, es ist eine Vermutung.

Vielleicht solltest du dich hinsichtlich des theoretischen Problems mal hier umschauen bzw. da nachfragen. Ich verweise zwar ungern auf die Konkurrenz, aber dort ist in diesen vertrackten Fragen sicherlich mehr Kompetenz versammelt als hier im Forum.

04.09.2007, 17:39

michifold

Auf diesen Beitrag antworten »

Danke für den Hinweis! Vielleicht frag ich da mal nach.

Übrigens hab ich auch folgende Reihe untersucht. Dazu definiere man folgende Funktion rekursiv.

f[n_] := Prime[f[n - 1]]
f[1] := Prime[1]

bedeutet also f[2]=Prime[Prime[1]], f[3]=Prime[Prime[Prime[1]]] usw.

da konvergiert die zugehörige Reihe rasend schnell (nach meiner experminentellen Auffassung von Kovergenz Augenzwinkern

)

$\begin{eqnarray*} \sum_{n=1}^m \frac{1}{f(n)} \end{eqnarray*}$

habe hier für m alle Werte zwischen 1 und 16 annehmen lassen. Die Liste zeigt den numerischen Wert der Reihe und f[m].

{{0, 2},
{0.333333333333333333333333333333, 3},
{0.533333333333333333333333333333, 5},
{0.624242424242424242424242424242, 11},
{0.656500488758553274682306940371, 31},
{0.664374504506584770745299066356, 127},
{0.665784941742127789080983128415, 709},
{0.665970780805498909690535256272, 5381},
{0.665989752177698260869606038462, 52711},
{0.665991294456971107038044526967, 648391},
{0.665991397154496189111339134432, 9737333},
{0.665991402887124972430645967203, 174440041},
{0.665991403160535764607135369848, 3657500101},
{0.665991403171852737451399035498, 88362852307},
{0.665991403172264582879655593046, 2428095424619},
{0.665991403172277904899464633008, 75063692618249}}

Achja, was ich noch sagen wollte. Ich hab schon sooo viele derartige Reihen
experimentell untersucht, da musste im Grunde mal auch ein besondere Zahl rauskommen. Zumindest eine bessere als 0.66599....
Ich hatte mich natürlich auch schon Stunden hingesetzt und alle möglichen Kombinationen von Pi und e ausprobiert. Aber obige Reihe scheint langweilig zu sein.

Bei der 1/p(p(n))-Reihe hat mich die 1 natürlich sofort angesprungen.

04.09.2007, 17:50

Airblader

Auf diesen Beitrag antworten »

Würde man einen Zusammenhang zu Pi oder e herstellen wäre es imho ziemlich faszinierend: Ein Zusammenhang zwischen Primzahlen und Pi/e ! Darum wird das auch nicht so schnell klappen Big Laugh

Du solltest dir vllt. mal die Zeit nehmen und deine Vermutung bis zu einem gigantisch hohen Wert numerisch durcharbeiten.
Dafür solltest du aber ein gutes Programm schreiben, denn normale Bibliotheken werden da sehr schnell aufgeben.

Für so extrem große Zahlen habe ich auch lange etwas gesucht, um sie zu verarbeiten. Bisher habe ich nie etwas gefunden Big Laugh

air

04.09.2007, 18:27

Auf diesen Beitrag antworten »

Wer sich mein Programm oben genau angesehen hat, weiß, dass es wertebereichsmäßig ziemlich am Ende ist, d.h. ausgereizt.

Mit etwas größeren Umbaumaßnahmen kann man das zugrundeliegende Prinzip noch ein, zwei Zehnerpotenzen nach oben treiben:

(a) Dazu wird das (dann größere) Eratosthenes-Bitmuster direkt auf Festplatte geschrieben. Für einen Endwert $\begin{eqnarray*} p(p(n))\approx 10^{11} \end{eqnarray*}$ wäre das dann ein File der Größe $\begin{eqnarray*} \frac{10^{11}}{16}\approx 6~\text{GByte} \end{eqnarray*}$ . In diesem File ist dann $\begin{eqnarray*} p(n) \end{eqnarray*}$ gewissermaßen im Bitmuster versteckt.

(b) "Aufsammeln" der Primzahlen in einem Feld - wie oben - verbietet sich hier, denn jeder Feldeintrag müsste nunmehr 64Bit (also 8 Byte) groß sein, das ist im RAM momentaner PCs nicht haltbar. Aber man könnte zwei Filepointer dieses Bitmuster entlangfahren lassen (im Sinne von sukzessiv lesen): Der erste fährt immer von $\begin{eqnarray*} p(n) \end{eqnarray*}$ bis zu $\begin{eqnarray*} p(n+1) \end{eqnarray*}$ , der zweite von $\begin{eqnarray*} p(p(n)) \end{eqnarray*}$ zu $\begin{eqnarray*} p(p(n+1)) \end{eqnarray*}$ - und während dieser "Fahrt" kann man dann $\begin{eqnarray*} \frac{1}{p(p(n))} \end{eqnarray*}$ aufsummieren.

Für Teil (a) habe ich bereits vor längerer Zeit mal ein Programm geschrieben, Teil (b) ist umsetzungsmäßig auch relativ schnell machbar. Mal sehen, wenn ich etwas Muße dazu habe, mache ich es.

04.09.2007, 19:44

michifold

Auf diesen Beitrag antworten »

Arthur Dent, das wäre super! Leider habe ich (noch) viel zu wenig Ahnung vom Programmieren. Erst während meiner Numerikvorlesung habe und musste ich anfangen zu programmieren, eben in c++, allerdings sagt das was du schreibst nicht allzu viel. Könntest du mir eventuell das Programm mailen. Vielleicht versteh ichs dann.

Dieses Package, das Lazarus gelinkt hatte: http://cr.yp.to/primegen.html
ist das fähig auch größe p(n) zu berechnen?

04.09.2007, 20:23

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Meine Vermutung geht dahin, dass der Reihenwert echt kleiner als Eins ist - aber wie gesagt, es ist eine Vermutung.

Eine falsche Vermutung - hier die Ergebnisse von ca. 1 Stunde Athlon-X2-"Heizen":

$\begin{eqnarray*} \sum_{n=1}^{261\,150\,360} \frac{1}{p(p(n))} \approx 1\,.\,001\,106 > 1 \end{eqnarray*}$

mit

$\begin{eqnarray*} p(261\,150\,360) = 5\,586\,502\,267 \end{eqnarray*}$
$\begin{eqnarray*} p(5\,586\,502\,267) = 137\,438\,950\,763 \end{eqnarray*}$ (knapp unterhalb von $\begin{eqnarray*} 2^{37} \end{eqnarray*}$ ) .

Der Quelltext sieht momentan zu besch... aus, um ihn hier posten zu können. Aber das hole ich vielleicht noch nach. Augenzwinkern

Gerechnet wurden die Reziproken mit "double", also etwa 16 Stellen Mantisse. Auch bei konservativer numerischer Fehlerabschätzung dürfte das og. Ergebnis signifikant größer als Eins sein.

04.09.2007, 20:30

michifold

Auf diesen Beitrag antworten »

sowas gemeines! aber bis ich deinen quelltext nicht gesehen, verstanden und bei mir gerechnet hab, glaub ich gar nix Augenzwinkern

gibst du mir bitte trotz Häßlichkeit deinen Quellcode? sonst kann ich nämlich heute bestimmt nicht schlafen...

nochmal meine e-mail, wenn du ihn hier noch nicht posten willst:
3.141592653589793238 ätt gmx.net

04.09.2007, 20:32

Auf diesen Beitrag antworten »

Nein - wenn ich ihn poste, dann für alle. Aber heute nicht mehr.

04.09.2007, 20:34

michifold

Auf diesen Beitrag antworten »

naja, vielleicht kann ich doch einschlafen traurig

04.09.2007, 20:42

Auf diesen Beitrag antworten »

Ich hab mal noch die Primzahlen des letzten Summanden ergänzt. Bei $\begin{eqnarray*} p(p(n)) \approx 8\cdot 10^{10} \end{eqnarray*}$ hatte die Partialsumme die Eins überschritten.

04.09.2007, 20:47

michifold

Auf diesen Beitrag antworten »

Versteh ich nicht. Ohne die letzte Zahl, bleibt die Partialsumme unter der 1?
Ist ja ein merkwürdiger Zufall, dass du bei 2,6 10^8 genau die Zahl als letzte erwischt die das Faß zum überlaufen bringt.
kann es sein, dass etwas mit der letzten Primzahl nicht stimmt?

04.09.2007, 20:53

Auf diesen Beitrag antworten »

Du solltest mal gründlicher lesen... unglücklich

Bei ca. 80 Milliarden wurde die 1 überschritten - aber die oben genannte Summe ging bis ca. 137 Milliarden. Ich spreche wohlgemerkt dabei von $\begin{eqnarray*} p(p(n)) \end{eqnarray*}$ , nicht von $\begin{eqnarray*} n \end{eqnarray*}$ .

04.09.2007, 21:14

therisen

Auf diesen Beitrag antworten »

Mensch Arthur, du hast dir eine hohe Geldprämie durch die Lappen gehen lassen:

Zitat:

Original von michifold
Bei 3 9en wäre ich bereit ziemlich viel Geld zu wetten, dass ich recht habe Big Laugh

04.09.2007, 21:25

Auf diesen Beitrag antworten »

So ein Mist, das hab ich glatt überlesen. Aber das ist ja nicht das erste leichtfertige Geldangebot eines Fragestellers hier im Matheboard, wenn ich mich recht erinnere. smile

P.S.: Ich bin übrigens mal gespannt, wie sich Anfrage

http://www.mathlinks.ro/Forum/viewtopic.php?t=165659

entwickelt. Ich poste gemeinerweise dort vorerst mal noch nix, aber michifold kann das natürlich tun, wenn er will.

04.09.2007, 22:05

michifold

Auf diesen Beitrag antworten »

Ja ja, gut, dass wir nicht gewettet haben! Big Laugh

Du hast doch n bis 2,61 10^8 laufen lassen, oder? Ich dachte die 8 10^10 seien die p(p(2,61 10^8)).

Ich werd auch erstmal abwarten, ab sich in dem Forum da überhaupt was tut. Wenn nicht scheints ja eh keinen da zu interessieren.

05.09.2007, 14:27

Airblader

Auf diesen Beitrag antworten »

Ich persönlich finde es aber interessant, dass die Reihe überhaupt konvergiert. Der tatsächliche Wert würde mich irgendwie schon interessieren Big Laugh

(z.B. auch ob er rational/irrtational oder algebraisch/transzendent, ... ist)

air

05.09.2007, 16:33

akechi90

Auf diesen Beitrag antworten »

Ich würde persönlich behaupten, dass sie divergiert. Kann man die n-te Primzahl nicht irgendwie durch einen etwas größeren Term abschätzen, über dem die Reihe noch immer divergiert?

05.09.2007, 16:50

michifold

Auf diesen Beitrag antworten »

Wie gesagt, die Kovergenz ist bewiesen, sogar auch von Arthur Dent!

Zitat:

Original von Arthur Dent
Aus dem Primzahlsatz kann man - zumindest für große $\begin{eqnarray*} n \end{eqnarray*}$ - die Ungleichung

$\begin{eqnarray*} n\cdot\ln(n) < P(n) < n\cdot\ln(n)\cdot\ln(\ln(n)) \end{eqnarray*}$

ableiten. Aus der rechten Ungleichung kann man

$\begin{eqnarray*} \sum_{n=n_0}^{\infty} \frac{1}{P(n)} \geq \sum_{n=n_0}^{\infty} \frac{1}{n\cdot\ln(n)\cdot\ln(\ln(n))} = \infty \end{eqnarray*}$

folgern, aus der linken aber ebenso $\begin{eqnarray*} P(P(n)) > n\cdot(\ln(n))^2 \end{eqnarray*}$ und somit

$\begin{eqnarray*} \sum_{n=n_0}^{\infty} \frac{1}{P(P(n))} \leq \sum_{n=n_0}^{\infty} \frac{1}{n\cdot(\ln(n))^2} < \infty \end{eqnarray*}$ .

der Beweis stammte aus dem Thread:
spezielle Funktion gesucht

Damit kovergieren natürlich auch alle anderen Abarten dieser Reihe, wie die 1/p(p(p(n))) usw.

Auch ganz interessant ist der Wert der alternierenden Reihe:

$\begin{eqnarray*} \sum_{n=1}^{\infty}(-1)^n \frac{1}{p(n)}=-0.269606... \end{eqnarray*}$

bzw. es ist noch nicht mal geklärt ob diese Reihe überhaupt konvergiert oder nicht:

$\begin{eqnarray*} \sum_{n=1}^{\infty}(-1)^n \frac{n}{p(n)} \end{eqnarray*}$

Mir hats schon immer Spaß solche Dinge einfach in Mathematika einzutippen und einfach zu schauen, was passiert.
Ich glaube draufgekommen bin ich über die nebenbei angemerkte Tatsache aus dem Forster: Analysis 1, dass die 1/p(n)-Reihe divergiert. Dann wollte ich eben wissen, ob die ausgedünnte Reihe auch noch divergiert oder nicht.
Wo mir eben Mr. Dent auch schon weitergeholfen hat. Freude

Ich hoffe übrigens immer noch das Programm bald ausprobieren zu dürfen smile

Edit:
Ich wunder mich gerade, wieso von letzt genannter Reihe noch nicht bekannt sein soll, ob sie konvergiert oder nicht. Quelle: http://mathworld.wolfram.com/PrimeSums.html

n/p(n) ist doch eine Nullfolge, oder? Da ja p(n)~n log(n). Meine Analysiskenntnisse sind zwar schon fast vollständig verdrängt, aber konvergiert eine alternierende Reihe nicht, wenn das "Innere" eine Nullfolge ist?

123 nächste Seite »

Neue Frage »

Antworten »

Primzahl-Algorithmus gesucht

Verwandte Themen