Erste 3 Dez.-Stellen 2^64 < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Wie lauten die ersten drei Dezimalstellen (von links) der Zahl [mm] $2^{64} [/mm] - 1$? |
Hallo allerseits!
Vor kurzem tauchte in einer Aufgabe die Frage nach den drei größten Dezimalstellen der Zahl [mm] $2^{64} [/mm] - 1$ auf.
Mit einem Taschenrechner lässt sich diese Aufgabe natürlich schnell lösen.
Ich habe mich jedoch gefragt, ob es auch eine Möglichkeit gibt, diese drei Ziffern ohne technische Hilfsmittel oder massenhaftes stures Multiplizieren zu bekommen. Leider bin ich auf keinen grünen Zweig gekommen.
Die einzige (etwas magere) Idee war die folgende:
Gebe $d(n) [mm] \; \forall \, [/mm] n [mm] \left\{ n \in \mathbb{N} \mid n \geq 100 \right\}$ [/mm] die ersten drei Dezimalstellen der Zahl $n$ an. Es gilt
$$10 [mm] \nmid 2^{64} \Rightarrow d(2^{64}-1) [/mm] = [mm] d(2^{64})$$
[/mm]
Zudem ist
[mm] $$d(2^{n+1}) [/mm] = 2 [mm] \cdot d(2^n) \; \vee \; d(2^{n+1}) [/mm] = 2 [mm] \cdot d(2^n) [/mm] + 1 [mm] \; \forall \, d(2^n) [/mm] < 500$$
Für größere [mm] $d(2^n)$ [/mm] müsste man noch beachten, dass die letzte Ziffer gestrichen werden muss (dies ließe sich natürlich auch noch formulieren  ).
Jetzt kommt das große Problem: Mir ist es unmöglich festzustellen, welche der beiden Fälle eintritt.
Ich entdecke bei den kleineren Dezimalstellen, die das Verhalten beim Verdoppeln beeinflussen, keine Regelmäßigkeit.
Somit ist es mir unmöglich, die ersten drei Dezimalstellen sukzessive zu erhalten.
Für mich ist es noch ziemlich ungewohnt, mathematische Probleme formal darzustellen. Ich hoffe, es ist mir hier einigermaßen gelungen. Zudem bin ich mir nicht sicher, in welches Teilgebiet der Mathematik die Frage einzuordnen ist (wobei ich instinktiv Zahlentheorie annehme).
Ich wäre sehr dankbar, wenn ihr mir Ideen liefern könntet, wie man dieses Problem lösen könnte.
Im voraus besten Dank!
|
|
| |
|
Hoi
Der entscheidende Begriff hier ist die Rechenoperation modulo. Wenn du eine ganze Zahl modulo einer anderen rechnest, ergibt das den Rest bei der normalen Division.
Bsp.
$17 [mm] \mod [/mm] 6 = 5$ denn $17:6=2 [mm] \mbox{ Rest } [/mm] 5$
$56205252 [mm] \mod [/mm] 1000 = 252$
Letzeres Beispiel zeigt dir, dass du die letzten drei Ziffern einer Zahl kriegst, wenn du mod 1000 rechnest. D.h. deine Frage reduziert sich auf:
Was ist [mm] $2^{64}-1 \mod [/mm] 1000$ ?
Bei der modulo-Operation gibt es eine ganz praktische Rechenregel für dieses Problem:
$(a*b) [mm] \mod [/mm] m = (a [mm] \mod [/mm] m) * (b [mm] \mod [/mm] m)$
Wenn ich mehr sage, ist das Problem schon fast gelöst 
Gruss
EvenSteven
|
|
|
| |
|
Hallo EvenSteven,
vielen Dank für deine Hilfe. Leider hast du mein Problem falsch verstanden. Ich suchte die drei ersten Ziffern der Zahl und nicht die drei letzten.
Nichtsdestoweniger eine Rückfrage zu dem neuen Problem
Folgender Lösungssatz
Wir betrachten die letzten drei Ziffern der Zahl [mm] $2^{64}$ [/mm] und ziehen anschließend $1$ ab, um die gewünschten letzten drei Ziffern zu erhalten.
Nach deiner Formel gilt
[mm] $$2^{64} \mod [/mm] 1000 = [mm] \left(\left(2^{10}\right)^6 * 2^4 \right) \mod [/mm] 1000 = [mm] 24^6 \cdot [/mm] 16$$
Das macht so keinen Sinn . Irgendetwas habe ich da falsch verstanden. Denn
$$30 [mm] \mod [/mm] 7 = (6 [mm] \mod [/mm] 7) [mm] \cdot [/mm] (5 [mm] \mod [/mm] 7) = 30$$
So kann bei der Multiplikation doch ein viel größerer Wert entstehen, wie es die Restgruppe zulässt?
Gruß und schönes Wochenende!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:14 So 17.09.2006 | | Autor: | subclasser |
Vielen Dank EvenSteven!
Ich habe weitergerechnet und dann tatsächlich $616$ als Ergebnis herausbekommen. Damit wäre die Frage nach den letzten drei Dezimalstellen geklärt
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:06 So 17.09.2006 | | Autor: | felixf |
Hallo!
> Bei der modulo-Operation gibt es eine ganz praktische
> Rechenregel für dieses Problem:
>
> [mm](a*b) \mod m = (a \mod m) * (b \mod m)[/mm]
Wie ihr schon bemerkt habt, diese Rechenregel ist fuer die meisten Faelle falsch. Richtig lautet sie: [mm] (a * b) \mod m = ((a \mod m) * (b \mod m)) \mod m[/mm].
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 02:57 Mi 18.10.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
