598 ANSWERS TO EXERCISES 4.5.2 26. By induction, (Com web hosting)
598 ANSWERS TO EXERCISES 4.5.2 26. By induction, the length is m f [n/2] w h en m 2 n, except that when m = n = 1 there is no path to (0,O). 27. Let a, = (2n -(-l)n)/3; then a~, al, ~2, . . . = 0, 1, 1, 3, 5, 11, 21, . . . (This sequence of numbers has an interesting pattern of zeros and ones in its binary representation. Note that a, = a,-1 + 2an-2, and a, + a,+1 = 2 .) For m > n, let u = 2m+1 -an+2, v = am+2. For m = n > 0, let u = an+2 and v = 2u,+l, or u = 2u,+l and v = an+2 (depending on which is larger). Another example for the case m = n > 0 is u = 2n+ -1, 2, = Zn+ -2; this choice takes more shifts, and gives C = n + 1, D = 2n, E = 1. 28. This is a problem where it appears to be necessary to prove more than was asked just to prove what was asked. Let us prove the following: If u and v are positive integers, Algorithm B does 5 1 + Llg max(u, v)J subtraction steps; and if equality holds, then lldu + v)l > lk m&u, 41. For convenience, let us assume that u 2 v; let m = Llgu], n = LlgvJ; and let us use the lattice-point terminology, saying that we are at point (m, n). The proof is by induction on m + n. Case 1, m = 72. Clearly, [lg(u + v)J > LlguJ in this case. If u = v the result is trivial; otherwise the next subtraction-shift cycle takes us to a point (m -k, m). By induction, at most m + 1 further subtraction steps will be required; but if m + 1 more are needed, we have [lg((u -v)2- + v)J > llg v J, w h ere r 2 1 is the number of right shifts that were made. This is impossible, since (u -v)2- + v < (u -v) + v = u. So at most m further steps are needed. Case 2, m > n. The next subtraction step takes us to (m -k, n), and at most 1 + max(m -k, n) 2 m further steps will be required. Now if m further steps are required, then u has been replaced by u = (u -v)2- for some r 2 1. By induction, [lg(u + v)J 2 m; hence LMU + VII = llg 2((U -v)/ J + v)J 2 [lg 2(u + v)] 2 m + 1 > llg uJ. 29. Subtract the kth column from the 2&h, 3lcth, 4kth, etc., for k = 1, 2, 3, . . . . The result is a triangular matrix with xk on the diagonal in column k, where m = &,m Ed. It follows that xm = p(m), so the determinant is (p(l)p(2). . . cp(n). [In general, Smith s determinant, in which the (i, j) element is f(gcd(i, j)) for an arbitrary function f, is equal to nlcrncn Cd,m p(m/d)f(d), by the same argument. See L. E. Dickson, History of the Theory of Numbers 1 (New York: Chelsea, 1952), 122-123.1 30. To determine A and r such that u = Av + r, 0 5 r < v, using ordinary long division, takes 0((1 + logA)(log u)) units of time. If the quotients during the algorithm are Al, AZ, . . . , A,, then AlAz . . . A, 5 u, so log A1 + . . . + logA, 5 logu. Also m = O(logu). 31. In general, since (uU -1) mod (a -1) = uUmodv -1 (cf. Eq. 4.3.2-19), we find that gcd(u -1, un -1) = ugcd(m,n) -1 for all positive integers a. 32. Yes, to O(n(logn)2(loglogn)), even if we also need to compute the sequence of partial quotients that would be computed by Euclid s algorithm; see A. Schanhage, Acta Informatica 1 (19 71), 139-144. [But Algorithm L is better in practice unless n is extremely large.]