10.000!

Qualche anno fa su una rivista di informatica fu lanciato un concorso.
Calcolare gli zeri finali presenti in 10.000! ed eventualmente calcolare il fattoriale.

Per me un problema è interessante (tra l'altro) quando genera altri problemi che ti stimolano a costruire o studiare una piccola teoria matematica.

Questo problema ha due aspetti: uno poco interessante e l'altro molto interessante.
E' poco interessante calcolare con quanti zeri termina un fattoriale perché ciò riguarda NON l'essenza dei numeri MA SOLTANTO una loro particolare rappresentazione, che è quella decimale.
E' molto interessante calcolare qual è la massima potenza di un numero primo che divide un fattoriale perché ciò è indipendente dalla rappresentazione utilizzata e perciò riguarda l'essenza dei numeri.

Come posso calcolare facilmente la massima potenza di un numero primo che divide un fattoriale?

Per rispondere a questa domanda mi rendo conto che devo costruire una piccola teoria della funzione [parte intera di n].

Ma prima di procedere, vorrei riportare la soluzione inviata da Giorgio Dendi che in pratica è una esemplare dimostrazione di un teorema, sia pur applicata ad un caso particolare.

Ciao. A me risulta ci siano 2.499 zeri finali.
Per ottenere 0 finale, il numero deve essere divisibile per 10, cioè deve esserci un fattore 2 e un 5.
Di 2 ce ne sono molti, i 5 sono di meno.
Quindi ci chiediamo quanti 5 ci sono come fattore.
Ogni cinque numeri consecutivi considerati, uno mi porta un fattore 5: 1 2 3 4 non servono, il 5 mi porta un fattore 5.
Allora in tutto ce ne sono 10.000/5, cioè 2.000.
Ma ogni 5 di questi fattori 5, uno vale il doppio, cioè 5 10 15 20 mi portano un 5, ma il 25 me ne porta 2.
Allora quelli che mi portano un secondo 5 sono 2.000/5, cioè 400.
Anche fra questi c'è uno ogni 5 che mi porta un ulteriore 5, il terzo 5 come fattore. Infatti 25 50 75 100 mi portano ciascuno i due 5 già considerati, ma 125 me ne porta un terzo.
Questi numeri sono in numero di 400/5, cioè 80.
Poi quelli che portano quattro 5 sono 80/5, cioè 16 e quelli che portano cinque 5 come fattore sono 16/5, cioè 3.125, 6.250 e 9.375.
In tutto 2.000 + 400 + 80 + 16 + 3 = 2.499.
Che curioso che sia proprio la quarta parte del numero di cui si calcola il fattoriale. Quasi!
(Giorgio Dendi)

La procedura proposta da Giorgio Dendi può essere generalizzata.
Posso chiedermi, ad esempio: quanti 2 o quanti 23 ci sono in 10.000! ?

La regola in sintesi
Per calcolare l'esponente k della massima potenza di un numero primo p che divide un fattoriale n! si procede così:

[n / p] = q1 (parte intera del quoziente n/p)

[q1 / p] = q2

[q2 / p] = q3

... e così via, fino a trovare un qn < p

Quindi si calcola k, che è la somma dei quozienti parziali.

k = q1 + q2 + q3 + .... + qn

Esempio:
Qual è la massima potenza di 7 che divide 946! ?

[946 / 7] = 135

[135 / 7] = 19

[19 / 7] = 2

135 + 19 + 2 = 156

Risposta: 7^156 è la massima potenza di 7 che divide 946!

Cominciamo con un fattoriale piccolo
Per capire meglio, diamo un'occhiata ad un fattoriale "piccolo".

16! = 16 x 15 x 14 x 13 x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 = 20.922.789.888.000

Osserviamo che il suo sviluppo contiene tutti i numeri interi da 2 a 16.
Se consideriamo il numero primo 2, osserviamo che 16! contiene come fattori:
2, 4, 6, 8, 10, 12, 14, 16, divisibili per 2.
Scomponiamoli in fattori primi:
2, 2², 2x3, 2³, 2x5, 2²x3, 2x7, 2⁴

Più precisamente:
Gli 8 numeri 2, 4, 6, 8, 10, 12, 14, 16 contengono il fattore 2.
Posso ottenere 8 calcolando 16/2 = 8

I 4 numeri 4, 8, 12, 16 contengono il fattore 2^2.
Posso ottenere 4 calcolando 16/2² = 4
O anche dividendo per 2 il numero ottenuto con il calcolo precedente, che era 8.

I 2 numeri 8, 16 contengono il fattore 2^3.
Posso ottenere 2 calcolando 16/2³ = 2
O anche dividendo per 2 il numero ottenuto con il calcolo precedente, che era 4.

Il numero 16 contiene il fattore 2^4.
Posso ottenere 8 calcolando 16/2⁴ = 1
O anche dividendo per 2 il numero ottenuto con il calcolo precedente, che era 2.

Sommando i risultati parziali ottengo il massimo esponente n tale che 2^n divide 16!
8 + 4 + 2 + 1 = 15
Concludo che 2¹⁵ divide 16!

Il problema della parte intera
Osserviamo ora 30!, consideriamo il fattore 3 e proviamo a ripetere il ragionamento precedente.

30! = 30 x 29 x 28 x 27 x 26 x 25 x 24 x 23 x 22 x 21 x 20 x 19 x 18 x 17 x 16 x 15 x 14 x 13 x 12 x 11 x 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 = 2,6525285981219105863630848e+32

Se consideriamo il numero primo 3, osserviamo che 30! contiene come fattori:
3, 6, 9, 12, 15, 18, 21, 24, 27, 30, divisibili per 3.
Scomponiamoli in fattori primi:
3, 2x3, 3², 2²x3, 3x5, 2x3², 3x7, 2³x3, 3³, 2x5x3

Più precisamente:
I 10 numeri 3, 6, 9, 12, 15, 18, 21, 24, 27, 30 contengono il fattore 3.
Posso ottenere 5 calcolando 30/3 = 10

I 3 numeri 9, 18, 27 contengono il fattore 3^2.
Posso ottenere 3 calcolando 30/3² = 3,333... e considerare la parte intera.
Se indico la parte intera di x con [x], posso scrivere:
[30/3²] = [3,333...] = 3
O anche dividendo per 3 il numero ottenuto con il calcolo precedente, che era 10 e considerare la parte intera.
= [10/3] = [3,333...] = 3

Il numero 27 contiene il fattore 3^3.
Posso ottenere 1 calcolando 30/3³ = 1,111... e considerare la parte intera.
[30/3³] = [1,111...] = 1
O anche dividendo per 3 il numero ottenuto con il calcolo precedente, che era 3,333... e considerare la parte intera.
A questo punto devo applicare una proprietà della parte intera, vediamo:
[ [x] / m ] = [ x / m ]
[ [3,333...] / 3] = [ 3 / 3] = 1

Torniamo al nostro 10.000!
Calcolo la massima potenza di 2 che divide 10.000!

10.000/2 = 5.000
10.000/2^2 = 5.000/2 = 2.500
10.000/2^3 = 2.500/2 = 1.250
10.000/2^4 = 1.250/2 = 625
Da questo punto in poi devo considerare la parte intera del risultato, che indico con [x]
[10.000/2^5] = [625/2] = [312,5] = 312
[10.000/2^6] = [[312,5]/2] = [312/2] = 156
Per scrivere quest'ultimo risultato ho applicato la proprietà:
[ [x] / m ] = [ x / m ]
Procedendo allo stesso modo ottengo:
[10.000/2^7] = [156/2] = 78
[10.000/2^8] = [78/2] = 39
[10.000/2^9] = [39/2] = 19
[10.000/2^10] = [19/2] = 9
[10.000/2^11] = [9/2] = 4
[10.000/2^12] = [4/2] = 2
[10.000/2^13] = [2/2] = 1

Osservo che 2^13 = 8.192 è la potenza di 2 più vicina a 10.000 per difetto.
Poiché 2^12 = 16.384, si ha che:
[10.000/2^14] = 0

Addiziono tutti i risultati ottenuti:
5.000 + 2.500 + 1.250 + 625 + 312 + 156 + 78 + 39 + 19 + 9 + 4 + 2 + 1 = 9.995.

Giorgio Dendi
Ciao. A me risulta ci siano 2.499 zeri finali.
Per ottenere 0 finale, il numero deve essere divisibile per 10, cioè deve esserci un fattore 2 e un 5. Di 2 ce ne sono molti, i 5 sono di meno. Quindi ci chiediamo quanti 5 ci sono come fattore.
Ogni cinque numeri consecutivi considerati, uno mi porta un fattore 5: 1 2 3 4 non servono, il 5 mi porta un fattore 5.
Allora in tutto ce ne sono 10.000/5, cioè 2.000. Ma ogni 5 di questi fattori 5, uno vale il doppio, cioè 5 10 15 20 mi portano un 5, ma il 25 me ne porta 2. Allora quelli che mi portano un secondo 5 sono 2.000/5, cioè 400. Anche fra questi c'è uno ogni 5 che mi porta un ulteriore 5, il terzo 5 come fattore. Infatti 25 50 75 100 mi portano ciascuno i due 5 già considerati, ma 125 me ne porta un terzo. Questi numeri sono in numero di 400/5, cioè 80. Poi quelli che portano quattro 5 sono 80/5, cioè 16 e quelli che portano cinque 5 come fattore sono 16/5, cioè 3.125, 6.250 e 9.375. In tutto 2.000 + 400 + 80 + 16 + 3 = 2.499. Che curioso che sia proprio la quarta parte del numero di cui si calcola il fattoriale. Quasi!

Hal
Confermo a livello sperimentale la brillante intuizione di Giorgio Dendi e aggiungo che in effetti ogni numero multiplo di 100 ha esattamente n/4 - 1 zeri finali.

Cesarone
Confermo anch'io. Col programmino vengono 35660 cifre di cui 2499 "0".

Qualche teorema

Notazione: [x] significa "parte intera di x" ed è il più grande intero minore o uguale di x.
x è un numero reale.

Teorema
Per calcolare l'esponente k della massima potenza di un numero primo p che divide un fattoriale n! si procede così:

[

]

[

]

[

]

[

]

---

...

p²

p³

p⁴

Barlumi di dimostrazione.
a) La somma è finita perché, da un certo punto in poi le successive potenze di p saranno maggiori di n e la parte intera dei quozienti di conseguenza sarà uguale a 0.

b) dati i numeri 1, 2, 3, ..., n, ve ne sono [n/p] divisibili per p, [n/p²] divisibili per p² , etc.

Da questo teorema discende la seguente regola abbreviata:

Regola breve
Per calcolare l'esponente k della massima potenza di un numero primo p che divide un fattoriale n! si può procedere così:

[n / p] = q1 (parte intera del quoziente n/p)

[q1 / p] = q2

[q2 / p] = q3

... e così via, fino a trovare un qn < p

Quindi si calcola k, che è la somma dei quozienti parziali.

k = q1 + q2 + q3 + .... + qn

La regola è valida grazie alle seguenti proprietà della parte intera di x.

Proprietà della parte intera di un numero reale, [x]
1. Se n, m, q, r sono interi tali che n = qm + r con 0<=r<=(m-1) allora [n/m] = q
Dimostrazione.
Discende dalla definizione di divisione e di parte intera.

2. Se m è intero positivo e x è reale, allora [[x] / m] = [x/m].
Dimostrazione.
Siano:
n = [x]
x = n + a, con 0<=a<1 (per la definizione di [x]
n = qm + r, con 0<=r<=(m-1)
quindi, sostituendo:
x = qm + r + a

Posso allora scrivere:
[x/m] = [(qm + r + a)/m] = q + [(r + a)/m] = q
infatti
[(r + a)/m] = 0
perché (r + a)<m
Conclusione parziale: [x/m] = q

Posso anche scrivere, per sostituzioni successive:
[[x] / m] = [n / m] = [(qm + r)/m] = [q + r/m] = q
perché r<=(m-1)<m
Conclusione parziale: [[x] / m] = q

Riunendo le due conclusioni parziali ottengo:
[x/m] = [[x]/m]

Come volevasi.