Web host - 4.5.3 ANALYSIS OF EUCLID S ALGORITHM 361 21. [HiV29]
4.5.3 ANALYSIS OF EUCLID S ALGORITHM 361 21. [HiV29] (E. Wirsing.) The bounds (37) were obtained for a function (o correspond- ing to g with Tg(z) = l/(a: + 1). Sh ow that the function corresponding to Tg(z) = l/(z + c) yields better bounds, when c > 0 is an appropriate constant. 22. [H.46] (K. I. Babenko.) Develop efficient means to calculate accurate approxima- tions to the quantities Xj and I j(S) in (42), for small j > 3 and for 0 5 z 2 1. 23. [H.,%?] Prove (51), using results from the proof of Theorem W. 24. [M%?] What is the average value of a partial quotient A, in the regular continued fraction expansion of a random real number? 25. [HM,%] Find an example of a set 1 = 11 u 1~ U 1s lJ . e. c [0, l], where the I s are disjoint intervals, for which (43) does not hold. 26. [MH] Show that if the numbers {l/n, 2/n,. . . , ]n/2J/n} are expressed as regular continued fractions, the result is symmetric between left and right, in the sense that /At,… ,Az,AlI appears whenever /Al, AZ, . . . , At/ does. 27. [Mz?~] Derive (53) from (47) and (52). 28. [A&%?] Prove the following identities involving the three number-theoretic func- tions cp(n), p(n), A(n): a) C p(d) = &I. b) Inn = c A(d), n = c 44. dn dn dn 4 A(n) = xp(f)lnd cp(n)= cp(z)d. dn 4 29. [A&Y?] Assuming that Tn is given by (53), show that (55) equals (56). b 30. [H&f%?] The following variant of Euclid s algorithm is often suggested: Instead of replacing v by umodv during the division step, replace it by ](~modv) -v] if umodw > iv. Thus, for example, if u = 26 and v = 7, we have gcd(26,7) = gcd(-2,7) = gcd(7,2); -2 is the remainder of smallest magnitude when multiples of 7 are subtracted from 26. Compare this procedure with Euclid s algorithm; estimate the number of division steps this method saves, on the average. b 31. [A&%] Find the worst case of the modification of Euclid s algorithm suggested in exercise 30; what are the smallest inputs u > v > 0 that require n division steps? 32. [.20] (a) A Morse code sequence of length n is a string of T dots and s dashes, where r + 29 = n. For example, the Morse code sequences of length 4 are . . . . . . .-) *-.) -..-.., –. Noting that the continuant 94(x1, z2, zs, 24) is zlz2×3z4 + Z1Z2 + 2124 + Z3Z4 + 1, find and prove a simple relation between Qn(zi, . . . , zn) and Morse code sequences of length n. (b) (L. Euler, Novi Comm. Acad. Sci. Pet. 9 (1762), 53-69.) Prove that Qm+n(% *. . , %n+n) = Q&I,. . . ,~J&&m+l,. . . ,xm+n) + Qm-~(a,. . . , em-1)&n-l(zm+2,. . . , zm+n).