Fakultäten und Teiler

23.10.2015, 11:56

Bananenmann

Fakultäten und Teiler

Einen schönen Gruß zum Wochenende Wink

Ist es möglich die Potenz eines bestimmten Teilers d von x! zu erwarten / berechnen, ohne die Fakultät tatsächlich berechnen zu müssen? Zum Beispiel d = 2 und x = 8. Es ist 8! = 40320 und dann die Potenz von d = 7. Die Faktorisierung von 8! ist 2^7 * 3^2 * 5^7. Wäre d = 11, dann hieße das Ergebnis 0.

23.10.2015, 12:12

HAL 9000

Auf diesen Beitrag antworten »

Ja, ist möglich. Für Primzahlen $\begin{align*} p \end{align*}$ ist die Sache einfach darstellbar: Der Maximalexponent ist da

$\begin{align*} e_p(n) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor \end{align*}$ .

Auch wenn es wie eine unendliche Reihe aussieht, für festes $\begin{align*} n \end{align*}$ werden alle Reihenglieder $\begin{align*} k > \log_p(n) \end{align*}$ zu Null, so dass es in Wahrheit "nur" eine Summe ist. Augenzwinkern

Eine alternative Darstellung ist $\begin{align*} e_p(n) = \frac{n-Q_p(n)}{p-1} \end{align*}$ , wobei $\begin{align*} Q_p(n) \end{align*}$ die Quersumme der Zahl $\begin{align*} n \end{align*}$ in der $\begin{align*} p \end{align*}$ -adischen Zahlendarstellung ist, dies ermöglicht z.B. die einfache obere Schrankenabschätzung $\begin{align*} e_p(n) \leq \frac{n-1}{p-1} \end{align*}$ .

Für Nichtprimzahlen $\begin{align*} m \end{align*}$ kann man das ganze auf die eben getroffenen Aussagen zurückführen: Ist $\begin{align*} m = p_1^{s_1}\cdot \ldots \cdot p_r^{s_r} \end{align*}$ , so ist der Maximalexponent für $\begin{align*} m \end{align*}$ gleich $\begin{align*} e_m(n) = \min\limits_{i=1,\ldots,r} \left\lfloor \frac{e_{p_i}(n)}{s_i} \right\rfloor \end{align*}$ . Augenzwinkern

Zu deinen Beispielen: Es ist

$\begin{align*} e_2(8) = \left\lfloor \frac{8}{2} \right\rfloor + \left\lfloor \frac{8}{4} \right\rfloor + \left\lfloor \frac{8}{8} \right\rfloor + \left\lfloor \frac{8}{16} \right\rfloor = 4+2+1+0 = 7 \end{align*}$

$\begin{align*} e_{11}(8) = \left\lfloor \frac{8}{11} \right\rfloor = 0 \end{align*}$

(ich hab mal jeweils die Reihe "gestoppt", wenn ein Nullglied auftaucht, denn dann sind auch alle weiteren Glieder gleich Null.)

23.10.2015, 12:34

Bananenmann

Auf diesen Beitrag antworten »

HAL, was wäre das Board ohne dich Gott

Dann ist für 18! = 6.402.373.705.728.000 und p = 5 also 3, weil
$\begin{eqnarray*} e_{5}(18) = floor(\frac{18}{5}) + floor(\frac{18}{25}) = 3 + 0 = 3 \end{eqnarray*}$ (...wie auch immer man die floor-Funktion mit Latex darstellt)

Und ich muss nicht mal die Fakultät berechnen, was bei Zahlen jenseits von 64bit ziemlich zeitaufwendig würde Big Laugh

Vielen Dank!

23.10.2015, 13:27

HAL 9000

Auf diesen Beitrag antworten »

Bei 5 und 18! ist es ja noch auch händisch sofort überblickbar: Die Faktoren 5, 10 und 15 haben jeweils einmal Primfaktor 5, alle anderen nicht. Augenzwinkern

Hier mal noch ein komplexeres Beispiel für Nicht-Primzahlen: Wie ist der Maximalexponent von $\begin{align*} 24 \end{align*}$ in $\begin{align*} 100! \end{align*}$ ?

Wegen $\begin{align*} 24 = 2^3\cdot 3^1 \end{align*}$ berechnen wir zunächst

$\begin{align*} e_2(100) = 50 + 25 + 12 + 6 + 3 + 1 = 97 \end{align*}$

$\begin{align*} e_3(100) = 33 + 11 + 3 + 1 = 48 \end{align*}$

und anschließend

$\begin{align*} e_{24}(100) = \min\left\{ \left\lfloor \frac{e_2(100)}{3}\right\rfloor , \left\lfloor \frac{e_3(100)}{1}\right\rfloor \right\} = \min\left\{ 32, 48 \right\} = 32 \end{align*}$ .

23.10.2015, 13:55

Bananenmann

Auf diesen Beitrag antworten »

Ich glaube, ich sehe, was du meinst. Erst mit den Primfaktoren und dann mit min[floor()...] aus den einzelnen Exponenten. 24 ist evtl ein "unpassendes" Beispiel, aber ich gehe davon aus, dass die min()-Bestimmung für -alle- Primfaktoren gilt. Da 24 nur zwei Primfaktoren hat -> min(ep1, ep2). Für 600 (Primfaktorzerlegung 2^3 * 3^1 * 5^2) dann min(ep1, ep2, ep3).

Soweit richtig?

23.10.2015, 21:06

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Bananenmann
Für 600 (Primfaktorzerlegung 2^3 * 3^1 * 5^2) dann min(ep1, ep2, ep3).

Soweit richtig?

Ja, sofern du die $\begin{align*} e_p \end{align*}$ -Werte vor der Minimumbildung noch durch die zugehörigen Exponenten (von mir oben $\begin{align*} s_i \end{align*}$ genannt) teilst - also genau, wie von mir oben in der Formel beschrieben.

23.10.2015, 21:20

Bananenmann

Auf diesen Beitrag antworten »

Another day saved by HAL9000 Big Laugh

Vielen Dank!

Neue Frage »

Antworten »

Fakultäten und Teiler

Verwandte Themen