Letzte Ziffer ungleich 0 von 1.000.000 Fakultät

03.12.2010, 22:35

strike300

Letzte Ziffer ungleich 0 von 1.000.000 Fakultät

Meine Frage:
Hallo zusammen,
wir haben als Weihnachtsbastelaufgabe von unserem Lineare-Algebra-Prof. die Aufgabe bekommen, die letzte Ziffer von 1.000.000!, die keine Null ist anzugeben, d. h. die erste Ziffer ungleich Null von rechts gesehen (im Weiteren einfach letzte Ziffer genannt).

Meine Ideen:
Für die letzte Ziffer eines Produkts zählen nur die letzten Ziffern der Faktoren. Für 1.000.000! sind also nur die Faktoren 1,2,3,4,5,6,7,8,9,0 relevant. 0, 1, sowie 2*5 ändern nichts an der letzten Ziffer.
3*4*6*7*8*9 = 8 (mod 10), also hat 10! als letzte Ziffer die 8. Es folgt: letzte Ziffer von 20! ist 8*8 = 4 (mod 10), letzte Ziffer von 30! ist 4*8 = 2 (mod 10), letzte Ziffer von 40! ist 2*8 = 6 (mod 10). Die letzte Ziffer von 50! ist wieder 6*8 = 8 (mod 10).
Die letzte Ziffer wiederholt sich quasi "alle 40!". Da 40 | 1.000.000, sollte die letzte Ziffer von 1.000.000! also eine 6 sein, genau wie bei 40!.
Unter http://sourceforge.net/projects/bigal/files/BigAl%20results/factorial/factorial_1000000.txt/download kann man sich den genauen Wert von 1000000! als .txt runterladen und die letzte Ziffer ist eine 4.

Wo liegt mein Denkfehler?

Vielen Dank für Eure Hilfe!

Grüße
Sven

03.12.2010, 22:54

wisili

Auf diesen Beitrag antworten »

RE: Letzte Ziffer ungleich 0 von 1.000.000 Fakultät
Es geht leider nicht so einfach.
30! hat eine 8 vor den Nullen, nicht wie behauptet eine 2.

03.12.2010, 23:24

grafzahlonline

Auf diesen Beitrag antworten »

Ist es erlaubt ein kleines Computerprogramm zur Lösung zu schreiben?

04.12.2010, 07:04

René Gruber

Auf diesen Beitrag antworten »

@strike300

Deine Idee bricht in der dritten Dekade 21..30 in sich zusammen, wie wisili ja schon angemerkt hat, aber warum:

Grund ist, dass du angenommen hast, dass die mittlere, auf 5 endende Zahl immer nur genau eine zusätzliche Endnull erzeugt. Das ist bei $\begin{eqnarray*} 25=5^2 \end{eqnarray*}$ nicht der Fall, dieser Faktor erzeugt sogar zwei zuätzliche Endnullen. Desweiteren hast du die letzte, durch 10 teilbare Zahl in dieser Dekade auch falsch verarbeitet: Faktor 10 erzeugt bei Multiplikation einen anderen Effekt auf die letzte Nicht-Null-Ziffer als Faktor 20 oder 30. Bei Faktor 50 u.ä. kommt dann sogar der Effekt der 25 von oben zum Tragen usw.

Nein, so einfach ist es wirklich nicht.

---------------------------------------------------

Ein Computer-Programm zur Berechnung der letzten Nicht-Null von $\begin{eqnarray*} n! \end{eqnarray*}$ ist allerdings relativ einfach zu bewerkstelligen (der Prof ist vielleicht nicht ganz auf der Höhe in Bezug auf die derzeitigen Rechenmöglichkeiten, sonst hätte er die Aufgabe mit $\begin{eqnarray*} n = 1\,000\,000\,000 \end{eqnarray*}$ statt nur $\begin{eqnarray*} n=1\,000\,000 \end{eqnarray*}$ gestellt und somt deine Lösung via http://sourceforge.net/projects/bigal/fi...00.txt/download bis auf weiteres wirksam unterbunden Big Laugh

):

In diesem gruppiert man Faktoren des Produkts $\begin{eqnarray*} n! \end{eqnarray*}$ vorab so zusammen, dass die Produkte der Gruppenelemente den oben beschriebenen Effekt nicht zeigen, d.h. dass in ihner Primfaktorzerlegung der Exponent der 2 immer mindestens so groß ist wie der Exponent der 5 - oder kurz gesagt: Dass die letzte Nicht-Null-Ziffer dieses Teilprodukts keine 5 ist. (*)

Da man auf diese Weise nicht sukzessiv $\begin{eqnarray*} 1\cdot 2\cdot 3\cdot \ldots \end{eqnarray*}$ vorgeht, benötigt man zum Merken der Faktoren, die man bereits verarbeitet hat, noch ein boolesches Feld der Länge $\begin{eqnarray*} n \end{eqnarray*}$ . Was das Bewerkstelligen der obigen Gruppierung betrifft, da knöpft man sich am besten zuerst alle durch 5 teilbaren Faktoren des Produkts $\begin{eqnarray*} n! \end{eqnarray*}$ vor und ergänzt sie durch noch verfügbare gerade Zahlen, bis man Effekt (*) erreicht. Die letzte Nicht-Null-Ziffer des Gruppenprodukts geht dann sukzessive in die Rechnung ein.

EDIT: Ich korrigiere mich: Bei geschickter Organisation der Berechnung benötigt man nicht mal das genannte boolesche Feld. Augenzwinkern

---------------------------------------------------

Das wäre die Brachialvariante, eine elegante Berechnung ohne Computerunterstützung würde natürlich mehr hermachen. Die müsste natürlich Effekte wie oben berücksichtigen, also dass etwa beim Übergang von $\begin{eqnarray*} 390624! \end{eqnarray*}$ zu $\begin{eqnarray*} 390625! \end{eqnarray*}$ auf einen Schlag 8 zusätzliche Endnullen hinzukommen, dass man also zur Bestimmung der letzten Nicht-Null von $\begin{eqnarray*} 390625! \end{eqnarray*}$ sogar die letzten 9 Nicht-Nullen von $\begin{eqnarray*} 390624! \end{eqnarray*}$ kennen muss...

04.12.2010, 10:25

strike300

Auf diesen Beitrag antworten »

Hallo zusammen,
das ging ja schnell :-). Ja, jetzt wo man es hört, war es tatsächlich ziemlich dämlich, was ich da gemacht hatte.

Ein Computerprogramm ist keine Lösung. Die Ziffer allein ohne Begründung wäre auch keine Lösung, da man ja schon mit 25 % Wahrscheinlichkeit richtig raten kann.

Ich habe mal alle 5en und 2en aus 1.000.000 rausgezogen:

$\begin{eqnarray*} 1000000! = 10^{249998} \cdot 2^{749995} \cdot der Rest \equiv 8 \cdot der Rest (mod 10) \end{eqnarray*}$

Und genau beim Rest liegt das Problem. So richtig weiß ich nämlich nicht was da alles übrigbleibt (Vielfache von Primzahlen usw.). Ich nehme mal an, dass das per Hand der falsche Weg ist und es noch einen schönen Trick gibt.

Mit dem Computer könnte man auch einfach so wie oben mit 2 und 5 alle Primfaktoren bis 1.000.000 durchzählen und dann immer (mod 10) multiplizieren. Aber es muss doch auch per Hand gehen.

Vielleicht könnte man nur so viele 2en nehmen wie man für die 5en braucht, dann hätte man nicht so viele Faktoren verändert.

Ich bin völlig ideenlos gerade.

Vielleicht hätte jemand noch einen Schubs in die richtige Richtung?

Danke schonmal bis hierher
Grüße
Sven

04.12.2010, 11:07

René Gruber

Auf diesen Beitrag antworten »

Ok, hier dann mal eine Anregung (oder vielleicht schon mehr als das) zur theoretischen Variante:

Sei $\begin{eqnarray*} Z(k) \end{eqnarray*}$ die letzte Nicht-Null-Ziffer der positiven ganzen Zahl $\begin{eqnarray*} k \end{eqnarray*}$ . Klar ist dann $\begin{eqnarray*} Z(k_1\cdot k_2) \equiv Z(k_1)\cdot Z(k_2) \bmod 10 \end{eqnarray*}$ sofern $\begin{eqnarray*} Z(k_1)\cdot Z(k_2) \not\equiv 0\bmod 10 \end{eqnarray*}$ .

Betrachten wir nun mal $\begin{eqnarray*} (5n)! \end{eqnarray*}$ für beliebiges $\begin{eqnarray*} n \end{eqnarray*}$ :

$\begin{eqnarray*} (5n)! = \prod\limits_{k=1}^{5n} k = \prod\limits_{m=1}^n (5m) \cdot \prod\limits_{m=1}^n (5m-4)(5m-3)(5m-2)(5m-1) = n! \cdot \prod\limits_{m=1}^n 5(5m-4)(5m-3)(5m-2)(5m-1) \end{eqnarray*}$ .

Nun ist (nachrechnen!)

$\begin{eqnarray*} (10k-4)(10k-3)(10k-2)(10k-1) \equiv 24\bmod 100 \end{eqnarray*}$
$\begin{eqnarray*} (10k+4)(10k+3)(10k+2)(10k+1) \equiv 24\bmod 100 \end{eqnarray*}$ ,

also insgesamt $\begin{eqnarray*} 5(5m-4)(5m-3)(5m-2)(5m-1) \equiv 5\cdot 24 \equiv 20\bmod 100 \end{eqnarray*}$ , was $\begin{eqnarray*} Z(5(5m-4)(5m-3)(5m-2)(5m-1)) = 2 \end{eqnarray*}$ zur Folge hat. Daraus folgt dann die simple Rekursion

$\begin{eqnarray*} Z((5n)!) \equiv 2^n \cdot Z(n!) \bmod 10 \end{eqnarray*}$ .

Mit ein paar Zusatzüberlegungen kann man dann rekursiv alles sehr schnell herunterbrechen.

05.12.2010, 12:54

strike300

Auf diesen Beitrag antworten »

Hallo nochmal,
Danke für den ausführlichen Lösungsweg. Den habe ich soweit verstanden und habe es auch noch durchgerechnet:

$\begin{eqnarray*} Z((5\cdot 200000)!)\equiv 2^{200000} \cdot Z(200000!) mod 10 \end{eqnarray*}$

$\begin{eqnarray*} \cdot \end{eqnarray*}$

$\begin{eqnarray*} \cdot \end{eqnarray*}$

$\begin{eqnarray*} \cdot \end{eqnarray*}$

$\begin{eqnarray*} \equiv 2^{249984} \cdot Z(64!) mod 10 \end{eqnarray*}$

$\begin{eqnarray*} \equiv 6 \cdot Z(64 \cdot 63 \cdot 62 \cdot 61) \cdot Z((5 \cdot 12)!) mod 10 \end{eqnarray*}$

$\begin{eqnarray*} \equiv 6 \cdot 4 \cdot 2^{12} \cdot Z(12!) mod 10 \end{eqnarray*}$

$\begin{eqnarray*} \equiv 3 \cdot 2^{15} \cdot Z(12 \cdot 11) \cdot Z((5 \cdot 2)!) mod 10 \end{eqnarray*}$

$\begin{eqnarray*} \equiv 3 \cdot 2^{16} \cdot 2^{2} \cdot Z(2!) mod 10 \end{eqnarray*}$

$\begin{eqnarray*} \equiv 3 \cdot 2^{19} mod 10 \end{eqnarray*}$

$\begin{eqnarray*} \equiv 3 \cdot 8 mod 10 \equiv 4 mod 10 \end{eqnarray*}$

Soweit so gut. Da stellt sich für mich nur noch eine Frage: Wie kommt man auf so einen Lösungsansatz? Probiert man einfach mit 5 und 2 ein wenig rum und stellt dann fest, dass günstigerweise $\begin{eqnarray*} 1 \cdot 2 \cdot 3 \cdot 4 \equiv 6 \cdot 7 \cdot 8 \cdot 9 \equiv 4 mod 10 \end{eqnarray*}$ ?
Oder gibt es einen zwingenden Grund, warum man auf so etwas kommen muss?

Viele Grüße
Sven

05.12.2010, 13:02

René Gruber

Auf diesen Beitrag antworten »

Zitat:

Original von strike300
Wie kommt man auf so einen Lösungsansatz?

Erfahrung erwirbt man mit der Zeit und kann sie nicht mal schnell in 5 Minuten vermitteln. Augenzwinkern

Bisschen probieren hilft auch: Das Ausrechnen von $\begin{eqnarray*} 1\cdot 2\cdot 3\cdot 4 \end{eqnarray*}$ , $\begin{eqnarray*} 6\cdot 7\cdot 8\cdot 9 \end{eqnarray*}$ , $\begin{eqnarray*} 11\cdot 12\cdot 13\cdot 14 \end{eqnarray*}$ ... hilft schon mal, auf so eine Vermutung zu kommen, die sich dann ziemlich einfach nachweisen lässt. Probieren ist zwar keine Beweismethode, aber zur Ideenfindung offenbar viel zu unterschätzt.

Übrigens, in dem Zusammenhang: Da weitergehend sogar $\begin{eqnarray*} (5m-4)(5m-3)(5m-2)(5m-1) \equiv 24\bmod 1000 \end{eqnarray*}$ und mithin $\begin{eqnarray*} 5(5m-4)(5m-3)(5m-2)(5m-1) \equiv 120\bmod 1000 \end{eqnarray*}$ gilt, kann man mit der obigen Methode sogar relativ einfach die zwei letzten Ziffern $\begin{eqnarray*} Y(k) \end{eqnarray*}$ vor den Endnullen der Fakultäten über die Rekursion

$\begin{eqnarray*} Y((5n)!) \equiv 12^n \cdot Y(n!) \bmod 100 \end{eqnarray*}$

berechnen, in deinem Fall dann $\begin{eqnarray*} Y(1000000!) = 44 \end{eqnarray*}$ .

05.12.2010, 13:20

strike300

Auf diesen Beitrag antworten »

Dann hoffe ich mal, dass ich die Erfahrung auch noch sammeln kann, aber ich schätze als Informatiker im 1. Semester habe ich da noch viel Spielraum Augenzwinkern

Vielen Dank nochmal und vielleicht bis bald.

Viele Grüße
Sven

Neue Frage »

Antworten »

Letzte Ziffer ungleich 0 von 1.000.000 Fakultät

Verwandte Themen