Page 39 - MATINF Nr.2

Determinarea ultimei cifre nenule pentru produse de numere naturale 39

Lema 2. Dac˘a n este un num˘ar natural nenul, atunci

n n n n
ï ò ï ò ï ò ï ò
a(n!) = + + + . . . + , unde k = [log n]
2
2 2 2 2 3 2 k
s , i
n n n n
ï ò ï ò ï ò ï ò
0
b(n!) = + + + . . . + 0 , unde k = [log n] .
5
5 5 2 5 3 5 k
Demonstrat¸ie. a(n!) reprezint˘a puterea lui 2 din descompunerea ˆın factori primi a produsului
î ó
n
1 · 2 · . . . · n. Printre numerele 1, 2, . . . , n avem exact numere divizibile cu 2, dintre care exact
2
n 2 n 3
î ó î ó
2 2 sunt divizibile s , i cu 2 , dintre care exact 2 3 sunt divizibile s , i cu 2 , s , .a.m.d., deci
n n n
ï ò ï ò ï ò
a(n!) = + + + . . . .
2 2 2 2 3
Cum 2 k+1 > n, deci printre numerele 1, 2, . . . , n nu exist˘a numere divizibile cu 2 k+1 , rezult˘a c˘a
î n ó
suma anterioar˘a se poate ˆıncheia cu termenul k . Analog se demonstreaz˘a s , i formula lui b(n!)
2
din enunt , .
Lema 3. Avem a(n!) = Θ(n) s , i b(n!) = Θ(n).

∗
Demonstrat¸ie. Fie n ∈ N s , i k = [log n]. Conform lemei anterioare,
2
n n n n
ï ò ï ò ï ò ï ò
a(n!) = + + + . . . + .
2 2 2 2 3 2 k
î ó î ó
k
k
Avem k ≤ log n < k + 1, deci 2 ≤ n < 2 k+1 . Deducem c˘a 2 k−1 ≤ n < 2 , 2 k−2 ≤ n 2 <
2
î n ó 2 2
1
0
2 k−1 ,. . . , 2 ≤ k < 2 , deci prin adunare obt , inem
2
k
k
2 − 1 ≤ a(n!) < 2(2 − 1).
Cum log n − 1 < k ≤ log n, rezult˘a c˘a
2 2
n − 2
< a(n!) < 2n − 2,
2
deci a(n!) = Θ(n).
Analog se demonstreaz˘a c˘a

n − 5 5n − 5
< b(n!) < ,
20 4

deci s , i b(n!) = Θ(n).

Lema 4. Avem a(0!) = b(0!) = a(1!) = b(1!) = 0 s , i a(n!) > b(n!) pentru orice n ≥ 2.

0
Demonstrat¸ie. Evident, a(1) = b(1) = 0. Pentru n ≥ 2, cu notat , iile din Lema 2, avem k ≥ k ,
n > n , n 2 ≥ n 2 , . . . , n n
î ó î ó î ó î ó î ó î ó
2 5 2 5 2 k 0 ≥ 5 k 0 , de unde prin adunare obt , inem c˘a a(n!) > b(n!).
Lema 5. Pentru orice n ∈ N, num˘arul de zerouri ˆın care se termin˘a num˘arul n! este egal cu
b(n!).