MySQL Web Server, Tomcat, Jsp, Struts Hosting Blog

3.2.2 ANSWERS TO EXERCISES 529 15. Algorithm M generates (Xn+k,Yn) in step Ml and outputs 2, = Xn+k–q, in step M3, for all sufficiently large n. Thus (.&) has a period of length X , where X is the least positive integer such that Xn+kwq,, = Xn+X/+k–qnfX, for all large n. Since X is a multiple of X1 and X2, it follows that X is a divisor of X. (These observations are due to Alan G. Waterman.) We also have n + k -qn E n + X + k -q,+~t (modulo Xl) for all large n, by the distinctness of the X s. The bound on (qn) implies that qn+xt = qn + c for all large n, where c z X (modulo Xl) and ICI < &X1. But c must be 0 since (qn) is bounded. Hence X E 0 (modulo Xl), and q,+x/ = qn for all large n; it follows that X is a multiple of X2 and X1, so X = X. Note: The answer to exercise 3.2.1.2-4 implies that when (Yn) is a linear congruen- tial sequence of maximum period modulo m = 2 , the period length XZ will be at most Zep2 when k is a power of 2. 16. There are several methods of proof. (1) Using the theory of finite fields. In the field with 2k elements let [ satisfy p=alp-l+...+ ak. Let f(bl tk- + + bk) = bk, where each b3 is either zero or one; this is a linear function. If word X in the generation algorithm is (blbz . . . bk)2 before (10) is executed, and if bltkml + . .. + bkt = En, then word X represents 7L+1 after (10) is executed. Hence the sequence is f([ ), f([ +l), f([ -t2), . . . ; and :(tnik) = f(( tk) = f(ul[ +k- + ... f akEn) = alf(( +k-l) + . . + akf(< ). (2) Using brute force, or elementary ingenuity. We are given a sequence Xnj, n 2 0, 1 5 j 5 k, satisfying x(,+1), = -&(,+I) + Gh, l 1, we have by induction &, = X(n+~)(J–l) -a,-l-G1 EC aX(n+l-,)(,-l) -a3–1 c azX(n–2)l l

528 ANSWERS TO EXERCISES 3.2.2 there must exist polynomials a(z) and b(z) such that pefl(u(z) + pa(z)) = f(z)b(z). Since f(0) = 1, this implies that b(z) is a multiple of pef (by Gauss s Lemma 4.6.1G); hence V(Z) E 0 (modulo f(z) and p), a contradiction. (b) If zx - 1 = f(z)u(z) $ p v(z), then G(z) = 4Mz -1) + ~ Wlf(z)(z~ -1); hence An+i E A, (modulo p ) for large n. Conversely, if (An) has the latter property then G(z) = u(z) + v(z)/(l -z ) + peH(z), f or some polynomials u(z) and V(Z), and some power series H(z), all with integer coefficients. This implies the identity 1-zx = u(z)f(z)(l -z )+~(z)f(z)+p~H(z)f(z)(l-zzX); and H(z)f(z)(l -zx) is a polynomial since the other terms of the equation are polynomials. (c) It suffices to prove that X(p ) # X(p + ) implies that X(p + ) = pX(pe) # X(p +*). Applying (a) and (b), we know that X(p +*) # pX(pe), and that X(pefl) is a divisor of pX(pe) but not of X(p ). Hence if X(p ) = pfq, where qmodp # 0, then X(p + ) must be p f+ d where d is a divisor of 4. But now Xn+rf+l E X, (modulo p ); hence p + d is a multiple of pfq, hence d = q. [Note: The hypothesis p > 2 is necessary; for example, let al = 4, us = -1, k = 2; then (An) = 1, 4, 15, 56, 209, 780, . . ; X(2) = 2, X(4) = 4, X(8) = 4.1 (d) g(z) = Xo + (XI -alXo)z + . . . +(x&-l -UlXk-2 -U2Xk-3 -. . . -uk-lXO)Zk–l. (e) The derivation in (b) can be generalized to the case G(z) = g(z)/f(z); then the assumption of period length X implies that g(z)(l -z ) E 0 (modulo f(z) and p ); we treated only the special case g(z) = 1 above. But both sides of this congruence can be multiplied by Hensel s b(z), and we obtain 1 - zx = 0 (modulo f(z) and p ). Note: A more elementary proof of the result in (c) can be given without using generating functions, using methods analogous to those in the answer to exercise 8: If Alfn. = A, + p B,, for n = r, r + 1,. . . , r + k -1 and some integers B,, then this same relation holds for dl n 2 r if we define &+k, &+k+r, . . . by the given recurrence relation. Since the resulting sequence of B s is some linear combination of shifts of the sequence of A s, we will have &+, E B, (modulo p ) for all large enough values of n. Now X(p +l) must be some multiple of X = X(pe); for all large enough n we have An+jx = An+p’(Bn+Bn+x +Bn+zx+. . .+B,+(j-1)~) E A,+jpeBn (modulo p ) forj=1,2,3 ,… . No k consecutive B s are multiples of p; hence X(p + ) = pX(pe) # X(pe+*) follows immediately when e 2 2. We still must prove that X(p +*) # pX(p ) when p is odd and e = 1; here we let Bx+, = B,, +pC,, and observe that C&+X E C, (modulo p) when n is large enough. Then A,+, E A, +p2(Bn + (g)C-) (modulo p ), and the proof is readily completed. For the history of this problem, see Morgan Ward, Trans. Amer. Math. Sot. 35 (1933), 600-628; see also D. W. Robinson, AMA4 73 (1966), 619-621. 12. The period length mod 2 can be at most 4; and the period length mod Zefl is at most twice the maximum length mod 2 , by the considerations of the previous exercise. So the maximum conceivable period length is 2ef1; this is achievable, for example, in the trivial case a = 0, b = c = 1. 13, 14. Clearly ,&+A = Z,, so X is certainly a divisor of X. Let the least common multiple of X and X1 be Xi, and define Xi similarly. X, + Y, = 2, ZE Zn+x; EE XI + yn+x;, so Xi is a multiple of X2. Similarly, Xi is a multiple of X1. This yields the desired result. (The result is best possible in the sense that sequences for which X = X0 can be constructed, as well as sequences for which X = X.)

3.2.2 ANSWERS TO EXERCISES 527 X, 3 cn + pY, (modulo p ), we must have Yn+l G n2c2r + ncs + Y, (modulo p); hence Y, G (:)2 c2r + (;)(c ~ + cs) (modulo p). Thus YP modp = 0, and the desired relation has been proved. Now we can prove that the sequence (Xtl) of integers defined in the hint satisfies the relation X n+pf = X, + tpf (modulo pf+ ), n 2 0, for some t with t mod p # 0, and for all f 2 1. This suffices to prove that the sequence (X, modp ) has period length p , for the length of the period is a divisor of pe but not a divisor of pe- . The above relation has already been established for f = 1, and for f > 1 it can be proved by induction in the following manner: Let X nfpf -xn + tpf + Znpffl (modulo pffz); then the quadratic law for generating the sequence, with d = pr, a = 1+ ps, yields z n+l -2rtnc + st + 2, (modulo p). It follows that Zn+P E Z, (modulo p); hence X n+kpf = X, + k(tpf + Z,pf+ ) (modulo pff2) for k = 1,2,3,. . ; setting k = p completes the proof. Notes: If f(z) is a polynomial of degree higher than 2 and Xn+l = f(Xn), the analysis is more complicated, although we can use the fact that f (m + pk) = f(m) + pk f (M) + p2 f (m)/2! + . . . to prove that many polynomial recurrences give the maximum period. For example, Coveyou has proved that the period is m = 2 if f(0) is odd, f’(j) 3 1, f”(j) -0, and f(j+ 1) = f(j)+ 1 (modulo 4) for j = 0,1,2,3. [Studies in Applied Math. 3 (1967), 70-111.1 9. Let X, = 4Y,+2; then the sequence Y, satisfies the quadratic recurrence Y,+l = (4Yi + 5Y, + 1) mod ae- . 10. Case 1: XO = 0, X1 = 1; hence X, = F,. We seek the smallest n for which F,, s 0 and F,+I G 1 (modulo ae). Since Fzn = Fn(Fn-l + Fn+l), Fzn+l = Ft + Fi+l, we find by induction on e that, for e > 1, F3.2e–1 = 0 and F3.2c-~+1 SE 2 + 1 (modulo 2 + ). This implies that the period is a divisor of 3 . Ze- but not a divisor of 3 + 2e-2, so it is either 3 . Ze- or 2e-1. But Fze-1 is always odd (since only Fan is even). Case 2: X0 = a, X1 = b. Then X,, = aF,-1 + bF,; we need to find the smallest positive n with a(F,+l -Fn) + bF, ZE a and aF, + bF,+l E b. This implies that (b2 -ab -a )F,, z 0, (b2 -ab - a2)(F n+l -1) E 0; and b2 -ab - a2 is odd (i.e., prime to m) so the condition is equivalent to F, z 0, F,+I G 1. Methods to determine the period of F, for any modulus appear in an article by D. D. Wall, AMM 67 (1960), 525-532. Further facts about the Fibonacci sequence mod 2 have been derived by B. Jansson [Random Number Generators (Stockholm: Almqvist & Wiksell, 1966), Section 3Cl]. 11. (a) We have zx = 1 + f(z)u(z) + p v(z) for some u(z), V(Z), where V(Z) $ 0 (modulo f(z) and p). By the binomial theorem zxp = 1 + pe+ w(z) + p + V(z)2(p -1)/2 plus further terms congruent to zero (modulo f(z) and pe+ ). Since pe > 2, we have zxP E I+$+ V(Z) (modulo f(z) and p + ). If peflv(z) = 0 (modulo f(z) and pef2),

526 ANSWERS TO EXERCISES 3.2.2 (b) The underlined numbers are V[j] after step B2. 0utput:initial 236570053…46(30…47)… V[O]: 0 000000544…1111…11… V[l]: 3 36~111111…0004…00… V[2]: 2 177733331…6222…72… V[3]: 5 555002222…3355…33… x: 4 761032547…3254…32… In this case the output is considerably better than the input; it enters a repeating cycle of length 40 after 46 steps: 236570 05314 72632 40110 37564 76025 12541 73625 03746 (30175 24061 52317 46203 74531 60425 16753 02647). The cycle can be found easily by applying the method of exercise 3.1-7 to the above array until a column is repeated. 4. The low-order byte of many random sequences (e.g., linear congruential sequences with m = word size) is much less random than the high-order byte. See Section 3.2.1.1. 5. The randomizing effect would be quite minimized, because V[j] would always contain a number in a certain range, essentially j/k 5 V[j]/m < (j + 1)/k. However, some similar approaches could be used: we could take Y, = XnPl, or we could choose j from X, by extracting some digits from about the middle instead of at the extreme left. None of these suggestions would produce a lengthening of the period analogous to the behavior of Algorithm B. 6. For example, if X,/m < $, then X,+1 = 2X,. 7. [W. Mantel, Nieuw Arehief voor Wiskunde (2) 1 (1897), 172-184.1 00.. .Ol 00.. .Ol 00.. .lO The subsequence of 00.. .lO X values: becomes: 10.. .oo 10.. .oo 00.. .oo CONTENTS (A) CONTENTS (A) 8. We may assume that Xs = 0 and m = p , as in the proof of Theorem 3.2.1.2A. First suppose that the sequence has period length pe; it follows that the period of the sequence mod pf has length p f, for 1 < f 5 e, otherwise some residues mod pf would never occur. Clearly, c is not a multiple of p, for otherwise each X, would be a multiple of p. If p 5 3, it is easy to establish the necessity of conditions (iii) and (iv) by trial and error, so we may assume that p 2 5. If d $ 0 (modulo p) then dz2 + aa: + c = d(z + a,) + cl (modulo p ) for some integers al and cl and for all integers x; this quadratic takes the same value at the points x and --z -2~1, so it cannot assume all values modulo pe. Hence d G 0 (modulo p); and if a $ 1, we would have dx2 $ ax + c E x (modulo p) for some z, contradicting the fact that the sequence mod p has period length p. To show the sufficiency of the conditions, we may assume by Theorem 3.2.1.2A and consideration of some trivial cases that m = pe where e > 2. If p = 2, we have Xntp = X, +pc (modulo p2), by trial; and if p = 3, we have either Xn+r G X, fpc (modulo p ), for all n, or Xn+r = X, -pc (modulo p ), for all n. For p 2 5, we can prove that Xn+r = X, + pc (modulo p ): Let d = pr, a = 1 f ps. Then if

3.2.2 ANSWERS TO EXERCISES 525 8. Since X, is always odd, Xn+2 = (234 + 3 . 218 f 9)X, mod 235 = (234 + 6X,+1 -9X,) mod 235. Given Y, and Yn+i, the possibilities for Yn+2 M (5 i- 6(Y,+l + ~1) - 9(Y, + a)) mod 10, with 0 2 ~1 < 1, 0 2 ~2 < 1, are limited and nonrandom. Note: If the multiplier suggested in exercise 3 were, say, 233 +218 +22 + 1, instead of 223 + 214 + 22 + 1, we would similarly find X n+:! -10X,+1 $25X, z constant (modulo 235). In general, we do not want a f 6 to be divisible by high powers of 2 when 6 is small, else we get second order impotency. See Section 3.3.4 for a more detailed discussion. The generator that appears in this exercise is discussed in an article by MacLaren and Marsaglia, JACM 12 (1965), 83-89. The deficiencies of such generators were first demonstrated by M. Greenberger, CACM 8 (1965), 177-179. Yet generators like this were still in widespread use more than ten years later (cf. the discussion of RANDU in Section 3.3.4). SECTION 3.2.2 1. The method is useful only with great caution. In the first place, aU, is likely to be so large that the addition of c/m that follows will lose almost all significance, and the mod 1 operation will nearly destroy any vestiges of significance that might remain. We conclude that double-precision floating point arithmetic is necessary. Even with double precision, one must be sure that no rounding, etc., occurs to affect the numbers of the sequence in any way, since that would destroy the theoretical grounds for the good behavior of the sequence. (But see exercise 23.) 2. Xn+i equals either X,-i +X, or X,-l + X, -m. If Xn+i < X, we must have X,+1 = X,.-l +X, -m; hence Xn+l < X,-l. 3. (a) The underlined numbers are V[f after step M3. Output: initial / 0 4 5 6 2 0 3(2 7 4 1 6 3 0 5) and repeats. V[O]: 0 jp77777741777777/7… V[l]: 3 333333255555552555… V[2]: 2 2222QCl333333033333… V[3]: 5 556~1111116~111111… x: 476103254761032547… Y: 016745230167452301… So the potency has been reduced to l! (See further comments in the answer to exercise 15.)

524 ANSWERS TO EXERCISES 3.2.1.2 16. (a) f(z) = (z -a)(~?-~ + (a + ci)~?-~ +. . . + (an- -j-. . . + ~-1)) + f(a). (b) The statement is clear when n = 0. If a is one root, f(s) = (z -a)q(z); therefore if a is any other root, 0 G f(d) E (a -u)q(a ), and since a -a is not a multiple of p, a must be a root of q(z). So if f(s) has more than n distinct roots, q(z) has more than n -1 distinct roots. (c) X(p) 2 p -1, since f(z) must have degree 2 p -1 in order to possess so many roots. But by Theorem 1.2.4F, X(p) 2 p-1. 17. By Lemma P, 115 f 1 (modulo 25) 115 $ 1 (modulo 125), etc.; so the order of 11 is 5+-l (modulo 5e), not the maximum value X(5e) = 4. gem . But by Lemma Q the total period length is the least common multiple of the period modulo 2 (namely 2 - ) and the period modulo 5 (namely 5e-1), and this is 2e-25e-1 = X(lOe). The period modulo 5e may be ge- or 2 . ge- or 4 . 5=-l, without affecting the length of period modulo 10e, since the least common multiple is taken. The values that are primitive modulo 5 are those congruent to 2, 3, 8, 12, 13, 17, 22, 23 modulo 25 (cf. exercise 12), namely 3, 13, 27, 37, 53, 67, 77, 83, 117, 123, 133, 147, 163, 173, 187, 197. 18. According to Theorem C, umod 8 must be 3 or 5. Knowing the period of a modulo 5 and modulo 25 allows us to apply Lemma P to determine admissible values of a mod 25. Period = 4. ge- : 2, 3, 8, 12, 13, 17, 22, 23; period = 2. 5e-1: 4, 9, 14, 19; period = 5e-1: 6, 11, 16, 21. Each of these 16 values yields one value of a, 0 5 a < 200, with a mod 8 = 3, and another value of a with a mod 8 = 5. 19. One example appears in Table 3.3.4-1, line 26. 20. (a) We have AY, +X0 G AY,+k + X0 (modulo m) iff Y, = Yn+k (modulo m ). (b)(i) Obvious. (ii) Theorem A. (iii) (a -l)/(u -1) = 0 (modulo 2e) iff un z 1 (modulo 2ef1); if a $ -1, the order of a modulo 2 + is twice its order modulo 2 . (iv) (a -l)/(u -1) z 0 (modulo p ) iff un E 1. 21. X,+, = X, + X, by Eq. 3.2.1-6; and s is a divisor of m, since s is a power of p when m is a power of p. Hence a given integer q is a multiple of m/s iff X,, = 0 iff q is a multiple of m/ gcd(X,, m). SECTION 3.2.1.3 1. c = 1 is always relatively prime to B5; and every prime dividing m = B5 is a divisor of B, so it divides b = B2 to at least the second power. 2. Only 3, so the generator is not recommended in spite of its long period. 3. The potency is 18 in both cases (see next exercise). 4. Since umod4 = 1, we must have umod8 = 1 or 5, so bmod8 = 0 or 4. If b is an odd multiple of 4, and if bl is a multiple of 8, clearly bS = 0. (modulo 2 ) implies that bi = 0 (modulo 2 ), so bl cannot have higher potency. 5. The potency is the smallest value of s such that fjS 2 e3 for all j. 6. The modulus must be divisible by 27 or by p4 (for odd prime p) in order to have a potency as high as 4. The only values are m = 227 + 1 and 10 -1. 7. a = (1 -b + b2 -. .) mod m, where the terms in b , bsfl, etc., are dropped (if s is the potency).

3.2.1.2 ANSWERS TO EXERCISES 523 6. (Cf. previous exercise.) a 3 1 (modulo 3.7 . 11 . 13.37) implies that the solutions are a = 1 f llllllk, for 0 5 k 5 8. 7. Using the notation of the proof of Lemma Q, p is the smallest value such that X P+x = X,; so it is the smallest value such that Y,+x = Yp and .Zcl+x = 2,. This shows that p = max(pi, . . . , pt). The highest achievable p is max(ei, . . . , et), but nobody really wants to achieve it. 8. We have a2 = 1 (modulo ; so a4 G 1 (modulo 16), us = 1 (modulo 32), etc. If a mod 4 = 3, then a-1 is twice an odd number; so (aze- -1)/2 = 0 (modulo 2 + /2), and this yields the desired result. 9. Substitute for X, in terms of Y, and simplify. If Xc mod 4 = 3, the formulas of the exercise do not apply; but they do apply to the sequence 2, = (-Xn) mod 2e, which has essentially the same behavior. 10. Only m = 1, 2, 4, pe, and 2pe, for odd primes p. In all other cases, the result of Theorem B is an improvement over Euler s theorem (exercise 1.2.4-28). 11. (a) Either z+l or z-l (not both) will be a multiple of 4, so ~71 = 92f, where q is odd and f is greater than 1. (b) In the given circumstances, f < e and so e 2 3. We have -& = 1 (modulo 2f) and fz $1 (modulo af+ ) and f > 1. Hence by applying Lemma P, we find that (f~) ~- - $ 1 (modulo 27, while z2e–f = (*z) -~ E 1 (modulo 27. So the order is a divisor of 2e- , but not a divisor of Zemf- . (c) 1 has order 1; 2e -1 has order 2; the maximum period when e 2 3 is therefore 2e-2, and for e 2 4 it is necessary to have f = 2, that is, z = 4 f 1 (modulo . 12. If k is a proper divisor of p -1 and if uk G 1 (modulo p), then by Lemma P we have ukpe- = 1 (modulo p ). Similarly, if up- = 1 (modulo p ), we find that u(P-l)P -* -1 (modulo p ). So in these cases a is not primitive. Conversely, if up- $ 1 (zodulo p ), Theorem 1.2.4F and Lemma P tell us that u(~- )~ -~ $ 1 (modulo p ), but u(~- )~~- G 1 (modulo p ). So the order is a divisor of (p -l)pe- but not of (p -l)pep2; it therefore has the form kpe- , where k divides p -1. But if a is primitive modulo p, the congruence a kpe- = uk = 1 (modulo p) implies that k=p-1. 13. Let X be the order of a modulo p. By Theorem 1.2.4F, X is a divisor of p -1. If X < p -1, then (p -1)/X has a prime factor, q. 14. Let 0 < k < p. If up- = 1 (modulo p2), then (a + kp)*- E up- + (p -1)X uP-2kp (modulo p2); and this is $ 1, since (p -l)uPp2k is not a multiple of p. By exercise 12, a + kp is primitive modulo pe. 15. (a) If Xi =pi …p;t,X2 =pf …pft, let ~1 =pyl…py,~,a =p: …pft, where g3 = e3 and hi = 0, if ej

522 ANSWERS TO EXERCISES 3.2.1.1 7. The prime factors of zk -1 appear in the factorization of zkr -1. If T is odd, the prime factors of zk f 1 appear in the factorization of zkr + 1. And zzk -1 equals (z -l)(zk + 1). 8. JOV *+1 (Ensure that overflow is off.) LDA X MULA STX TEMP ADD TEMP Add lower half to upper half. JNOV *+2 If 2 w, subtract w -1. INCA 1 (Overflow is impossible in this step.) 1 Note: Since addition on an e-bit ones -complement computer is mod (2e -l), it is possible to combine the techniques of exercises 4 and 8, producing (yz)mod(2 -1) by adding together the two e-bit halves of the product yz, for all ones complement numbers y and z regardless of sign. 9. The pairs (0, w -2), (1, w -1) are treated as equivalent in input and output: JOV *+I LDA X MULA aX=qw+r. SLC 5 rA + r, rX + q. STX TEMP ADD TEMP JNOV *+2 Get (r + q) mod (w -2). INCA 2 Overflow is impossible. ADD TEMP JNOV *+3 Get (r + 2q) mod (w -2). INCA 2 Overflow is possible. JOV *-I 1 SECTION 3.2.1.2 1. Period length m, by Theorem A. (Cf. exercise 3.) 2. Yes, these conditions imply the conditions in Theorem A, since the only prime divisor of 2e is 2, and any odd number is relatively prime to 2 . (In fact, the conditions of the exercise are necessary and sufficient.) 3. By Theorem A, we need a E 1 (modulo 4) and a = 1 (modulo 5). By Law D of Section 1.2.4, this is equivalent to a z 1 (modulo 20). 4. We know Xze-l E 0 (modulo 2e-1) by using Theorem A in the case m = 2+ . Also using Theorem A for m = 2 , we know that Xze-l $ 0 (modulo 27. It follows that X,.-l = 2e-1. More generally, we can use Eq. 3.2.1-6 to prove that the second half of the period is essentially like the first half, since XnfZe–l = (Xn+2e-1) mod 2e. (The quarters are similar too, see exercise 21.) 5. We need a = 1 (modulo p) for p = 3,11,43,281,86171. By Law D of Section 1.2.4, this is equivalent to a 3 1 (modulo 3. 11 . 43. 281 . 86171), so the only solution is the terrible multiplier a = 1.

3.2.1.1 ANSWERSTOEXERCISES 521 SECTION 3.2.1.1 1. Let c be a solution to the congruence UC E c (modulo m). (Thus, c = a c mod m, if a is the number in the answer to exercise 3.2.1-5.) Then we have LDA X ADD CPRIME MULA I Overflow is possible on this addition operation. (From results derived later in the chapter, it is probably best to save a unit of time, taking c = a and replacing the ADD instruction by INCA 1″. Then if X0 = 0, overflow will not occur until the end of the period, so it won t occur in practice.) 2.RANDM STJ 1F LDA XRAND MULA SLAX 5 ADD C (or, INCA c, if c is small) STA XRAND IH JNOV * JMP *-1 XRAND CON Xo A CON a C CON c I Note: Locations A and C should probably be named 2H and 3H to avoid conflict with other symbols, if this subroutine is to be used by other programmers. 3. See WMl at the end of Program 4.2.3D. 4. Define the operation z& 2 = y iff z E y (modulo 2e) and -2e- 5 y < 2e- The congruential sequence (Y,) defined by Y,=Xo&2 32 , Yn+l =(aY,+c)m&d232 is easy to compute on 370-style machines, since the lower half of the product of y and z is (yz) mod 232 for all two s complement numbers y and z, and since addition ignoring overflow also delivers its result &232. This sequence has all the random- ness properties of the standard linear congruential sequence (X,), since Y, G X, (modulo 232). Indeed, the two s complement representation of Y, is identical to the binary representation of X,, for all n. [G. Marsaglia and T. A. Bray first pointed this out in CACM 11 (1968), 757-759.1 5. (a) Subtraction: LDA X; SUB Y; JANN *+2; ADD M. (b) Addition: LDA X; SUB M; ADD Y; JANN *+2; ADD M. (Note that if m is more than half the word size, the instruction SUB M must precede the instruction ADD Y .) 6. The sequences are not essentially different, since adding the constant (m -c) has the same effect as subtracting the constant c. The operation must be combined with multiplication, so a subtractive process has little merit over the additive one (at least in MIX s case), except when it is necessary to avoid affecting the overflow toggle.

520 ANSWERS TO EXERCISES 3.1 The desired average value can now be computed; it is (cf. exercise 12) E,,, = ;(HI + 2H$$ + 3H3 - +f~~+…. =1+j m This latter formula was obtained by quite different means by Martin D. Kruskal, AMM 61 (1954), 392-397. Using the integral representation he proved the asymptotic relation lim,,, (Em -$ lnm) = i(r + ln2). For further results and references, see John Riordan, Annals Math. Stat. 33 (1962), 178-185. 15. The probability that f(s) # z for all x is (m-l) /m, which is approximately l/e. The existence of a self-repeating value in an algorithm like Algorithm K is therefore not colossal at all-it occurs with probability 1 - l/e M .63212. The only colossal thing was that the author happened to hit such a value when X0 was chosen at random (see exercise 11). 16. The sequence will repeat when a pair of successive elements occurs for the second time. The maximum period is m2. (Cf. next exercise.) 17. After selecting Xc,. . . , Xk-1 arbitrarily, let Xn+l = f(Xn, , Xn-kfr), where 0 0. 2. Let X, be the first repeated value in the sequence. If X, were equal to Xk for some k where 0 < k < r, we could prove that X,-i = X&r, since X, uniquely determines X,-i when a is prime to m. Hence Ic = 0. 3. If d is the greatest common divisor of a and m, the quantity ax,, can take on at most m/d values. The situation can be even worse; e.g., if m = 2e and if a is even, Eq. (6) shows that the sequence is eventually constant. 4. Induction on k. 5. If a is relatively prime to m, there is a number a for which aa = 1 (modulo m). Then X,-r = (a/X% -a c) mod m, and in general, xn-k = ((a )kXn -c(a + . . . + (a )k)) mod m = (a )kXn -c(a cT:r ) modm when k > 0, n-k 2 0. If a is not relatively prime to m, it is not possible to determine XnP1 when X, is given; multiples of m/gcd(a,m) may be added to X,-i without changing the value of X,. (See also exercise 3.2.1.3-7.)