64 FUNCTIONS AND ALGORITHMS [CHAP. 3
3.16. Find: (a)25(mod7);(b)25(mod5);(c)− 35 (mod 11);(d)− 3 (mod 8).
Whenkis positive, simply dividekby the modulusMto obtain the remainderr. Thenr=k(modM).Ifkis
negative, divide|k|byMto obtain the remainderr′. Thenk(modM)=M−r′(whenr′=0). Thus:(a)25(mod 7)=4(c)− 35 (mod 11)= 11 − 2 = 9
(b)25(mod 5)=0(d)− 3 (mod 8)= 8 − 3 = 53.17. Evaluate moduloM=15: (a)9+13; (b)7+11; (c)4−9; (d)2−10.
Usea±M=a(modM):(a)9+ 13 = 22 = 22 − 15 =7(c)4− 9 =− 5 =− 5 + 15 = 10
(b)7+ 11 = 18 = 18 − 15 =3(d)2− 10 =− 8 =− 8 + 15 = 73.18. Simplify: (a)n!
(n− 1 )!;(b)(n+ 2 )!
n!.(a)
n!
(n− 1 )!
=
n(n− 1 )(n− 2 )··· 3 · 2 · 1
(n− 1 )(n− 2 )··· 3 · 2 · 1
=nor, simply,
n!
(n− 1 )!
=
n(n− 1 )!
(n− 1 )!
=n(b)
(n+ 2 )!
n!
=
(n+ 2 )(n+ 1 )n!
n!
=(n+ 2 )(n− 1 )=n^2 + 3 n+ 23.19. Evaluate: (a) log 2 8; (b) log 2 64; (c) log 10 100; (d) log 100 .001.(a) log 28 =3 since 2^3 =8(c) log 10100 =2 since 10^2 = 100
(b) log 264 =6 since 2^6 = 64 (d) log 100. 001 =−3 since 10−^3 = 0. 001RECURSIVE FUNCTIONS
3.20. Letaandbbe positive integers, and supposeQis defined recursively as follows:Q(a, b)={
0ifa<b
Q(a−b, b)+1ifb≤a(a) Find: (i)Q( 2 , 5 ); (ii)Q( 12 , 5 ).
(b) What does this functionQdo? FindQ( 5861 , 7 ).
(a) (i)Q( 2 , 5 )=0 since 2<5.
(ii)Q( 12 , 5 )=Q( 7 , 5 )+ 1
=[Q( 2 , 5 )+ 1 ]+ 1 =Q( 2 , 5 )+ 2
= 0 + 2 = 2
(b) Each timebis subtracted froma, the value ofQis increased by 1. HenceQ(a, b)finds the quotient whenais
divided byb. ThusQ( 5861 , 7 )=837.3.21. Use the definition of the Ackermann function to findA( 1 , 3 ).
Figure 3-10 shows the 15 steps that are used to evaluateA( 1 , 3 ).
The forward indention indicates that we are postponing an evaluation and are recalling the definition, and the backward
indention indicates that we are backtracking. Observe that (a) of the definition is used in Steps 5, 8, 11 and 14; (b)in
Step 4; and (c) in Steps 1, 2, and 3. In the other steps we are backtracking with substitutions.