Page 43 - MATINF Nr.2

Determinarea ultimei cifre nenule pentru produse de numere naturale 43

Conform rezultatelor de mai sus obt , inem urm˘atorul algoritm pentru determinarea lui r(n!).

s 0 ← 6; s 1 ← 6; s 2 ← 2; s 3 ← 6; s 4 ← 4;
s 5 ← 4; s 6 ← 4; s 7 ← 8; s 8 ← 4; s 9 ← 6;
t 0 ← 6; t 1 ← 8; t 2 ← 4; t 3 ← 2;
UCNF(n) : // calculeaz˘ a r(n!), recursiv
if n ≤ 1 then
return 1;
else
p ← [n/5]; i ← n MOD 10; j ← p MOD 4;
return (s i · t j · UCNF(p)) MOD 10;

Propozit , ia 7. Algoritmul UCNF are complexitatea Θ(ln n).

Demonstrat¸ie. Fie T(n) num˘arul de instruct , iuni executate de algoritm. Avem T(0) = T(1) = 1
n
Äî óä
s , i T(n) = T + 5 pentru n ≥ 2. Fie n ≥ 2 s , i k = [log n], deci k ≤ log n < k + 1 s , i astfel
5 5 5
k
avem 5 ≤ n < 5 k+1 .
k
n
n
ó
Cazul 1. Dac˘a 5 < n < 5 k+1 , atunci 1 < n k < 5, k+1 < 1, î k+1 = 0 deci adunˆand
5 5 5
egalit˘at , ile
n n n n n
Åï òã Åï òã Åï òã Åï òã Åï òã
T(n) = T + 5, T = T + 5, . . . , T = T + 5
5 5 5 2 5 k 5 k+1
obt , inem T(n) = T(0) + 5(k + 1), adic˘a T(n) = 5 [log n] + 6.
5
k
n
Cazul 2. Dac˘a n = 5 , atunci k+1 = 1 s , i analog cazului 1 obt , inem c˘a T(n) = T(1) + 5k =
5
5 [log n] + 1.
5
Observat ,ia 10. O variant˘a iterativ˘a a algoritmului UCNF, datorat˘a lui Gregory P. Dresden s , i
bazat˘a pe reprezentarea num˘arului n ˆın baza 5, precum s , i alte rezultate privind r(n!), pot fi
g˘asite ˆın [4]. Ment , ion˘am c˘a Dresden a demonstrat s , i faptul c˘a num˘arul
∗
C = 0,d 1 d 2 . . . d n . . . , unde d n = r(n!), ∀n ∈ N

este s , i irat , ional (deci s , irul numerelor r(n!) nu este periodic), s , i transcendent [2, 3].

Bibliografie

[1] C. B˘alc˘au, Optimalitatea algoritmului de c˘autare binar˘a, MATINF 1 (2018), nr. 1, 39–51.

n
[2] G. Dresden, Two Irrational Numbers From the Last Nonzero Digits of n! and n , Math.
Mag. 74 (2001), no. 4, 316–320.

n
[3] G. Dresden, Three Transcendental Numbers From the Last Non-Zero Digits of n , F n and
n!, Math. Mag. 81 (2008), no. 2, 96–105.

[4] The On-Line Encyclopedia of Integer Sequences, https://oeis.org/A008904