Page 40 - MATINF Nr.2

40 S.C. Andronescu, C. B˘alc˘au, D. Constantin, D.A. Popescu

Demonstrat¸ie. Conform lemei anterioare, a(n!) ≥ b(n!), deci conform (1) avem n! = 10 b(n!) ·
2 a(n!)−b(n!) · (M10 + c(n!)), de unde rezult˘a afirmat , ia din enunt , .

Observat ,ia 5. Algoritmul pentru determinarea lui r(n!) bazat pe calculul lui n! are, conform
Observat , iei 1 s , i Lemelor 5 s , i 3, complexitatea Θ(n), dar este practic inoperabil pentru valori
mari ale lui n din cauza m˘arimii num˘arului n!.
Cum n! = 1 · 2 · . . . · n = m 1 · m 2 · . . . · m n cu m k = k pentru orice k = 1, n, ˆınlocuind ˆın
algoritmul UCNP instruct , iunea p ← m k cu p ← k obt , inem un algoritm pentru determinarea
lui r(n!) care evit˘a calculul lui n! s , i, conform Propozit , iilor 5 s , i 4 s , i Lemei 3, are de asemenea
complexitatea Θ(n).
3
2
Exemplul 6. r(11!) = r(1 · 2 · 3 · . . . · 11) = r(1 · 2 · 3 · 2 · 5 · 2 · 3 · 7 · 2 · 9 · 2 · 5 · 11) =
2
8
Ä
ä
r (2 · 5 · 3 · 3 · 7 · 9 · 1) = u 6 · 2 (8−2) MOD 4 · 3 · 3 · 7 · 9 = 8.
Totus , i, acest procedeu este practic imposibil de aplicat pentru valori mari ale lui n, s˘a zicem,
1918!, dac˘a nu se utilizeaz˘a echipament electronic de calcul.
ˆ
In continuare vom prezenta un algoritm mai eficient decˆat algoritmul descris ˆın observat , ia
anterioar˘a, s , i anume un algoritm subliniar pentru determinarea lui r(n!). Avem nevoie de alte
cˆateva rezultate.

Observat ,ia 6. Dac˘a m este un num˘ar natural nedivizibil cu 10, atunci u(m) 6= 0, deci r(m) =
u(m).
Observat ,ia 7. Fie m 1 , m 2 , . . . , m n numere naturale nenule astfel ˆıncˆat r(m i ) 6= 5 pentru orice
i = 1, n. Atunci u (r(m 1 ) · r(m 2 ) · . . . · r(m n )) 6= 0 s , i conform Observat , iei 4 avem r(m 1 · m 2 ·
. . . · m n ) = u (r(m 1 ) · r(m 2 ) · . . . · r(m n )) .

Lema 6. Fie n un num˘ar natural, n ≥ 2. Atunci r(n!) ∈ {2, 4, 6, 8}.

Demonstrat¸ie. Conform Lemei 4, a(n!) > b(n!), deci conform (1) avem

n! = 10 b(n!) · 2 a(n!)−b(n!) · (M10 + c(n!)) ,

de unde rezult˘a c˘a
Ä ä
r(n!) = r 2 a(n!)−b(n!) · (M10 + c(n!)) .
Dar
Ä a(n!)−b(n!) ä Ä a(n!)−b(n!) ä
r 2 = u 2 ∈ {2, 4, 6, 8},
r (M10 + c(n!)) = u (M10 + c(n!)) = c(n!) ∈ {1, 3, 7, 9},
Ä Ä ä ä
deci, folosind s , i Observat , ia 7, r(n!) = u r 2 a(n!)−b(n!) · c(n!) ∈ {2, 4, 6, 8}.

Lema 7. Fie m s , i k dou˘a numere naturale astfel ˆıncˆat m este divizibil cu 2 k+1 . Atunci
Ä k ä Ä k MOD 4 ä Ä 4−(k MOD 4) ä
u m : 2 = u m : 2 = u m · 2 .

∗
Demonstrat¸ie. Din ipotez˘a rezult˘a c˘a m = 2 k+p · y, cu p ∈ N s , i y impar. Avem

Ä k ä p p
u m : 2 = u (2 · y) = u (u(2 ) · u(y)) ,
Ä k MOD 4 ä Ä p k−(k MOD 4) ä Ä p k−(k MOD 4) ä
u m : 2 = u 2 · 2 · y = u u(2 ) · u(2 ) · u(y)
p
p
p
= u (u(2 ) · 6 · u(y)) = u (u(2 · 6) · u(y)) = u (u(2 ) · u(y))