608 ANSWERS TO EXERCISES 4.5.3 42. Suppose that
608 ANSWERS TO EXERCISES 4.5.3 42. Suppose that (IqXII = IqX -pi. We can always find integers u and v such that q = uq,-1 + vq, and p = up,-.1 + up,, where p, = Qn-~(A2,. . . ,An), since qnpn-1-qn-1pn = fl. We must have uw < 0, hence u(q,-IX -~~-1) has the same sign as v(q,X-pp,), and IqX--pi = JuI lqn-lX-p,-lI + lzll lqnX-p,l. This completes the proof, since u # 0. See Theorem 6.4s for a generalization. 43. If z is representable, so is the father of z in the Stern-Peirce tree of exercise 40; thus the representable numbers form a subtree of that binary tree. Let (U/U ) and (V/V ) be adjacent representable numbers. Then one is an ancestor of the other; say (u/u ) is an ancestor of (V/V ), since the other case is similar. Then (u/u ) is the nearest left ancestor of (V/V ), so all numbers between u/u and v/w are left descendants of (V/U ) and the mediant ((u + w)/(u + v )) is its left son. According to the relation between regular continued fractions and the binary tree, the mediant and all of its left descendants will have (U/U ) as their last representable p,/qi, while all of the mediant s right descendants will have (w/z) ) as one of the pz/qz. (The numbers p,/q, label the fathers of the turning-point nodes on the path to x.) 44. A counterexample for A4 = N = 100 is (U/U ) = 4, (U/W ) = $$. However, the identity is almost always true, because of (12); it fails only when u/u + w/v is very nearly equal to a fraction that is simpler than (U/U ). 45. See M. S. Waterman, BIT 17 (1977), 465-478. SECTION 4.5.4 1. If dk isn t prime, its prime factors are cast out before dk is tried. 2. No; the algorithm would fail if pt-1 = pt, giving 1 as a spurious prime factor. 3. Let P be the product of the first 168 primes. [Note: Although P = 19590.. .5910 is a 416-digit number, such a gcd can be computed in much less time than it would take to do 168 divisions, if we just want to test whether or not n is prime.] 4. In the notation of exercise 3.1-11, 2~ gmax(~+l~~)lp(p, X) = ; c f(l) n (1 -;); c I1>x 121 Ilk<1 where f(l) = Cl,,,, 2r gmax( –XrX)l. If 1 = 2kfe, where 0 < 6 5 1, we have f(2) = 12(3. 2- -2. 2-2e), where the function 3. 2-* -2 . 2-20 reaches a maximum of { at 0 = lg(4/3) and has a minimum of 1 at 0 = 0 and 1. Therefore the average value of 2r1gmax(Vf1,X)1 lies between 1.0 and 1.125 times the average value of p + X, and the result follows. [Algorithm B is a refinement of Pollard s original algorithm, which was based on exercise 3.1-6(b) instead of the (yet undiscovered) result in exercise 3.1-7. He showed that the least n such that X2, = X, has average value -(7r2/12)Q(m); this constant r2/12 is explained by Eq. 4.5.3-21. Hence the average value of 3n in his original method is -(~/2)~/ fi = 3.0926. Richard Brent has observed that, as m + 00, the density fl,,,,, (1 -k/m) = exp(–l(l-1)/2m+0(13/m2)) approaches a normal distribution, and we may assume that 0 is uniformly distributed. Then 3.2- -2.2-2e takes the average value 3/(41n 2), and the average number of iterations needed by Algorithm B comes to -(3/(4ln2) + a)-= 1.983& A similar analysis of the more general method in the answer to exercise 3.1-7 gives -1.9266, when p = 2.4771 is chosen optimally as the root of (p2 -1) lnp = p2 -p + 1.1