Zählen von nachgestellten Nullen von Fakultätszahlen in einem beliebigen Zahlensystem

Wie kann ich die Anzahl der nachgestellten Nullen der Fakultät einer Zahl in einem bestimmten Zahlensystem berechnen?

Schauen wir uns den Fall an, in dem wir uns im 10. Zahlensystem befinden, und sehen wir dann, wie wir dies zu einer universellen Lösung verallgemeinern können. Wir erhalten die Zahl N und für ihre Fakultät müssen wir die Anzahl der nachgestellten Nullen finden. Die Lösung wird ganz einfach sein - die Summe:

Math.floor(N/5) + Math.floor(N/25) + Math.floor(N/125) + Math.floor(N/625) + ... 

Wir können es in eine solche Formel verallgemeinern:

$$

$$\ sum \ limit_ {i = 1} ^ \ infty {N \ over 5 ^ i}.$$

Warum 5? Das ist einfach. Die endgültige Null wird nur erhalten, wenn die Zahl 10 in der Fakultät hat. Wenn wir also die Anzahl der Zehner in der Fakultät zählen, ermitteln wir die Anzahl der endlichen Nullen.

Warum teilen wir im obigen Beispiel durch 5? Da 10 durch Multiplizieren von 5 mit 2 erhalten werden kann, hat die vollständige Lösung zwei Formeln:

$$

$$\ sum \ limit_ {i = 1} ^ \ infty {N \ over 5 ^ i}$$

und

$$

$$\ sum \ limit_ {i = 1} ^ \ infty {N \ over 2 ^ i}.$$

Aus logischen Gründen wissen wir jedoch, dass der erste Betrag geringer sein wird, sodass wir ihn nur berechnen müssen (weitere Details finden Sie hier ).

Lösung für unser Problem

Um die letzten Nullen der Fakultät einer Zahl in einem bestimmten Zahlensystem zu berechnen, habe ich den folgenden Algorithmus zusammengestellt :

1. Faktor die Zahl B des Zahlensystems.
2. Teilen Sie die Zahl N durch jeden eindeutigen Primfaktor K und multiplizieren Sie K mit sich selbst bis $$$N \ über K$ wird mehr als eins sein, während jedes Ergebnis auf eine kleinere ganze Zahl gerundet wird.
3. Wenn wir beim Erweitern der Zahl des Zahlensystems mehrere identische Primfaktoren K erhalten, sollten wir das obige Ergebnis durch die Zahl der identischen K dividieren.
4. Wählen Sie aus allen Divisionen von N durch jeden einzelnen Faktor K den kleinsten Quotienten, der unsere Antwort sein wird.

Ich werde es mit einem Beispiel zeigen.
Sei die Zahl N = 5, das Zahlensystem B = 12. Faktor 5! = 120 und 120 im 12. System ist A0. Wir sehen, dass in einem endlichen Zahlensystem die Fakultät der ursprünglichen Zahl eine Null hat. Wenn wir 12 in Primfaktoren zerlegen, erhalten wir 2, 2, 3. Wir haben zwei eindeutige Zahlen: 2 und 3. Nach unserem Algorithmus erfüllen wir Punkt 2 mit der Zahl 2.

$$

$${5 \ über 2} + {5 \ über 4} + {5 \ über 8} + ... = 2 + 1 + 0 + ... = 3.$$

Aber die Zwei haben sich bei der Zerlegung von 12 zweimal getroffen, also teilen wir das Endergebnis durch 2 und runden auf eine kleinere ganze Zahl. Als Ergebnis erhalten wir 1.

Wir machen dasselbe mit 3:

$$

$${5 \ over 3} + {5 \ over 9} + ... = 1 + 0 + ... = 1.$$

Somit haben wir zwei Quotienten von Divisionen der Zahl N durch Primfaktoren der Zahl des Zahlensystems erhalten. Sie sind beide gleich 1, daher müssen wir nicht die kleinere auswählen und geben nur die Antwort - 1.

Betrachten Sie ein anderes Beispiel.

Sei die Zahl N = 16, das Zahlensystem B = 16. Die Fakultät 16! = 20922789888000 und 20922789888000 im 16. System - 130777758000. Wir sehen, dass im endgültigen Zahlensystem die Fakultät der ursprünglichen Zahl drei Nullen hat. Wenn wir 16 in Primfaktoren zerlegen, erhalten wir 2, 2, 2, 2. Hier haben wir nur eine eindeutige Zahl, daher wird Punkt 2 nur einmal ausgeführt:

$$

$${16 \ über 2} + {16 \ über 4} + {16 \ über 8} + {16 \ über 16} + {16 \ über 32} + ... = 8 + 4 + 2 + 1 + 0 + ... = 15.$$

Als wir zerlegten, hatten wir vier Zweien, also teilen wir die Summe der Teilungen durch 4 mit Rundung auf eine kleinere ganze Zahl: $$${15 \ over 4} = 3.$

PS Das meiste Material für den Beitrag wurde von hier übersetzt. Gepostet von Aditya Ramesh .