Variazioni Pialiche per la fattoriazzazione di n!

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
Julito
Messaggi: 32
Iscritto il: 29 dic 2013, 14:34
Località: Brescia

Variazioni Pialiche per la fattoriazzazione di n!

Messaggio da Julito » 29 dic 2013, 14:48

Salve,
conosco l'algoritmo per fattorizzare n!, e mi ricordo che tale algoritmo discendeva dal concetto di VARIAZIONI PIALICHE (?) con riferimento ad una formula di Legendre-..... (e non ricordo il nome dell'altro matematico). Qualcuno mi potrebbe aiutare con del materiale in merito? Grazie.

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Re: Variazioni Pialiche per la fattoriazzazione di n!

Messaggio da ma_go » 29 dic 2013, 15:42

ciao Julito, e benveuto sul forum. ho spostato la tua domanda nel glossario, dove mi sembra più pertinente.

detto questo, credo che tu ti riferisca a questa.
si parla di valutazioni $p$-adiche (su wikipedia dovrebbe esserci tutto il materiale necessario, e molto di più).

per fare i pedanti: le formule che ti danno la fattorizzazione di $n!$ non discendono dal concetto di valutazione $p$-adica, ma, semmai, le valutazioni $p$-adiche ti danno una mano a formulare il teorema di legendre-de polignac in modo più compatto. non c'è niente di misterioso o di non elementare, né dietro l'enunciato, né dietro la dimostrazione. al massimo sono un po' mascherate.

EvaristeG
Site Admin
Messaggi: 4756
Iscritto il: 01 gen 1970, 01:00
Località: Roma
Contatta:

Re: Variazioni Pialiche per la fattoriazzazione di n!

Messaggio da EvaristeG » 29 dic 2013, 15:58

:D credo fosse "valutazioni p-adiche" (letto piadiche), ma non mi sembra il caso di parlare così difficile... basta ragionare un pochino:
diciamo che vogliamo sapere quale esponente ha $2$ nella fattorizzazione di $n!$, allora la prima cosa che ci viene in mente è
- quanti numeri divisibili per $2$ compaiono nel prodotto $n!=1\cdot\ldots\cdot n$?
e qui è facile, perché è la parte intera di $n/2$, ovvero $[n/2]$.
Poi però ci si accorge che, ad esempio, $4$ contribuisce con 2 fattori 2 e quindi per ogni multiplo di 4 che incontriamo dobbiamo contare un altro fattore 2, al che ci domandiamo
- quanti numeri divisibili per $4$ compaiono del prodotto $n!$ ?
e la risposta è ancora facile: $[n/4]$.
Ora dobbiamo guardare i multipli di 8, che danno ancora un fattore $2$ in più e poi i multipli di 16 e così via. Quindi alla fine quanti $2$ compaiono nel prodotto $n!$?
Beh i 2 dei pari + i secondi 2 dei multipli di 4 + i terzi 2 dei multipli di 8 + ...
ovvero
$$[n/2]+[n/4]+[n/8]+\ldots + [n/2^k]$$
dove k è (l'unico intero) tale che $2^k\leq n < 2^{k+1}$.
Quindi, nella fattorizzazione di $n!$, l'esponente di $2$ è dato da $[n/2]+[n/4]+[n/8]+\ldots + [n/2^k]$ (dove $2^k$ è la più grande potenza di 2 che sia minore od uguale a $n$).

Ora credo tu intuisca (e ti invito però a scrivere questa tua intuizione) come si ricavano gli altri esponenti.

Noiosa nomenclatura snobbista
Dati un numero naturale $n$ ed un numero primo $p$, la valutazione p-adica di $n$ si indica con $v_p(n)$ ed è il numero naturale $h$ tale che $p^h$ divide $n$, ma $p^{h+1}$ non divide $n$ (si dice allora che $p^h$ divide esattamente $n$ e si scrive $p^h\parallel n$).
La fattorizzazione unica di un numero $n$ si può scrivere come
$$n=2^{v_2(n)}\cdot 3^{v_3(n)}\cdot 5^{v_5(n)}\cdot\ldots$$
con un prodotto che, sulla carta, è infinito (perché devono comparire tutti i primi), ma in pratica solo un numero finito di fattori conta, in quanto, se $p>n$, $v_p(n)=0$ e dunque $p^{v_p(n)}=1$.

La formula di de Polignac dice che
$$v_p(n!)=\sum_{h=1}^{\infty}\left[\dfrac{n}{p^h}\right]$$
ed anche qui la somma sembra infinita, ma non appena $h>\log_p(n)$ (ovvero non appena $p^h>n$), si ha che $0<n/p^h<1$ e dunque la sua parte intera è 0, dunque c'è solo un numero finito di termini in quella somma. La dimostrazione è il ragionamento che ho scritto sopra.

Rispondi