Folge für Primzahlen

22.08.2010, 17:24

graNite

Folge für Primzahlen

Meine Frage:
ich weiss nicht genau, wie ichs erklären soll:

2^2-1=3 <<< primzahl
2^3-1=7 <<< primzahl
2^7-1=127 <<< primzahl
2^127-1=170141183460469231731687303715884105727 <<< primzahl

liefert 2^x-1=y > 2^y-1=z immer eine weitere primzahl, wenn ich mit 2^2-1 beginne?
2^(2^127-1)-1 ist auch prim, glaube ich

Meine Ideen:
keine ahnung^^

hier die formel nochmal in übersichtlich, aus einem anderen forum:

$\begin{eqnarray*} a_{n+1}=2^{a_{n}}-1 \end{eqnarray*}$

22.08.2010, 17:25

Airblader

Auf diesen Beitrag antworten »

Schau dir mal den Begriff der Mersenne-Primzahl an. Augenzwinkern

air

22.08.2010, 17:28

graNite1

Auf diesen Beitrag antworten »

hab ich
primzahlen die als 2^x-1 dargestellt werden können sind mersenne primzahlen

die frage ist, ob bei der formel immer auch eine primzahl heraus kommt.
ich kann das nicht überprüfen, der beste primfaktorzerleger den ich gefunden hab gibt bei derart großen zahlen auf...

22.08.2010, 17:33

Airblader

Auf diesen Beitrag antworten »

Als ersten Hinweis z.B. den ersten Punkt hier lesen:

Zitat:

Daraus folgt unmittelbar, dass der Exponent $\begin{eqnarray*} p \end{eqnarray*}$ einer Mersenne-Primzahl $\begin{eqnarray*} M_p = 2^p-1 \end{eqnarray*}$ selbst eine Primzahl ist. Der Umkehrschluss ist jedoch falsch, da beispielsweise $\begin{eqnarray*} M_{11} = 23 \cdot 89 \end{eqnarray*}$ keine Mersenne-Primzahl ist.

Deine Vermutung ist nun ja aber etwas spezieller, da sie bereits eine Bedingung an den Exponenten stellt. Dazu schaue dir den vorletzten Punkt von hier an.

air

22.08.2010, 17:53

graNite

Auf diesen Beitrag antworten »

ich hab mir deinen beitrag und den wikipedia artikel durchgelesen und bin immer noch nicht weiter, weil ichs nicht verstehe Big Laugh

bitte nochmal in einfacheren worten

22.08.2010, 18:06

Airblader

Auf diesen Beitrag antworten »

Deine Vermutung:

$\begin{eqnarray*} 2^n-1 \end{eqnarray*}$ ist prim, falls $\begin{eqnarray*} n = 2^k-1 \end{eqnarray*}$ prim ist.

Die (alte) Mersenne-Vermutung:

$\begin{eqnarray*} 2^n-1 \end{eqnarray*}$ ist prim, falls $\begin{eqnarray*} n = 2^k\pm 1 \end{eqnarray*}$ oder $\begin{eqnarray*} n = 4^k \pm 3 \end{eqnarray*}$ prim ist.

Die alte Mersenne-Vermutung ist bekanntermaßen falsch (siehe wikipedia). Was schließt du daraus für deine Vermutung?

air

22.08.2010, 19:21

graNite

Auf diesen Beitrag antworten »

wahrscheinlich wilslt du mir sagen, dass meine vermutung dann auch falshc ist.

das kann sein, aber du hast mich teilweise falsch verstanden:

Zitat:

Deine Vermutung: $\begin{eqnarray*} 2^n-1 \end{eqnarray*}$ ist prim, falls $\begin{eqnarray*} n = 2^k-1 \end{eqnarray*}$ prim ist.

das stimmt nicht, da n nicht irgendeine mersenne primzahl sein soll, sondern eine, die aus der folge entstammt, die ich beschrieben habe:

$\begin{eqnarray*} a_{n+1}=2^{a_{n}}-1 \end{eqnarray*}$ mit $\begin{eqnarray*} a_{1}=2 \end{eqnarray*}$

22.08.2010, 19:35

Airblader

Auf diesen Beitrag antworten »

Hi,

da hast du recht - habe ich wohl aus den Augen verloren.
Dann lies dir den letzten Punkt zu den Vermutungen auf wikipedia durch. Das von dir beschriebene Problem ist noch nicht gelöst.

air

22.08.2010, 20:09

graNite

Auf diesen Beitrag antworten »

Alles klar, vielen dank für deine Mühen.
Wie könnte so eine Lösung aussehen?
Alleine die Zahl nach $\begin{eqnarray*} 2^{2^{127}-1}-1 \end{eqnarray*}$ ist schon unglaublich groß, da wird ja wohl kaum einfach ausprobiert.^^

22.08.2010, 20:15

Airblader

Auf diesen Beitrag antworten »

Man muss große Zahlen nicht explizit ausrechnen um etwas über sie zu wissen. Das ist Aufgabe der Zahlentheorie, die haben doch eine ganze Menge an Werkzeugen. Augenzwinkern

Möglicherweise wird aber durchaus auch mit Computernetzen monatelang gerechnet - auf der Suche nach einem Gegenbeispiel. i.d.R. macht immer irgendjemand soetwas. Augenzwinkern

Edit: Die Größe der Zahlen ist aber sicherlich ein entscheidender Faktor, warum es bisher noch ungeklärt ist.

air

22.08.2010, 22:41

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von graNite
Wie könnte so eine Lösung aussehen?
Alleine die Zahl nach $\begin{eqnarray*} 2^{2^{127}-1}-1 \end{eqnarray*}$ ist schon unglaublich groß, da wird ja wohl kaum einfach ausprobiert.^^

Doch ja, es ist (fast) so wie der kleine Max sich das vorstellt, indem für derart riesige Zahlen, wo klarerweise dann jeder probabilistische Primzahltest schon versagt, einfach alle potenziellen Teiler bis zu einer gewissen Schranke S (diese ist laut Curt Noll dzt. bei $\begin{eqnarray*} 5 \cdot 10^{51} \end{eqnarray*}$ ) durchprobiert werden, allerdings mit einer kleinen Erleichterung: Man weiß von vornherein, dass alle potenziellen Teiler einer Mersenne Zahl $\begin{eqnarray*} 2^p-1 \end{eqnarray*}$ , wo p eine ungerade Primzahl ist, die Form 2kp+1 haben müssen, wobei entweder k oder k+p durch 4 teilbar ist...

Es ist also durchaus möglich, dass man von der von dir genannten Zahl nie wissen wird, ob sie prim ist oder nicht... Es ist andererseits extrem unwahrscheinlich, dass obengenannte Folge $\begin{eqnarray*} a_n \end{eqnarray*}$ , n=1,2,3,...nur Primzahlen liefert, denn es gibt überhaupt keinen logischen Grund, warum das der Fall sein sollte...Ganz sicher jedenfalls nicht deshalb, weil deine Folgenglieder $\begin{eqnarray*} a_1,a_2,a_3,a_4,a_5 \end{eqnarray*}$ tatsächlich prim sind... Schließlich sind ja bekanntlich auch die ersten 5 Fermatzahlen

$\begin{eqnarray*} F_n = 2^{2^n}+1 \ (n \in \mathbb N) \end{eqnarray*}$

alle prim, und man hat bisher keine einzige (!) weitere Fermatsche Primzahl bisher gefunden, aber dafür hunderte zusammengesetzte...

22.08.2010, 22:47

Airblader

Auf diesen Beitrag antworten »

@ Mystic

Hast du zufälliger nähere Informationen, wie weit man bei dieser Rekursion ist, also wie viele Zahlen man schon überprüft hat?
Ich finde dem Problem wohnt ja schon eine gewisse Ästhetik inne und erwähnt wird es auf wikipedia auch. Also so ganz unlohnend finde ich es nicht, danach zu suchen .. wie bei den Fermat-Zahlen eben auch (selbst wenn es am Ende "scheitert").

Edit: Und bei einem Problem wie den Fermat-Zahlen kann man den Spieß dann ja durchaus umdrehen und ebenso fragen: Liefern die Fermat-Zahlen wirklich NUR diese fünf Primzahlen oder gibt es noch eine weitere? Ich finde sowas doch schon interessant. Augenzwinkern

air

22.08.2010, 23:17

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Airblader
@ Mystic

Hast du zufälliger nähere Informationen, wie weit man bei dieser Rekursion ist, also wie viele Zahlen man schon überprüft hat?

Was ich oben geschrieben habe, dürfte (siehe hier) schon der letzte Erkenntnisstand sein, d.h., die oben angegebene Zahl, in seiner Bezeichnungsweise $\begin{eqnarray*} a_6 \end{eqnarray*}$ , wäre dann das erste Folgenglied, von dem man nicht weiss, ob es prim oder zusammengesetzt ist...

Zitat:

Original von Airblader
Edit: Und bei einem Problem wie den Fermat-Zahlen kann man den Spieß dann ja durchaus umdrehen und ebenso fragen: Liefern die Fermat-Zahlen wirklich NUR diese fünf Primzahlen oder gibt es noch eine weitere? Ich finde sowas doch schon interessant. Augenzwinkern

Ja, genaugenommen habe ich ja auch nirgends gesagt, dass obiges Problem (bzw. auch das mit den Fermatschen Zahlen) uninteressant ist, nur wird man möglicherweise die Anworten auf diese Fragen nie wissen... Von daher sollte man sich vielleicht doch besser mit Problemen beschäftigen, die ebenfalls interessant sind, aber wo die Erfolgsaussichten dann doch ungleich größer sind... Augenzwinkern

22.08.2010, 23:28

Airblader

Auf diesen Beitrag antworten »

Zitat:

Original von Mystic
Ja, genaugenommen habe ich ja auch nirgends gesagt, dass obiges Problem (bzw. auch das mit den Fermatschen Zahlen) uninteressant ist,

Stimmt, so hatte ich es auch nicht gemeint. Entschuldige. Augenzwinkern

Zitat:

Von daher sollte man sich vielleicht doch besser mit Problemen beschäftigen, die ebenfalls interessant sind, aber wo die Erfolgsaussichten dann doch ungleich größer sind... Augenzwinkern

Ja, da ist wohl was Wahres dran. smile

air

Neue Frage »

Antworten »

Folge für Primzahlen

Verwandte Themen