La formula di Legendre e la sua utilità nelle applicazioni

Premessa

Siamo partiti da un presupposto, siamo interessati ad un problema, che ci serve per sviluppare un algoritmo efficiente per i fattoriali: vogliamo trovare la massima potenza di 2 che divide n!. Questo significa che vogliamo estrarre tutti i due che possiamo e formare la massima potenza, cioè :

Ci viene in aiuto una famosa formula matematica. Appunto la formula di Legendre e ci da la massima potenza di 2 che divide n! In realtà questa formula  è anche più generale cioè è in grado di darci il 𝞶 (valutazione du-adica) anche per altre basi non soltanto per il 2. A noi ci interessa usare la massima potenza di due perché per il computer è un operazione immediata. Perché basta che setta un bit nella rappresentazione binaria di un numero. Quindi non deve fare nessun algoritmo o particolare procedimento. Deve soltanto impostare un bit e nessuno dispendio dal punto di vista computazionale.

In generale  la base può essere un primo qualunque, e l'esponente viene chiamato la valutazione p-adica di M, con M qualunque intero positivo.

La formula di Legendre ci risponde a questo problema generale, cioè dato un qualunque primo(primo) ci consente di trovare la massima potenza di quel primo che divide n!
Quindi dati n! ci da il 𝞶 cioè la massima potenza di p che divide n! e sara :