Numitu

In 10.

radubl

10 intradevar

Andrei023

In 12. Cum 10=5*2, iar cifre de 2 sunt din plin in 50!, vrem sa aflam cate cifre de 5 avem.
5*(1+2+...+10) -> 10 cifre de 5
25*(1+2) -> 2 cifre de 5 in plus

A fost propusa in trecut o problema asemanatoare, dar cu un numar mult mai mare in fata factorialului. :-)

wmutex

Cifrele de zero de la sfarsitul unui numar -- in baza zece -- provin din factorii (2^i)x(5^j) din descompunerea numarului, iar numarul zerourilor este min(i, j).


Numerele care contribuie cu factori 2 la numarul 50! sunt:

2, 4, 6, 8, 10,
12, 14, 16, 18, 20,
22, 24, 26, 28, 30,
32, 34, 36, 38, 40,
42, 44, 46, 48, 50

adica sunt:

1 + 2 + 1 + 3 + 1 +
2 + 1 + 4 + 1 + 2 +
1 + 3 + 1 + 2 + 1 +
5 + 1 + 2 + 1 + 3 +
1 + 2 + 1 + 4 + 1 = 47 factori 2 in descompunerea lui 50!


Numerele care contribuie cu factori 5 la numarul 50! sunt:

5, 10, 15, 20, 25,
30, 35, 40, 45, 50

adica sunt:

1 + 1 + 1 + 1 + 2 +
1 + 1 + 1 + 1 + 2 = 12 factori 5 in descompunerea lui 50!


Deci:

50! = (2^47) x (5^12) x ...

si numarul de zerouri ale numarului 50! in baza zece este:

min(47, 12) = 12 zerouri.

wmutex

(Comentariu offtopic)

Am observat cateva probleme nesolutionate (foarte interesante, de altfel) lasate "orfane" de propunatorii lor, cu mentiunea "solutia mai pe seara" neonorata. :D De aici incolo vorbesc in nume propriu: nu ma plang deloc de o provocare mai in forta, dar, dupa senzatia nasoala a esecului rezolvarii,  imi ramane in continuare curiozitatea. Daca s-ar putea posta solutiile, ori specificarea ca problema e una deschisa, eu as fi foarte bucuros. Mai ales la problema de joi, 7 iulie 2011:-)

oneel

50,00000... =>o infinitate de zerouri fara valoare.:))

wmutex

Propun (rezolvitorilor cat si autorului) sa demonstreze (sau sa infirme) urmatoarea formula generala pentru numarul de zerouri finale -- in baza zece -- a lui n!:

                         Nz(n!) = sum{i=1..[log5(n)]} [n/(5^i)]

unde log5(x) este logaritmul in baza 5 din x, iar [x] este partea intreaga a lui x.

wmutex

Mai intai, o sa prescurtez "descompunere in factori primi" prin "d.f.p.", fiindca apare deseori mai jos si mi-e lene sa scriu, si o sa demonstrez urmatoarea lema (partea cea mai consistenta din demonstratie):

        Numarul de factori p, unde p>1 este un numar prim, care apar in d.f.p. a lui n!, este:

        Nf(p, n) = sum{i=1..∞} [n/(p^i)]

        sau, dupa "decuparea" termenilor nuli:

        Nf(p, n) = sum{i=1..[logp(n)]} [n/(p^i)]

        unde logp(x) inseamna logaritmul in baza p al lui x, iar [x] semnifica partea intreaga a lui x.

Demonstratie: dat fiind ca p este prim, numarul de "aparitii" in d.f.p. a lui n! se datoreaza exclusiv aparitiei lui p in d.f.p. ale lui 1, 2, 3, ..., n, si nu eventualelor "compuneri" din divizori disparati ai lui 1, 2, 3, ..., n.

Asadar:

- un numar din p numere consecutive se imparte la p. Ceea ce inseamna ca, din cei n factori consecutivi ai lui n!, [n/p] contribuie cu cate un factor p;

- un numar din p^2 numere consecutive se imparte, comparativ cu precedentele, inca o data la p. Ceea ce inseamna ca, din cei n factori consecutivi ai lui n!, [n/(p^2)] contribuie fiecare cu inca un factor p;

...

- un numar din p^i numere consecutive se imparte, comparativ cu precedentele, inca o data la p. Ceea ce inseamna ca, din cei n factori consecutivi ai lui n!, [n/(p^i)] contribuie fiecare cu inca un factor p;

...

Sumand, numarul de factori p din d.f.p. a lui n! este

Nf(p, n) = [n/p] + [n/(p^2)] + ... + [n/(p^i)] = sum{i=1..∞} [n/(p^i)] c.c.t.d.

wmutex

(continuare)

Desigur, dat fiind ca n este finit, exista un "prag" in seria de mai sus: un numar intreg k astfel incat

p^k ≤ n < p^(k+1)   =>
k ≤ logp(n) < k+1   =>
k = [logp(n)]

Evident ca, pentru orice i>k, [n/(p^i)] = 0 (partea intreaga a unei fractii subunitare este zero), ceea ce inseamna ca termenii de la k+1 "in sus" din serie sunt toti nuli, deci nu contribuie cu nimic la valoarea seriei. Rezulta deci ca:

Nf(p, n) = sum{i=1..[logp(n)]} [n/(p^i)] c.c.t.d.

wmutex

(continuare)

Revenind la problema originala, zerourile finale din reprezentarea zecimala a lui n! sunt datorate factorilor 2 si 5 din d.f.p. a lui n!:

n! = (2^Nf(2,n)) x (5^Nf(5,n)) x ...

numarul de zerouri finale fiind dat de cel mai mic exponent:

Nz(n!) = min(Nf(2,n), Nf(5,n))

Utilizand lema de mai sus, este evident ca, pentru orice i>0:

5^i > 2^i   =>
n/(5^i) < n/(2^i)   =>
[n/(5^i)] ≤ [n/(2^i)]   =>
sum{i=1..∞} [n/(5^i)] ≤ sum{i=1..∞} [n/(2^i)]   =>
Nf(5,n) ≤ Nf(2,n)

deci:

Nz(n!) = Nf(5,n)

Utilizand formula "decupata" rezulta deci ca:

Nz(n!) = sum{i=1..[log5(n)]} [n/(5^i)] c.c.t.d.