Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » kleinste Zahl n, so dass n! mit mindestens k Nullen endet
Autor
Universität/Hochschule kleinste Zahl n, so dass n! mit mindestens k Nullen endet
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 185
  Themenstart: 2021-06-25

Hallo, Gegeben ist eine natürliche Zahl \(k \in \mathbb{N}\) es soll die kleinste Zahl \(n \in \mathbb{N}\) gefunden werden, so dass \(n!\) mindesens \(k\) Nullen am Ende hat. Hat jemand eine Idee, wie das effizient berechnet werden kann? Danke!


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2935
  Beitrag No.1, eingetragen 2021-06-25

Bestimme die Potenz der 5 in der Fakultät. Das geht sehr einfach.


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 185
  Beitrag No.2, vom Themenstarter, eingetragen 2021-06-25

Danke für deine schnelle Antwort. Aber \quoteon(2021-06-25 10:13 - DerEinfaeltige in Beitrag No. 1) Bestimme die Potenz der 5 in der Fakultät. \quoteoff hierfür braucht man doch wenn ich dich richtig verstehe erstmal eine Fakultät, auf die muss man erst einmal kommen oder nicht?


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2466
  Beitrag No.3, eingetragen 2021-06-25

\quoteon(2021-06-25 18:50 - dvdlly in Beitrag No. 2) hierfür braucht man doch wenn ich dich richtig verstehe erstmal eine Fakultät, auf die muss man erst einmal kommen oder nicht? \quoteoff Um die Ordnung von 5 in $n!=n\cdot(n-1)\cdots2\cdot1$ zu bestimmen, muss man dieses Produkt ja nicht ausrechnen.


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 185
  Beitrag No.4, vom Themenstarter, eingetragen 2021-06-25

Danke für deine Antwort. Also ich weiß, dass ich die Anzahl der Nullen am Ende einer Zahl \(n!\) erhalte, indem ich sukzessive \(\frac{n}{5} =: y_1\) berechne bis \(5 \nmid y_k\) wobei \(y_{i+1} = \frac{y_i}{5}\) gilt und die Ergebnisse summiere. Meint ihr also, dass ich mit einer Zahl \(n!\) "anfangen" soll, davon die \(5\) Potenz berechnen soll, dann prüfen soll, ob sie genug Nullen am Ende hat und falls nicht die nächst höhere nehmen soll bis ich die richtige Zahl finde?


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
Kezer
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.10.2013
Mitteilungen: 1389
  Beitrag No.5, eingetragen 2021-06-25

\(\begingroup\)\(\newcommand{\Q}{\mathbb{Q}} \newcommand{\N}{\mathbb{N}} \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\C}{\mathscr{C}} \newcommand{\OO}{\mathcal{O}} \newcommand{\Spec}{\operatorname{Spec}} \newcommand{\Gal}{\operatorname{Gal}} \newcommand{\tr}{\operatorname{tr}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\Ab}{\mathbf{Ab}} \newcommand{\Set}{\mathbf{Set}} \newcommand*\dd{\mathop{}\!\mathrm{d}}\) Nein, die Bestimmung der Anzahl der 5'er ist eine Kombinatorikaufgabe. Fange vielleicht damit an, kleine Beispiele zu probieren. Z.B.: - $1!, 2!, 3!, 4!$ enthalten $0$ mal den Faktor $5$, - $5!, 6!, 7!, 8!, 9!$ enthalten $1$ mal den Faktor $5$, - ... Eventuell ist dir jetzt die Struktur der Fakultät ein bisschen klarer.\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 1022
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
  Beitrag No.6, eingetragen 2021-06-25

So "ohne" ist die Anforderung wirklich nicht! Spätestens für \(k=6\) wird sich unter den gefundenen Formeln die "Spreu vom Weizen trennen"... 😉


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2935
  Beitrag No.7, eingetragen 2021-06-26

Für eine grobe Abschätzung reicht die geometrische Reihe. $N$ sei die gewünschte Fünferpotenz/Anzahl der Nullen \[N \leq n \cdot \sum_{k=1}^{\log_5(n)} (\frac{1}{5})^k \leq \frac{1}{4}\cdot n\] \[n \geq 4 \cdot N\] Etwas komplizierter scheint die entsprechende obere Schranke: Ich erhalte \[n \leq 4 \cdot N + 4\cdot \log_5(N) + 1\] @Kezer: Mich würde deine kombinatorische Lösung interessieren. Hast du einen Tipp?


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2466
  Beitrag No.8, eingetragen 2021-06-26

\quoteon(2021-06-26 09:48 - DerEinfaeltige in Beitrag No. 7) Mich würde deine kombinatorische Lösung interessieren. \quoteoff Jeder 5. Faktor ist durch 5 teilbar, jeder 25. durch 25 usw. Also ist$$ \operatorname{ord}_5(n!)=\sum_{j>0}\left\lfloor\frac n{5^j}\right\rfloor \;.$$Damit endet z.B. $4700!$ mit$$ \left\lfloor\frac{4700}{3125}\right\rfloor + \left\lfloor\frac{4700}{625}\right\rfloor + \left\lfloor\frac{4700}{125}\right\rfloor + \left\lfloor\frac{4700}{25}\right\rfloor + \left\lfloor\frac{4700}{5}\right\rfloor = 1 + 7 + 37 + 188 + 940 = 1.173 $$Nullen.


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
Kuestenkind
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2016
Mitteilungen: 2068
  Beitrag No.9, eingetragen 2021-06-26

Huhu, siehe dazu z.B. auch diesen alten Thread mit 2 netten Aufgaben aus der Wurzel: https://matheplanet.de/matheplanet/nuke/html/viewtopic.php?rd2&topic=244136&start=0#p1778066 Gruß, Küstenkind


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2935
  Beitrag No.10, eingetragen 2021-06-26

\quoteon(2021-06-26 10:22 - zippy in Beitrag No. 8) \quoteon(2021-06-26 09:48 - DerEinfaeltige in Beitrag No. 7) Mich würde deine kombinatorische Lösung interessieren. \quoteoff Jeder 5. Faktor ist durch 5 teilbar, jeder 25. durch 25 usw. Also ist$$ \operatorname{ord}_5(n!)=\sum_{j>0}\left\lfloor\frac n{5^j}\right\rfloor \;.$$Damit endet z.B. $4700!$ mit$$ \left\lfloor\frac{4700}{3125}\right\rfloor + \left\lfloor\frac{4700}{625}\right\rfloor + \left\lfloor\frac{4700}{125}\right\rfloor + \left\lfloor\frac{4700}{25}\right\rfloor + \left\lfloor\frac{4700}{5}\right\rfloor = 1 + 7 + 37 + 188 + 940 = 1.173 $$Nullen. \quoteoff Das ist klar, scheint jedoch am Thema vorbeizugehen. Gesucht ist hier ja die zugehörige Umkehrfunktion. Wir wollen nicht wissen, wie viele Nullen $n!$ hat, sondern welches minimale $n$ (mindestens) die gewünschte Anzahl Nullen besitzt.


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
Kuestenkind
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2016
Mitteilungen: 2068
  Beitrag No.11, eingetragen 2021-06-26

Huhu DerEinfaeltige, ich habe keine Ahnung von Informatik, aber hier wird als obere Schranke einfach \(5N\) genommen - und, falls ich das richtig verstehe (?), suchen die dann sogar im Intervall \([0,5N]\). Du hattest ja schon als untere Grenze \(4N\) ausgemacht - bzw. man kann auch noch sagen, dass \(n\) sicherlich ein Vielfaches von 5 seien muss, wie André Nicolas hier auch feststellt. Gruß, Küstenkind


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2466
  Beitrag No.12, eingetragen 2021-06-26

\quoteon(2021-06-26 10:45 - DerEinfaeltige in Beitrag No. 10) Das ist klar, scheint jedoch am Thema vorbeizugehen. Gesucht ist hier ja die zugehörige Umkehrfunktion. \quoteoff Ausgehend von dieser Formel kann man nach $n$ auflösen, indem man die gewünschte Zahl der Nullen $k$ nach $a_j=5^j+\cdots+1$ entwickelt. Nur als Beispiel (das müsste man aber noch sauber aufarbeiten): Es ist $$ 1173 = 1\cdot781+2\cdot156+2\cdot31+3\cdot6+0\cdot1 \;. $$Damit ergibt sich für das kleinste $n$ mit $\operatorname{ord}_5(n!)=k$$$ 1\cdot5^5+2\cdot5^4+2\cdot5^3+3\cdot5^2+0\cdot5^1=4700 \;. $$Wenn in der Entwicklung von $k$ nach $a_j$ ein Koeffizient $5$ auftritt, ist das ein Zeichen dafür, dass zu diesem $k$ kein $n$ mit $\operatorname{ord}_5(n!)=k$ existiert, weil $n\mapsto\operatorname{ord}_5(n!)$ einen Sprung macht. Das ist aber kein Problem, weil man ja nicht genau, sondern nur mindestens $k$ Nullen haben möchte. In der Entwicklung muss man in diesem Fall einfach den zuvor berechneten Koeffizienten um 1 hochsetzen. Beispiel: $k=5$ hat die Entwicklung $5=0\cdot6+5$. Man ersetzt die $0$ durch eine $1$ und erhält $6=1\cdot6+0$. Dazu gehört $n=1\cdot5^2+0\cdot5=25$, und $25!$ hat $6$ Nullen statt der geforderten Mindestzahl von $5$ (während $24!$ mit nur $4$ Nullen zu wenige hat). Analog: $k=60=31+4\cdot6+5$ wird erst zu $61=31+5\cdot6$ und dann zu $62=2\cdot31$ und liefert $n=2\cdot5^3=250$. Und $250!$ hat $62$ Nullen, während $249!$ nur $59$ hat. [Die Antwort wurde vor Beitrag No.1 begonnen.]


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 2935
  Beitrag No.13, eingetragen 2021-06-26

@zippy: Schöne Lösung! :)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 1984
Wohnort: Thüringen
  Beitrag No.14, eingetragen 2021-06-26

Ich habe mich auch mal damit beschäftigt... Leider kann ich nur die Nullen zu einer Fakultät bestimmten :-( Zum Bsp. Man will die Nullen für (82*5)! haben, dann sind dies 82+3(3-2)+16(2-1)=101. Die 3 ist aus [82/25] und die 16 aus [82/5] Also 410! hat 101 Nullen. Man kommt ohne Summation am Ende nicht aus. 2. Bsp. Wieviele Nullen hat 333! ? 333/5=66 -> 66+2(3-2)+13(2-1)=81 Nullen Irrtum vorbehalten....


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 1022
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
  Beitrag No.15, eingetragen 2021-06-26

Hallo dvdlly, \quoteon(2021-06-25 10:06 - dvdlly im Themenstart) [...] Hat jemand eine Idee, wie das effizient berechnet werden kann? Danke! \quoteoff Von "effizient" mag ich noch nicht sprechen, aber was "effektiv" anbelangt, so hat zippy es bereits schön dargelegt. Mein "Lösungsweg" verläuft grundsätzlich ähnlich... "Mindestens \(k\) Nullen am Ende" bedeutet ja zunächst "mindestens durch \(10^k\) teilbar", und selbiges ist im Hinblick auf Fakultäten pragmatisch gleich zu "mindestens \(k\) mal Primfaktor \(5\). Die ebenfalls benötigten Primfaktoren \(2\) bekommt man bei Vergrößerung von \(n\) "im Übermaß nachgeworfen". 😉 Das kleinste \(n_1!\) , welches auf mindestens eine Null endet, muss demnach \(5=1\cdot5\) sein! Allgemein taugt jedoch \(k\cdot5\) in der Tat bloß als obere Schranke, weil bei schrittweiser Vergrößerung von \(n\) um \(1\) bei jeder neuerlich erreichten Fünferpotenz ein "Sprung" erfolgt - alle fünf um einen, alle fünfundzwanzig um zwei, alle einhunderfünfundzwanzig um drei usw. Siehe auch hierzu schon zippys Ausführungen. Man wird sich also nurmehr "heranrobben" können! Ich beginne mit dem vorgegebenem \(k\) als oberem Schrankenwert \(s\) für ein Vielfaches von \(5\) . Dann wandele ich \(s\) in eine Fünferzahl um. Und deren Ziffern interpretiere ich dann mir genehm von hinten her: Die letzte Ziffer hat einen "Wert" von 1! Die jeweils nächste Ziffer nach links hat als "Wert" das Fünffache desjenigen der vorherigen Ziffer, erhöht um 1! Demnach "von hinten her": 1 ; 6 ; 31 ; 156 ; 781 ... Ist nach dieser "Rückauswertung" der "Wert" von \(s\) größer als \(k\) , so wird \(s\) um \(1\) vermindert, und das ganze wiederholt. Sobald \(s=k\) , ist Schluss, und für \(sBeispiel: Sei \(k=85\) vorgegeben. \(\Rightarrow\) \(s_1=85\) ; \(85_{10}\:=\:320_5\) ; \(320_c\:=\:0\cdot1\,+2\cdot6\,+3\cdot31\:=105\:>\:85\) \(\Rightarrow\) \(s_2=84\) ; \(84_{10}\:=\:314_5\) ; \(314_c\:=\:4\cdot1\,+1\cdot6\,+3\cdot31\:=103\:>\:85\) \(\Rightarrow\) \(s_3=83\) ; \(83_{10}\:=\:313_5\) ; \(313_c\:=\:3\cdot1\,+1\cdot6\,+3\cdot31\:=102\:>\:85\) ... \(\Rightarrow\) \(s_{16}=70\) ; \(70_{10}\:=\:240_5\) ; \(240_c\:=\:0\cdot1\,+4\cdot6\,+2\cdot31\:=86\:>\:85\) \(\Rightarrow\) \(s_{17}=69\) ; \(69_{10}\:=\:234_5\) ; \(240_c\:=\:4\cdot1\,+3\cdot6\,+2\cdot31\:=84\:<\:85\) \(\Rightarrow\) \(s\:=\:s_{16}\:=\:70\) ; \(n\:=\:70\,\cdot\,5\:=\:350\) \(\Rightarrow\) \(350!\) endet "als erste" auf \(86\) fortlaufende Nullen. Die Effizienz ließe sich umgehend steigern, wenn man, wie DerEinfaeltige schon angedeutet hatte, trickreich mit dem Fünferlogarithmus von \(k\) ... "herumspielt"...?! [Die Antwort wurde nach Beitrag No.13 begonnen.]


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
schlauuu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2021
Mitteilungen: 29
  Beitrag No.16, eingetragen 2021-06-26

siehe hier https://www.youtube.com/watch?v=M6HZEzVI_c8


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 1984
Wohnort: Thüringen
  Beitrag No.17, eingetragen 2021-06-26

Eine schöne Abschätzung nach Zippys Bsp mit 4700! ((((1*5+1)*5+1)*5+1)*5+1)*4700/5^5=1174 Nullen Das resultiert aus der Bildung das Hauptnenners. wäre k=10, weil LOG(N)/LOG(5)>=10 ist, ist das Verfahren der Verfünffachung k-1 mal durchzuführen. Also 17123 ! hätte etwa: k=6 (((((1*5+1)*5+1)*5+1)*5+1)*5+1)*17123/5^6=4280 Nullen. (4277 exakt) [Die Antwort wurde nach Beitrag No.15 begonnen.]


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 1022
Wohnort: Schwäbischer Wald, seit 1989 freiwilliges Exil in Bierfranken
  Beitrag No.18, eingetragen 2021-06-26

Danke, schlauuu 🤗 [Fast] so weit war ich schon kurz nach dem Verfassen meines vorherigen Beitrages. Man beginne also die Schleife "unten" mit \(s\:=\:\lfloor\frac{4\,\cdot\, k}{5}\rfloor\) und erhöhe ggf. \(s\) so oft jeweils um \(1\) , bis \(c(s)\geq k\) ! Das ist in der Tat schon leidlich "effizient". 🤔


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil
dvdlly hat die Antworten auf ihre/seine Frage gesehen.
dvdlly wird per Mail über neue Antworten informiert.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]