Fattoriale - Bound sulla valutazione piadica
Inviato: 17 dic 2012, 15:27
Dato \( n\) naturale e \(p\) primo, dimostrare che \(n!\) contiene al più \(\displaystyle \lfloor \frac{n-1}{p-1} \rfloor \) fattori p. In simboli:
\( \displaystyle V_p(n!) \leq \lfloor \frac{n-1}{p-1} \rfloor\)
Inoltre vale il segno di uguale se e solo se \(n = p^k \).
Ultima domanda: è un buon bound? Ossia qual'è l'ordine dell'errore della disuguaglianza?
EDIT: Per i più volenterosi, dimostrare che vale anche \( \displaystyle V_p(n!) \geq \frac{n-p}{p-1} - log_p(n) \)
Una conseguenza interessante è che possiamo avere un buond sui fattoriali. Sia \(\displaystyle U(p,n)= \lfloor \frac{n-1}{p-1} \rfloor\) e \( \displaystyle L(p,n) = \frac{n-p}{p-1} - log_p(n)\).
\(\displaystyle \prod_{p\leq n}{p^{L(p,n)}} \leq n! \leq \prod_{p\leq n}{p^{U(p,n)}}\)
\( \displaystyle V_p(n!) \leq \lfloor \frac{n-1}{p-1} \rfloor\)
Inoltre vale il segno di uguale se e solo se \(n = p^k \).
Ultima domanda: è un buon bound? Ossia qual'è l'ordine dell'errore della disuguaglianza?
EDIT: Per i più volenterosi, dimostrare che vale anche \( \displaystyle V_p(n!) \geq \frac{n-p}{p-1} - log_p(n) \)
Una conseguenza interessante è che possiamo avere un buond sui fattoriali. Sia \(\displaystyle U(p,n)= \lfloor \frac{n-1}{p-1} \rfloor\) e \( \displaystyle L(p,n) = \frac{n-p}{p-1} - log_p(n)\).
\(\displaystyle \prod_{p\leq n}{p^{L(p,n)}} \leq n! \leq \prod_{p\leq n}{p^{U(p,n)}}\)
