Newsgroup: it.hobby.enigmi
Titolo: 100 !

Con quanti zeri finisce 100!   ? (cento fattoriale).

>Con quanti zeri finisce 100!   ? (cento fattoriale).
S
P
O
I
L
E
R
n zeri in fondo al numero significa che 100! e' divisibile n volte per 10.
Condizione necessaria e sufficiente perche' un numero sia divisibile per 10 
e' che sia divisibile per 5 e per 2.
Poiche' 2<5 e' ovvio che in 100! il fattore 2 compare un numero non 
inferiore di volte rispetto al fattore 5.
Di conseguenza, il numero di zeri in fondo a 100! e' pari a quante volte il 
5 si presenta nella sua scomposizione in fattori primi.
100 / 5 = 20: tra i primi 100 numeri ne esistono 20 divisibili per 5
100 / (5^2) = 4: tra i primi 100 numeri ne esistono 4 divisibili per 25, 
cioe' divisibili per 5 due volte
Notiamo che 5^3 = 125 > 100.
Possiamo concludere che 100! termina con 20+4=24 zeri.
Ciao
Paolo Zavarise

>Con quanti zeri finisce 100!   ? (cento fattoriale).
A
A
R
G
H
H
O
C
A
P
P
E
L
L
A
T
O
.
.
.
La risposta esatta (calcolata con mathematica) e' 143... mmmm.... ora devo 
capire dove ho sbagliato...

 ha scritto nel messaggio
news:8FD7C6F7Apaolo...@192.106.1.6...

Paolo, penso che la tua prima risposta sia corretta. Il numero degli 0 è
strettamente legato al numero dei fattori 5, visto che di fattori 2 ce n'è
in abbondanza, quindi il conto dovrebbe proprio dare 24.
Il fatto che Mathematica ne indichi 143 è solo dovuto a motivi di
approssimazione. Per esempio, la "semplice" calcolatrice di Windows fornisce
il risultato:
9,3326215443944152681699238856267e+157
che (per quanto il risultato possa soffrire di errori di arrotondamento) sta
ad indicare che il valore ha 158 cifre e almeno le prime 32 sono diverse da
0, per cui gli zeri al massimo sarebbero 126.
Ciao
Giorgio

a me la TI 92 mi da tutte le cifre...e gli zeri infondo sono 24 .  la
risposta é corretta....il mathematica...può sbagliare...la mia cara TI92 no!
...(scherzo!=)
--
                                                                Giovanni


Il metodo dei 5 va bene e la risposta esatta e' 24.
Non so cosa abbia calcolato mathematica ma e' impossibile
che 100! sia divisibile per 10^143 (o 5^143).
Per verifica ho calcolato (cioe' ho fatto calcolare al
computer) il fattoriale di 100. Il risultato e'
93326215443944152681699238856266700490715968264381
62146859296389521759999322991560894146397615651828
62536979208272237582511852109168640000000000000000
00000000
Sono 158 cifre, con 24 zeri finali.
	Mauro

 wrote in message
8t4u5u$llcqa$1...@ID-57385.news.cis.dfn.de...

Mathematica può essere settato adeguatamente per questi calcoli...
MaxArt

Con quanti zeri finisce 100!   ? (cento fattoriale).
Sapevo che era facile.
Le calcolatrici (e la forza bruta) possono solo spostare il limite piu' avanti
e non eliminarlo:  se avessi chiesto 1000!  ?
Santo

avanti e non eliminarlo:  se avessi chiesto 1000!  ?
S
P
O
I
L
E
R
1000/(5^1)=200
1000/(5^2)=40
1000/(5^3)=8
1000/(5^4)=1...
.... se avessi chiesto 1000! ti avremmo risposto 249 zeri...
Ciao
Paolo Zavarise

 Paolo Zavarise
A questo punto, posso proporre un giochino apparso tempo fa sulla
rivista MC Microcomputer: qual'e' l'ultima cifra diversa da 0 con cui
termina 10000!
Bye by Massimo 8-]

 Bye by Massimo 8-]
Contando solo le ultime cifre :
1*2*3*4*5*6*7*8*9*10 = _*_*3*4*_*6*7*8*9*_ * 10^2
= 12 * 42 * 72 *10^2 = 2^3 *100 = 8 * 1000
Qundi basta calcolare 8^1000 (mod10)
8^1=8
8^2=64=4
8^3=32=2
8^4=16=6 ---
8^5=48=8
8^6=64=4
8^7=2
8^8=6  ---
e' diventato periodico di periodo 4, tutti i multipli di 4 valgono 6,
8^1000 compreso : la risposta e' 6.

Ooops! Ho sbagliato di brutto....

 termina 10000!
Ho trovato un metodo un po' complicato che pero' sembra
funzionare (almeno per il 10000 funziona).
Con un po' di pazienza si puo' appllicare anche a mano,
ma con un computer e' molto meglio.
Il fattoriale puo' essere scomposto in alcuni fattori:
  (prodotto dei numeri pari) * 
  (prodotto dei dispari divisibili per 5, cioe' 5,15,25,...) *
  (prodotto degli altri, cioe' quelli che terminano in 1,3,7,9)
quindi (il simbolo '/' indica sempre la divisione intera):
  N! = 2^(N/2) * (N/2)!   *   5^k * P5   *   PA
dove  k  e' il numero di fattori 5 presente nel prodotto dei
dispari div. per 5, e P5 e' quello che rimane dopo aver tolto i 5.
Si trova quindi:
  N! = 2^(N/2 - k)  *  10^k  *  P5  *  PA  *  (N/2)!
N/2 e' sempre maggiore di k (tranne che per 0! e 1! ma questi
possono essere trattati facilmente come casi speciali).
Il 10^k fornisce solo degli zeri e non ci interessa.
Gli altri fattori, escluso (N/2)!, non contengono 5, quindi
non contribiuscono agli zeri finali, ma determinano l'ultima
cifra diversa da zero.
Adesso "basta" trovare la cifra finale di 2^(N/2-k), P5, PA,
e l'ultima cifra diversa da zero di (N/2)!.
Per (N/2)! si puo' procedere ricorsivamente, fermandosi a 1!.
Esaminiamo gli altri fattori:
===========  2 ^ (N/2 - k)  ==========
2 ^ m  con m > 0 termina in:
  6  se  m mod 4 = 0
  2  se  m mod 4 = 1
  4  se  m mod 4 = 2
  8  se  m mod 4 = 3
Rimane da trovare k.
Il numero totale di 5 in N! e' uguale al numero di zeri finali
e si trova facilente con il medoto usato nel problema precedente.
A noi pero' interessano solo i 5 dei fattori dispari, quindi
dobbiamo eliminare quelli dei fattori divisibili per 10.
Il prodotto dei numeri div. per 10 e'  10^(N/10) * (N/10)!,
e contiene un numero di cinque pari a  N/10 + zeri(N/10).
Quindi  k = zeri(N) - N/10 - zeri(N/10).
Probabilmente esiste un metodo piu' veloce.
Adesso basta trovare
  (N/2 - zeri(N) + N/10 - zeri(N/10)) mod 4
e ricavare la cifra finale dalla tabella.
PA e' il prodotto dei numeri che finiscono in 1,3,7,9.
La cifra finale si trova abbastanza facilemnte:
 1   1
 3   3    (1*3)
 7   1    (1*3*7 = 21)
 9   9
11   9
13   7
17   9
19   1
e si ripete con un periodo pari a 20.
Quindi quando  N mod 20  vale 0,1,2,...,19 la cifra finale e'
rispettivamente 1,1,1,3,3,3,3,1,1,9,9,9,9,7,7,7,7,9,9,1
================  P5  ================
P5 e' il prodotto di quello che rimane ai numeri dispari
divisibili per 5 dopo ver tolto i 5.
Esempio:
     5  15  25  35  45   55   65  75      9975   9985   9995
P5 = 1 * 3 * 1 * 7 * 9 * 11 * 13 * 3 *...* 399 * 1997 * 1999
             ^                     ^         ^
Come si puo' notare, non e' la normale sequanza dei numeri
dispari ma contiene delle "anomalie" in corrispondenza dei
multipli di 25.
Si puo' vedere che le cifre finali sono:
  1,3,1,7,9,  1,3,3,7,9,  1,3,1,7,9, 1,3,7,7,9, ...
cioe' una sucessione "quasi periodica" di e periodo 5, dove cambia
solo la cifra centrale mentre le altre sono sempre 1,3, 7,9.
La cifra centrale vale 1,3,1,7,9,1,3,3,.... cioe' la stessa
sucessione.
Quindi (con indici che partono da 0):
  X(n) =  1,3,7,9   se  n mod 5 = 0,1,3,4
  X(n) =  X(n/5)    se  n mod 5 = 2
Per trovare il prodotto P5 si puo' usare un metodo brutale,
cioe' calcolare i primi (N+5)/10 termini della successione
e moltiplicarli modulo 10, oppure usare metodi piu' furbi.
Per esempio si puo' notare che 1*3*7*9 = 9 (mod 10), e che 
il prodotto di k gruppi da 5 e' uguale a 9^k * (prodotto
dei primi k/5 numeri).
Siccome i conti li ho fatti fare al computer ho usato il
primo metodo.
Risultato finale: 8
Verifica con forza bruta: 10000! = 284625968...8 000...000
per un totale di 35661 cifre, con 2499 zeri finali.
Il metodo si puo' ottimizzare da varie parti e probabilmente
esistono metodi migliori, pero' per ora e' l'unico che ho
trovato.
	Mauro

 funzionare (almeno per il 10000 funziona).
Forse il tuo metodo si puo' semplificare in questo modo(dovrebbe
funzionare per qualsiasi N):
Preferisco esporlo con un esempio, lasciando a chi se la sente il
compito di trasformarlo in formule o in programma.
Prendiamo per esempio N=9273
Scomponiamo N! in quattro fattori:
A) prodotto dei numeri multipli di 5
5*10*15*20*.....*9270
B) prodotto dei numeri che terminano in 2
2*12*22*.....*9272
C) prodotto dei numeri che terminano in 8
8*18*28*....*9268
D) prodotto di tutti gli altri
1*3*4*6*7*9*11*13.....*9273
possiamo scrivere
A = (5*1)*(5*2)*(5*3)*...*(5*1854)=
= 5^1854 * 1854!
B = (2*1)*(2*6)*(2*11)*(2*16)*...*(2*4636)=
= 2^928 * (1*6*11*16*...*4636)
C = (2*4)*(2*9)*(2*14)*(2*19)*...*(2*4814)
= 2^927 * (4*9*14*19*...4814)
confrontando le potenze di 5 in A e quelle di 2 in B e C, abbiamo
2 * 2^1854 * 5^1854 = 2*10^1854
e trascurando la potenza di 10, che genera soltanto zeri, rimane un
fattore 2
(notiamo che rimane il fattore 2 quando N termina in (2,3,4,8,9),
mentre se N termina in (0,1,5,6,7) le potenze di 2 e quelle di 5 si
equilibrano.
Per quanto riguarda gli altri fattori presenti in B,C,D, osserviamo che
Il prodotto (1*6*11*16*...) termina comunque con la cifra 6
Il prodotto (4*9*14*19*....) termina alternativamente in 4 o in 6:
sara' 4 quando, nell'ultimo termine in 8 considerato (nel nostro caso
9628) la cifra delle diecine e' pari, 6 se e' dispari.
Il prodotto (1*3*4*6....) termina ciclicamente in (6,8,2,2,4,6) se
l'ultimo fattore (nel nostro caso 9273) termina rispettivamente in
(1,3,4,6,7,9).
In conclusione, considerando, tra parentesi quadre, solo le cifre
terminali di ciascun fattore
9723! = [2] * [6] * [4] * [8] * 1854! =
= [4] * 1854!
Procediamo ricorsivamente per il fattoriale di 1854 e cosi' via, fino a
un numero sufficientemente piccolo per cui si possa calcolare il
fattoriale a mano.
Considerando che per ogni iterazione il numero di cui calcolare il
fattoriale si riduce all'incirca ad 1/5 del precedente, il numero di
iterazioni e' dato approssimativamente dal log(N) in base 5.
ciao
paolo
Sent via Deja.com 
http://www.deja.com/
Before you buy.

 > > termina 10000!   ?
L'aritmetica ci mostra che le ultime n cifre a destra di un prodotto
dipendono solo dalle n cifre a destra dei fattori:
       347 x
       321
-------------
       347
     6 94      
   104 1
-------------
   111 387  
47 x 21 = 987
Quindi se ad ogni prodotto buttiamo via gli zeri e teniamo solo 
n cifre a destra del prodotto, troviamo facilmente il risultato
richiesto.
P = 1                              'prodotto
For J = 2 To 10000
    P = P * J
    Do
        R = P Mod 10
        If R = 0 Then P = P / 10   'butto via gli zeri
    Loop While R = 0
    P = P Mod 100000               'tengo un po' di cifre a destra
Next J
Print P
Quindi:    10000!=   ..........8 x 10^tot
Ciao a tutti
Livio
-- 
Posted from 
pop09-acc.tin.it
 [212.216.176.72] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

termina 10000!
Poche spiegazioni... e pochi calcoli ;)
10000/5=2000
2000/5=400
400/5=80
80/5=16
16 non e' divisibile per 10, visto che e' piccolo lo possiamo analizzare in 
dettaglio
1..1 a
2..2 a
3..3 a
4..4 a
5..1 c
6..6 a
7..7 a
8..8 a
9..9 a
10..2 c 
11..1 b
12..2 b
13..3 b
14..4 b
15..3 c
16..6 b
Quindi, l'ultima cifra diversa da 0 con cui termina 10000! e' l'ultima 
cifra del prodotto
(2*3*6*7*8*9)^((2000+400+80+16)/2+1)*(3*4*6)*(2*3)
Ovvero il prodotto 18144^1249*432
Poiche' 18144 termina per 4 e 1249 e' dispari > 18144^1249 termina per 4
Un numero che termina per 4, moltiplicato un numero che termina per due, 
fornira' un numero che termina per 8.
Concludendo, l'ultima cifra diversa da 0 con cui termina 10000! e' 8
Ciao
Paolo Zavarise

 richiesto.
Pero' ci sono due problemi:
- bisogna fare N moltiplicazoni, mente con gli altri metodi
il numero di operazioni ha un andamento logaritmico (mi sembra
O((log N)^3) per il mio algoritmo ma non ho verificato).
- anche se non si tengono tutte le cifre, spesso e' necessario
lavorare con numeri piu' grandi di N.
Per esempio, se si vuole trovare l'ultima cifra di 10000000! (10^7),
ad un certo punto si deve moltiplicare per 9765625 (cioe 5^10) e
all'improvviso spuntano 10 zeri.
Quindi per un numero di 8 cifre bisogna tenerne 11.
Con numeri grandi la situazione peggiora: per (10^70)! servono
100 cifre.
	Mauro

 Procediamo ricorsivamente per il fattoriale...
E conclude con la complessita` log(N) in base 5.
Ok.
Si puo` migliorare ancora cosi` :
Divido quindi N nei suoi multipli di 5 e nei restanti,
es. facile : N=100
N = 5^20*(1*2*3*...*20) * (1*2*3*4 * 6*7*8*9 * ... *99)
se definisco (N) come il prodotto dei numeri da 1 a N
esclusi i multipli di 5 diventa, espandendo la ricorsione
100! = 5^20*20! * (100)
     = 5^20*[5^4*4! * (20)] * (100)
     = 5^20*[5^4*[(4)] *(20)] * (100)
     = 5^(24) * (4) * (20) * (100)
I numeri che saltano fuori sono N/(5^k) troncato all`intero.
Ora il trucco : visto che il risultato e` certamente pari,
data la sovrabbondanza dei fattori 5 sui fattori 2, si puo`
calcolare in modulo 5 (ci sono solo 0! e 1! in eccezione),
che ha delle proprieta` migliori del 10.
(x) = { 1,2,1,4,*4*,4,1,2,1,*1*}(mod5)
per x = 1 2 3 4  5  6 7 8 9  10
dopodiche` e` ciclico in modulo 10, ovvero (x)=(x mod 10)
e (0) si puo` dire che valga 1 :
100! = 5^24 * [ (4) * (0) * (0) (mod5)]
     = 5^24 * [ 4 * 1 * 1 (mod5) ]
     = 5^24 * [ 4 (mod5) ]
recupero quindi dalla parentesi quadra i fattori 2, ricordando
che il periodo moltiplicativo del 2 e` 4, 2^4=1 e 2^k=(2,4,3,1,2) :
100! = 10^24 * [ 4 * 2^(-24) (mod5) ]
     = 10^24 * [ 4 (mod5) ]
Il risultato e` 4. Ripetendo con 10000! viene 3, cioe` 8.

 (2*3*6*7*8*9)^((2000+400+80+16)/2+1)*(3*4*6)*(2*3)
     ^^^                         ^^^    ^^^ 
Ho capito che nei numeri segnati con `c` hai diviso per 5, che forse manca
un 4 ed un 2 poi buio pesto, oscurissimo quel `/2`... sono su candid camera ?