MySQL Web Server, Tomcat, Jsp, Struts Hosting Blog

4.5.3 ANSWERS TO EXERCISES 607 [The sequence of labels on successive levels of this tree was first studied by M. A. Stern, J. fiir die reine und Angew. Math. 55 (1858), 193-220, although the relation to binary trees is not explicit in his paper. Peirce independently communicated this construction in a letter dated July 17, 1903, but he never published it; and during the next few years he occasionally amused himself by making rather cryptic remarks about it without revealing the underlying mechanism. See C. S. Peirce, The New Elements of Mathematics 3 (The Hague: Mouton, 1976), 781-784, 826-829; also 1, 207-211; and his Collected Papers 4 (1933), 276-280. See also D. H. Lehmer, AM&4 36 (1929), 59-67.1 41. In fact, the regular continued fractions for numbers of the general form (-l)e ;+l,+$g 123 +… have an interesting pattern, based on the continuant identity Qm+n+1 (Xl,…, G-l,% -l,l,ym -l,ym-1,…,y1)= xnQn–1(x1,. . . , xn-l)Qm(~m, . , ~1) m+n(~1,~~~,2~-l,0,–Ym,-ym-l,~~~,-yl). + (–llmQ This identity is most interesting when ym = ~~-1, ympl = x%-z, etc., since Qn+l(a,. . , Zk,O, zk+l,. . . , Zn) = Qn–1(zl,. , zk-1, zk + Zk+l, zk+2,. . . , Zn). In particular we find that if p,/q, = QnyI(x2,. . . , zn)/Qn(xl,. . , zn) = /x1,. . . , xn/, then p,/q, + (-l) /qir = /XI,. . . , zn,r -l,l, xn -1, z~-~, . . . ,x1/. By changing /Xl,…,Xn/ to /Xl,…, ~~-1, xn -1, l/, we can control the sign (-l)R as desired. For example, the partial sums of the first series have the following continued fractions of even length: 11, I/; /I, l,l,l,O, l/ = /I, l,l, 2/; /l, 1,1,2,1,1,1,1,1, l/; /Ll,l, 2,l,LL1,l,l,L 1,&l, 1, 1, 1, 1,&l, 1, l/ = IL 1, 1,&l, 1, l,l, 1, l,l, 2,1,1,1, 1,2,1,1, I/; and from this point on the sequence settles down and obeys a simple reflecting pattern. We find that the nth partial quotient a, can be computed rapidly as follows, if n -1 = 20q + r where 0 5 r < 20: 1, if r = 0,2,4,5,6,7,9,10,12,13,14,15,17 or 19; 2, if r = 3 or 16; a, = 1 + (q + r) mod 2, if r = 8 or 11; 2 -4, ifr=l; 1-t ds+l, if r = 18. Here d, is the dragon sequence defined by the rules do = 1, dzn = d,, d4n+l = 0, dJn+s = 1; the dragon curve discussed in exercise 4.1-18 turns right at its nth step iff d, = 1. Liouville snumberswith1~3areequalto/I-l,2+1,I2-l,1,1,I-l,1 2-l, 1, 1 -2, 1, 1, 12 - 1, 1 + 1, 1 - 1, 172 - 1, /. The nth partial quotient a, depends on the dragon sequence on mmod4 as follows: If nmod4 = 1 it is 1 - 2 + d,-1 + (ln/2j mod 4) an d f 1 nmod4=2itis1+2-ddn+2- ([n/2] mod 4); if n mod 4 = 0 it is 1 or lk!(k- ) -1, depending on whether or not d, = 0 or 1, where Ic is the largest power of 2 dividing n; and if n mod 4 = 3 it is lktck- ) -1 or 1, depending on whether d 7L+l = 0 or 1, where Ic is the largest power of 2 dividing n $1. When 1 = 2 the same rules apply, except that O s must be removed, so there is a more complicated pattern depending on n mod 24. Cf. J. Number Theory 11 (1979), 209-217

606 ANSWERS TO EXERCISES 45.3 34. (a) Dividing z and y by gcd(z, y) yields g(n) = zd,n h(n/d); apply exercise 28(c), and use the symmetry between primed and unprimed variables. (b) For fixed y and t, the representations with zd 2 Z have Z < Jnd; hence there are O(m/y) such representations. Now sum for 0 < t 5 y < a. (c) If s(y) is the given sum, then &y s(d) = y(Hzy -HY) = k(y), say; hence s(y) = xd,y Ic(y/d). Now /c(y) = yln2–f+OPly)~ (4 Cl

4.5.3 ANSWERS TO EXERCISES 605 29. The sum is approximately (((12 In 2)/x2) In N!)/N -c,,, A(d)/d2 + 1.47; here c,,, h(d)/d2 converges to the constant value –< (2)/c(2), andwe know that In N! = N l;N -N + O(log N) by Stirling s approximation. 30. The modified algorithm affects the calculation if and only if the following division step in the unmodified algorithm would have the quotient 1, and in this case it avoids the following division step. The probability that a given division step is avoided is the probability that Ak = 1 and that this quotient is preceded by an even number of quotients equal to 1. By the symmetry condition, this is the probability that Ak = 1 and is followed by an even number of quotients equal to 1. The latter happens if and onlyifxk-1 > d-1 =0.618…, where 4 is the golden ratio: For Ak = 1 and Ak+l > 1 iff 3 2 xk-1 < 1; .& = Ak+i = Ak+2 = 1 and Ak+s > 1 iff 5 2 x!+-1 < f; etc. Thus we save approximately &i(I) -Fk-l(# -1) % 1 -lg+ M 0.306 of the division steps. The average number of steps is approximately ((12 In 4)/x ) Inn, when v = n and u. is relatively prime to n. Kronecker [Vorlesungen iiber Zahlentheorie 1 (Leipzig: Teubner, 1901) 1181 observed that this choice of least remainder in absolute value always gives the shortest possible number of iterations, over all algorithms that replace 1~ by (-&u) mod v at each iteration. For further results see N. G. de Bruijn and W. M. Zaring, Nieuw Archief voor Wiskunde (3) 1 (1953) 105-112; G. J. Rieger, Math. Nachr. 82 (1978), 157-180. On many computers, the modified algorithm makes each division step longer; the idea of exercise 1, which saves al11 division steps when the quotient is unity, would be preferable in such cases. 31. Let a0 = 0, al = 1, an+1 = 2a,+a,-1; then a, = ((l+&) -(l-&) )/2&, and the worst case (in the sense of Theorem F) occurs when u = a, + a,-~, v = a,, n 2 2. This result is due to A. Dupre [J. de Math. 11 (1846), 41-641, who also inves- tigated more general look-ahead procedures suggested by J. Binet. See P. Bachmann, Niedere Zahlentheorie 1 (Leipzig: Teubner, 1902), 99-118, for a discussion of early analyses of Euclid s algorithm. 32. (b) Qm--1(x1,. . ,xm-1)Qn--1(xm+2,. . . , z~+~) corresponds to Morse code se- quences of length (m + n) in which a dash occupies positions m and (m + 1); the other term corresponds to the opposite case. (Alternatively, use exercise 2. The more general identity m+n Xl,..., Gn+n)&k(Gn+l, . . . , %n+k) = Q ( mfk Xl,. . . , Xm+k)Qn(Gn+lr , Xm+n) Q ( + (-l)kQ,-~(z~, , G-1)&n-k--1(h+k+z,. , Gn+n) also appeared in Euler s paper.) 33. (a) The new representations are z = m/d, y = (n -m)/d, 2 = y = d = gcd(m, n -m), for an < m < n. (b) The relation (n/x ) -y 5 z < n/x defines z. (c) Count the x satisfying (b). (d) A pair of integers x > y > 0 with gcd(x, y) = 1 can be uniquely written in the form x = Qm(xl,. ,xm), y = Q,,.–1(x1,. ,xm–l), where x1 2 2 and m 2 1; here y/x = /xm,. . ,sl/. (e) It suffices to show that ~l

604 ANSWERS TO EXERCISES 4.5.3 17. (b) /xl -1, 1,22 -2,1,x3 -2,1,. . . , 1, zzn–l -2,1, ~2~ -l/. [Note: One can remove negative parameters from continuants by using the identity Qm+n+l(xl,~~~, xnr -2, ym, . . , Yl) = (-l)m-1Qm+n+2(51,~~~, G-1, Zn -1,1,x -1, -ym,. . . , -y1), from which we obtain Qm+n+l(xlr . . . ,xn, -x,ym, , yl) = -Q m+n+3 (2J1,…,&-1,G-1,1,x -x,1, ym -1, ym-1,. . . ,y1) after a second application.] (c) 1+/1,1,3,1,5,1,… /=1+/2m+l,l/, m>O. 19. The sum for 1 5 k 5 N is log,((l $ z)(N + l)/(N + 1 + z)). 20. Let H = SG, g(z) = (1 + s)G (z), h(z) = (1 + z)H (z). Then (35) implies that h(x + 1)/(x + 2) -Mx)l(x + 1) = -41-t x)r29(1/(1 + x)1/(1 + l/(1 +x,1. 21. p(z) = ~/(~~+1)~+(2-c)/((c-l)z+1)~, Up(z) = l/(z+c) . When c 5 1, the minifnum of ~(z)/U~(s) occurs at z = 0 and is 2c2 5 2. When c > #J = a(&+ l), the minimum occurs at z = 1 and is 5 c$~. When c RZ 1.31266 the values at 2 = 0 and z = 1 are nearly equal and the minimum is > 3.2; the bounds (0.29) (p 5 U p 5 (0.31)n(o are obtained. Still better bounds come from well-chosen linear combinations Tdx) = c %/(X + c3). 23. By the interpolation formula of exercise 4.6.4-15 with 20 = 0, 51 = z, z2 = Z+E, letting t + 0, we have the general identity R ,(z) = (Rn(z) -R,(O))/s + $&(0(s)) for some e(x) between 0 and x, whenever R, is a function with continuous second derivative. Hence in this case R ,(z) = 0(2- ). 24. 00. [A. Khinchin, in Compos. Math. 1 (1935), 361-382, proved that the sum A1 +. . . +A, of the fiist n partial quotients of a real number X will be asymptotically n lg n, for almost all X. Exercise 35 shows that the behavior is different for rational X.1 25. Any union of intervals can be written as a union of disjoint intervals, since we have Uk,lIk =Uk,l(lkUllj 1,At > 1, and &&%,A2 ,…, A)t is a divisor of n. Therefore (6) completes the proof. [Note: If ml/n = /AI,. . . ,At/ and m2fn = /At ,…, AI/, where ml and m2 are relatively prime to n, then mlm2 = *l (modulo n); this rule defines the correspondence. When A1 = 1 an analogous symmetry is valid, according to (44).] 27. First prove the result for n = pe, then for n = rs, where r and s are relatively prime. Alternatively, use the formulas in the next exercise. 28. (a) The left-hand side is multiplicative (see exercise 1.2.4-31), and it is easily evaluated when n is a power of a prime. (c) From (a), we have MGbius s inversion formula: If f(n) = Cd,,, g(d), then s(n) = Cd,n ~(nlQf(4.

4.5.3 ANSWERS TO EXERCISES 603 origin as n grows, so the continued fraction actually represents tanhz throughout the complex plane. Another proof gives further information of a different kind: If we let (n + Ic)! snPk A,(z) = n! c zklk! = c k,(n-k)! , OO then (n -i- k -l)! ((4n f 2)k + (n + 1 -k)(n -k)) Zn+l-k &+1(z) = c k! (n + 1 - k)! k>O = (4n + 2)A,(z) + z A,-l(z). It follows, by induction, that g,(i, 4,. . . ) 2&i) = An(2z;n;$J-2z), Qnvl( z, . . . , F) = An(2z;n-&-2z). Hence /z-l, 32-l , . , (2n -l)zC / = $; ; pi-;;;, n z 71 and we want to show that this ratio approaches tanhz. By Eqs. 1.2.9-11 and 1.2.6-24, e A,(-z) = n! c z WI>0 Hence e*A,(-z) -An(z) = Rn@) = (-l)n22n+l c (n + Ic)! xk k,O (2n + k + l)! k! - We now have (e2 -1)(An(2z)+An(-2z))-(e2Z+1)(An(2z)-An(-2z)) = 2R,(2z); hence 2R,(2z) tanh z -/z-l, 32-l) . . , (2n -l)z- / = (&(2z) -I- A(-2z))(e2 + 1) Thus we have an exact formula for the difference. When IzI 5 1, the factor e2* + 1 is bounded away from zero, J&(2z)I 5 en!/(2n + l)!, and >P+f-+..)=~y - Thus convergence is very rapid, even for complex values of z. To go from this continued fraction to the continued fraction for eZ, we have tanhz = 1 -2/(e2 + 1); hence we get the continued-fraction representation for (e2 + 1)/2 by simple manipulations. Hurwitz s rule gives the expansion of e2* + 1, from which we may subtract unity. For n odd, e –z/n = / 1,3mn + Ln/2J, (12m + 6)n, (3m + 2)n + [n/21,1/, m 2 0. Another derivation has been given by C. S. Davis, J. London Math. Sot. 20 (1945), 194-198.

602 ANSWERS TO EXERCISES 45.3 on output: X3 -1 5 1 1 1 2 1 2 Co xk 39 97 -58 -193 -2 -25 -62 37 123 2 16 53 3 5 17 22 7 1 2 3 5 1 3 1 4 5 14 1 2 1 3 7 1 2 7 9 25 12 1 0 1 2 2 1 co 0 M. Mend&s France has shown that the number of quotients output per quotient input is asymptotically bounded between l/r and r, where r = 2]K( lad -bc])/2] + 1 and K is the function defined in exercise 38; this bound is best possible. [Topics in Number Theory, ed. by P. Turan, Colloquia Math. Sot. Jrinos Bolyai 13 (1976), 183-194.1 Gosper has also shown that the above algorithm can be generalized to compute the continued fraction for (azy + bx + cy + d)/(Axy + Bx + Cy + D) from those of x and y (in particular, to compute sums and products). [MIT AI Laboratory Memo 239 (Feb. 29, 1972) Hack 101.1 16. It is not difficult to prove by induction that fn(z) = 2/(2n + 1) + O(z3) is an odd function with a convergent power series in a neighborhood of the origin, and that it satisfies the given differential equation. Hence jr(z) = /z-l + fl(Z)/ = = /z-l, 32-l,. . . ) (2n + l)z- + fn+l(z)/. It remains to prove that lim,,, /z-l, 32-l , . , (2n + l)z- / = fo(z). [Actually Euler, age 24, obtained continued fraction expansions for the considerably more general differential equation f;(z) = uzm + bf,(z)z - + cf,(z) ; but he did not bother to prove convergence, since formal manipulation and intuition were good enough in the eighteenth century.] There are several ways to prove the desired limiting equation. First, letting f&) = c, %kZk, we can argue from the equation (2n + 1)&l + (2n + 3)a,3z2 + (2n + 5)a,sz4 + . . . = 1 - (U,lZ + u,sz3 + a,5z5 + ) that (-l)ka,(zk+l) is a sum of terms of the form ck/(2n+l)k+ (2n+bk,). . . (2n+bkk), where the ck and bkm are positive integers independent of 72. For example, we have –an7 = 4/(2n + 1)4(2n + 3)(2n + 5)(2n + 7) + 1/(2n + 1)4(2n + 3)2(2n + 7). Thus ]a(,+i)k] 5 l&k], and ]fn(z)] 5 tan]z] for ]z] < r/2. This uniform bound on fn(z) makes the convergence proof very simple. Careful study of this argument reveals that the power series for fn(z) actually converges for ]z] < adm/2; this is interesting, since it shows that the singularities of fn(z) get farther and farther away from the

4.5.3 ANSWERS TO EXERCISES 601 But by (12), p,-l/q,-l and p,/q, are extremely close to X; since X # Y, Y -p,/q, and Y -p,-l/q,-1 will have the same sign as Y-X for all large n. This proves that Y, < 0 for all large n; hence 0 < X, < X, -Y, = am/V,; V, must be positive. Also U, < a, since X, > 0. Hence V, < 2@, since V, < A,V, < m f U,-I. Finally, we want to show that U, > 0. Since X, < 1, we have U, > a–V,, so we need only consider the case V, > a; then U, = A,V, -U,-I 2 V, -U,-1 > fi -U,-1, and this is positive as we have already observed. Note: In the repeating cycle, fi + U, = A,V, + (a -U,-I) > V,; hence l(dB + u,+,)/V,+,J = [An+1 + Vn/(fi + Un)l = Am+1 = l(a + Un)/Vn+ll. In other words A,+1 is determined by U n+l and Vn-tl; we can determine (U,,V,) from its successor (U,+I,V~+I) in the period. In fact, when 0 < V, < a $ Un and 0 < U,, < a, the arguments above prove that 0 < V,+I < @ f U,+l and 0 < u,+~ < fl; moreover, if the pair (U,+I, V,+I) follows (U , V ) with 0 < V < n + U and 0 < U < a, then U = U, and V = V,. Hence (U,, V,) is part of the cycle if and only if 0 < V, < a + U, and 0 < U, < a. (c) * = X,Y, = (4nX -Pn)(%Y -PTL) (%-1X -P,-1)(q,-1Y -pn-1) There is also a companion identity, namely VPnPn-1 + U(P&-1 + Pn-1%) + ((U -D)/V)q,q,-1 = (-l) U,. (d) If X, = X, for some n # m, then X is an irrational number that satisfies the quadratic equation (qnX -p,)/(q,-1X -~-1) = (q,X -p,)/(q,-1X -pm-l). 14. As in exercise 9, we need only verify the stated identities when c is the last partial quotient, and this verification is trivial. Now Hurwitz s rule gives 2/e = /1,2,1,2,0,1,1,1,1,1,0,2,3,2,0,1,1,3,1,1,0,2,5, /. Taking the reciprocal, collaps- ing out the zeros as in exercise 9, and taking note of the pattern that appears, we find (cf. exercise 16) that e/2 = 1 + / 2,2m + 1,3,1,2m + 1, 1,3/, m 2 0. [Schriften der phys.-okon. Gesellschafi zu Khigsberg 32 (1891) 59-62.1 15. (This procedure maintains four integers (A, B, C, D) with the invariant meaning that our remaining job is to output the continued fraction for (Ay + B)/(Cy + D), where y is the input yet to come. ) Initially set j + k + 0, (A, B, C, D) t (a, b, c, d); then input zJ and set (A, B, C, D) + (As, + B,A, Cx, + D, C), j + j + 1, one or more times until C + D has the same sign as C. (When j 2 1 and the input has not terminated, we know that 1 < y < co; and when C + D has the same sign as C we know therefore that (Ay + B)/(Cy + D) lies between (A + B)/(C + D) and A/C.) Now comes the general step: If no integer lies strictly between (A+ B)/(C + D) and A/C, output Xk c LA/C], and set (A, B, C, D) + (C, D,A -XkC, B -&D), k + k + 1; otherwise input xj and set (A, B, C, D) + (Ax, + B, A, Cx, + D, C), j + j + 1. The general step is repeated ad infinitum. However, if at any time the final x3 is input, the algorithm immediately switches gears: It outputs the continued fraction for (Ax, + B)/(Cx, + D), using Euclid s algorithm, and terminates. The following tableau shows the working for the requested example, where the matrix (E G) begins at the upper left corner, then shifts right one on input, down one

600 ANSWERS TO EXERCISES 45.3 7. Only 12.. . TZ and n .2 1. (The variable xk appears in exactly Fk Fn-4 terms; hence x1 and xn can only be permuted into x1 and xn. If xi and xn are fixed by the permutation, it follows by induction that x2, . . . , X,+-I are also fixed.) 9. This is equivalent to Qn-z(An-I,. . . , -42) -X&n-&L-l,. . . , A) = - &n-1(&, . . , AZ) -XQn(An, . . . , AI) XV% and by (6) this is equivalent to x = Qn-I(Az, . , An) +X,&n-2(&r . . . , An-l) Q&41, . . . , An) + XnQn-I(&, . . .,&-I) 9. (a) By definition. (b), (d) Prove this when n = 1, then apply (a) to get the result for general 72. (c) Prove when n = Ic + 1, then apply (a). 10. If A0 > 0, then Bo = 0, BI = Ao, Bz = AI, BB = AZ, Bd = As, Bg = A, m=5.IfAo=O,thenBo=A1,B1=A2,B2=As,Bs=Aq,m=3.IfAo=-l and AI = 1, then BO = -(AZ + 2), B1 = 1, B2 = As -1, Bs = ALI, m = 3. If A0 = -1 and AI > 1, then BO = -2, B2 = A1 -2, Ba = AZ, Bd = As, B5 = A4, m=5.IfA~<-l,thenB~=-l,B~=1,B~=-A~-2,Bs=1,B~=A~-l, B5 = Az, B6 = As, Br = A. [Actually, the last three cases involve eight subcases; if any of the B s is set to zero, the values should be collapsed together by using the rule of exercise 9(c). For example, if A0 = -1, Ai = As = 1, we actually have BO = -(A2 f 2), BI = & $ 1, m = 1. Double collapsing occurs when AO = -2, Ai = 1.1 11. Let qn = Q&41,. ,&I, 4, = &@I,. . . , B,), pn = Qn+l(Ao,. . . ,An), pi, = Qn+l(Bo,. . , h). BY (5) and (11) we have X = (pm + pm-lXm)/(qm + q,-lx,), Y = (p , +~ ,_,Y,)/(q:,+q)n_~Y,); therefore if X, = Y,, the stated relation between X and Y holds by (8). Conversely, if X = (qY + r)/(sY + t), Iqt -rsj = 1, we may assume that s 2 0, and we can show that the partial quotients of X and Y eventually agree, by induction on s. The result is clear when s = 0, by exercise 9(d). If s > 0, let q = as + s , where 0 5 s < s. Then X = a + l/((sY + t)/(s Y + r -at)); since s(r -at) -ts = sr -tq, and s < s, we know by induction and exercise 10 that the partial quotients of X and Y eventually agree. [Note: The fact that m is always odd in exercise 10 shows, by a close inspection of this proof, that X, = Y, if and only if X = (qY + r)/(sY + t), where qt -rs = (-l) - .] 12. (a) Since VnVnfl = D -Uz, we know that D -Uz+l is a multiple of Vn+i; hence by induction X, = (v@ -U,)/V,, where lJ,, and V, are integers. [Note that the identity Vn+l = A,(U,-I -Un) + V,-l makes it unnecessary to divide when V,+l is being determined.] (b) Let Y = (-a -U)/V, Y, = (-6 -Un)/Vn. The stated identity obviously holds by replacing fi by -4% in the proof of (a). We have y = (PnlY, + Pn-l)/(qn/Y, + qnvl), where pn and q,, are defined in part (c) of this exercise; hence Y, = (-q,/q,-l)(Y -p,/q,)/(Y -pn-l/qn-l).

4.5.3 ANSWERS TO EXERCISES 599 34. Keep track of the most significant and least significant words of the operands (the most significant is used to guess the sign oft and the least significant is to determine the amount of right shift), while building a 2 x 2 matrix A of single-precision integers such that A(z) = ($z), w h ere w is the computer word size and where U and w are smaller than u and w. (Instead of dividing the simulated odd operand by 2, multiply the other one by 2, until obtaining multiples of w after exactly lgw shifts.) Experiments show this algorithm running four times as fast as Algorithm L, on at least one computer. 35. (Solution by Michael Penk.) Yl. [Find power of 2.1 Same as step Bl. Y2. [Initialize.] Set (~1, ~2, us) + (l,O, U) and (01, VZ, 21s) +– (w, 1 - U, w). If u is odd, set (tl, t2, ts) + (0, -1, -v) and go to Y4. Otherwise set (tr, t2, ts) t (l,O, u). Y3. [Halve ts.] If ti and tz are both even, set (tl, t2, t3) t (tl, t2, t3)/2; otherwise set (tl, tz, t3) + (tl + v, t2 -u, t3)/2. (In the latter case, tl + IJ and t2 -U will both be even.) Y4. [Is t3 even?] If t3 is even, go back to Y3. Y5. [Reset max(us, ws).] If t3 is positive, set (~1, ~2, us) t (tl, t2, t3); otherwise set (Vl,V2,V3)+(w–l,– U.-t2,-t3). Y6. [Subtract.] Set (tl, t2, t3) + (~1,212, us)-(211,212, ~3). Then if tl < 0, set (tl, t2) t (tl + V, t2 -u). If t3 # 0, go back to B3. Otherwise the algorithm terminates with (~1,212, us . zk) as the output. 1 It is clear that the relations in (16) are preserved, and that 0 5 ui, ~11,tl 2 V, 0 2 212,212,t2 2 -u after each of steps Y2-Y6. If u is odd after step Y2, then step Y3 can be simplified, since tl and t2 are both even iff t2 is even; similarly, if v is odd, then tl and t2 are both even iff tl is even. Thus, as in Algorithm X, it is possible to suppress all calculations involving ~2, 212, and t2, provided that v is odd after step Y2. This condition is often known in advance (e.g., when v is prime and we are trying to compute U-I modulo w). SECTION 4.5.3 1. The running time is about 19.022 + 6, just a trifle slower than Program 4.5.2A. 2 Qn(51,Z2,..., G-I, xn) &n-1(21, ~2,. . . , G-I) * ( Qn-1(~2,. . . , G-I, xn) Qn--2(x2,. ,xn-I) > 3. Qn(x1,. . . , xn). 4. By induction, or by taking the determinant of the matrix product in exercise 2. 5. When the Z S are positive, the q s of (9) are positive, and qnfl > qnpl; hence (9) is an alternating series of decreasing terms, and it converges iff q,q,+l -+ CCL By induction, if the Z S are greater than E, we have q,, 2 c(1 + ~/2)~, where c is chosen small enough to make this inequality valid for n = 1 and 2. But if xn = 1/2n, we have qn 5 2 -1/2n. 6. It suffices to prove that A1 = &; and from the fact that 0 5 /xi,. . . , xn/ < 1 whenever zi, . . . , xn are positive integers, we have B1 = [l/X] = Al.

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.]