Duminică, 28 nov 2010 02:50
[#]
wmutex
Ok, metoda "cu pixul pe hartie" de data asta (si acum scot limba la
radufly, in gluma, desigur :D)
Numarul de zerouri din n! este egal cu exponentul lui 5 din descompunerea in factori a lui n! (fiindca 2 apare de mult mai multe ori decat 5 in factorizare)
5^9 | n!
Urmatoarele numere au "contributii" de factori 5, deci contribuie cu zerouri in "coada" factorialului:
5 (+1 la exponent -- 1 zero in "coada" factorialului)
10 (+1 la exponent -- 2 de zero in "coada" factorialului)
15 (+1 la exponent -- 3 de zero in "coada" factorialului)
20 (+1 la exponent -- 4 de zero in "coada" factorialului)
25 (+2 la exponent -- 6 de zero in "coada" factorialului)
30 (+1 la exponent -- 7 de zero in "coada" factorialului)
35 (+1 la exponent -- 8 de zero in "coada" factorialului)
40 (+1 la exponent -- 9 de zero in "coada" factorialului)
45 (+1 la exponent -- 10 de zero in "coada" factorialului)
Deci n este cel putin 40, dar strict mai mic decat 45:
n \apartine {40, 41, 42, 43, 44}
Cel mai comod sunt de testat numerele prime din setul de mai sus (si anume 41 si 43) fiindca astfel se poate afla daca n este mai mare sau mai mic decat ele: fiind prime nu exista pericolul de-a fi "compuse" din factori mai mici.
Tot cu "pixul pe hartie" (à propos, "calc" din Windows nu lucreaza cu numere atat de mari :D) se observa ca:
1405006117752879898543142606244511569936384000000000 / 41 =
34268441896411704842515673323036867559424000000000 (rest 0)
pe cand
1405006117752879898543142606244511569936384000000000 / 41 =
32674560877973951128910293168477013254334511627906 (rest 42)
deci n este maxim 42 si minim 41. Pe aceeasi idee ca la puterile lui 5 se observa (tot "cu pixul pe hartie" :D) ca
7^6 = 117649
1405006117752879898543142606244511569936384000000000 / 117649 =
11942354952042770431904585727413846016000000000 (rest 0)
deci exista cel putin 6 factori de 7 in numarul respectiv, deci n=42 (dupa cum spunea si
radufly).
Problema zilei
Top 10 cele mai văzute probleme