La formula di Legendre e la sua utilità nelle applicazioni

matteos43

In teoria dei numeri, l’identità di Legendre-de Polignac (o formula di Legendre), è una formula che fornisce l’esponente massimo di un numero primo p che divide il fattoriale n!. In altri termini, questa formula permette di ricavare una scomposizione, fissato un numero primo p, di un fattoriale nel seguente modo:

n! = p^\upsilon R

dove R è un intero residuo e \upsilon è il massimo esponente di p che permette tale divisione. Questa è chiamata anche valutazione p-adica di n ed è possibile attuarla per qualsiasi numero primo p. Nonostante possa sembrare una richiesta decisamente articolata, la soluzione è di per sé molto semplice. Per comodità, indicheremo con \upsilon_p(n!) la valutazione p-adica di n!, ovvero la funzione che restituisce l’esponente \upsilon massimo della divisione di n! per un numero primo p. Il suo calcolo è molto semplice, la formula generale infatti è la seguente:

\upsilon_p(n!) = \sum_{j = 1}^\infty\left\lfloor\frac{n}{p^j}\right\rfloor

dove \left\lfloor\frac{n}{p^j}\right\rfloor sarebbe la parte intera della divisione di n per p^j.

Questa formula può essere ulteriormente semplificata se si considera la rappresentazione binaria dei numeri (ovvero esattamente come sono rappresentati su un computer). Infatti, in questo caso la formula sarà la seguente:

\upsilon_p(n!) = \sum_{j = 1}^\infty\left\lfloor\frac{Numero \ di \ bit \ di \ n \ pari \ a \ 1}{p - 1}\right\rfloor

per cui il calcolo in un programma viene notevolmente semplificato.

Lascia un commento