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: 199
  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!


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3000
  Beitrag No.1, eingetragen 2021-06-25

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


   Profil
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 199
  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?


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2717
  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.


   Profil
dvdlly
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.12.2016
Mitteilungen: 199
  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?


   Profil
Kezer
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.10.2013
Mitteilungen: 1463
  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\)


   Profil
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 1111
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"... 😉


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3000
  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?


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2717
  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.


   Profil
Kuestenkind
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2016
Mitteilungen: 2136
  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


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3000
  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.


   Profil
Kuestenkind
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 12.04.2016
Mitteilungen: 2136
  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


   Profil
zippy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 24.10.2018
Mitteilungen: 2717
  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.]


   Profil
DerEinfaeltige
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.02.2015
Mitteilungen: 3000
  Beitrag No.13, eingetragen 2021-06-26

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


   Profil
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 2059
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....


   Profil
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 1111
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.]


   Profil
schlauuu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2021
Mitteilungen: 31
  Beitrag No.16, eingetragen 2021-06-26

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


   Profil
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 2059
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.]


   Profil
cramilu
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 09.06.2019
Mitteilungen: 1111
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". 🤔


   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]