Forum: Knobelecke

Moin!

Die erste Primzahl mit mehr als 1.000.000 Ziffern wurde 1999 gefunden, die Mersenne-Primzahl 2^6972593 - 1. Mersenne-Primzahlen lassen sich verhältnismäßig leicht finden, weil sie alle die Form 2^P - 1 haben und P eine Primzahl ist.

Im Jahr 2004 wurde aber eine Non-Mersenne Primzahl gefunden mit 2.357.207 Ziffern: 28433 * 2^7830457 + 1

Wie lauten die letzten 10 Ziffern dieser Zahl?

Da es sich hier um eine offensichtlich extrem leichte Rechenaufgabe handelt, gewinnt diesmal wieder die _effizienteste_ Lösung. Ich bezweifle, dass ich im Besitz dieser effizientesten Lösung bin.

Gruss,
Philip

--
The C Programming Quiz - bitte Fragen einreichen :)

 

Offenbar ist das Rätsel doch nicht so leicht, wie ich gedacht habe.

Woran hängt's denn?

Gruss,
Philip

--
The C Programming Quiz - bitte Fragen einreichen :)

 

Calc meldet bei 2^7830457 "Ungültige Funktionseingabe"
Mir fehlt grad einfach ein bisschen die Zeit.

--
To follow the path: look to the master, follow the master, walk with the master, see through the master, become the master.

 

Hi,

Zitat:

Woran hängt's denn?

An der Umrechnung von Binär auf Dezimal ... oder ich bin überhaupt auf dem Holzweg.

Gedankengang:

Multiplikation mit 2^X enspricht Links-Shift im Binärsystem um X.

D.h: Die Zahl 28433 * 2^7830457 + 1 sieht binär so aus:

Zitat:
110111100010001<insert 7830456 Zeros here>1

--> Umrechnung ?

mfg, Wolfgang

--
Hex, Bugs and Rock 'n Roll

 

Zitat:

Multiplikation mit 2^X enspricht Links-Shift im Binärsystem um X.

Das stimmt.

Zitat:

oder ich bin überhaupt auf dem Holzweg.

Das stimmt auch.
Das Problem ist ja, dass wir bei 32 bzw. 64 Bit nicht knapp 8 Millionen Mal einen Links-Shift machen können. Wir brauchen also einen anderen Ansatz.

Da wir nur an den letzten 10 Stellen des Ergebnisses interessiert sind (also ergebnis % 10), reicht es aus wenn wir die Zwischenergebnisse jeweils modulo 10 speichern. Traurigerweise ist zwischenergebnis%10 recht schnell 0, wenn wir Bitshifts auf integers machen. Der Trick ist also, die Zwischenergebnisse als double zu speichern.


Ich dachte, das sei eh jedem klar, das eigentliche Rätsel sollte lediglich die spätere Optimierung sein.

Möchte sich jemand erstmal an der naiven Implementation wie oben angegeben versuchen oder soll ich sie einfach mal posten?

Gruss,
Philip

--
The C Programming Quiz - bitte Fragen einreichen :)