464 ARITHMETIC 46.3 16. [HM15] Show that Theorem (Photoshop web design)
464 ARITHMETIC 46.3 16. [HM15] Show that Theorem D is not trivially true just because of the binary method; if LB(n) denotes the length of the addition chain for n produced by the binary S-and-X method, lB(n)/X(n) does not approach a limit as n -+ co. 17. [M%] Explain how to find the intervals J1, . . , Jh that are required in the proof of Lemma P. 18. [HM24] Let ,0 be a positive constant. Show that there is a constant a: < 2 such that c(:+ :)( ;v)41Y((mits)2) < am for all large m, where the sum is over all s, t, v satisfying (30). 19. [M,8] A multiset is like a set, but it may contain identical elements repeated a finite number of times. If A and B are multisets, we define new multisets AN B, AU B, and An B in the following way: An element occurring exactly a times in A and b times in B occurs exactly a + b times in AN B, exactly max(a, b) times in AU B, and exactly min(a, b) times in A n B. (A set is a multiset that contains no elements more than once; if A and B are sets, so are A U B and A n B, and the definitions given in this exercise agree with the customary definitions of set union and intersection.) a) The prime factorization of an integer n > 0 is a multiset N whose elements are primes, where l&e,, = n. The fact that every positive integer can be uniquely factored into primes gives us a one-to-one correspondence between the positive integers and the finite multisets of prime numbers; for example, if n = 22 . 33 .17, the corresponding multiset is N = {2,2,3,3,3,17}. If M and N are the multisets corresponding respectively to m and n, what multisets correspond to gcd(m,n), lcm(m, n), and mn? b) Every manic polynomial f(z) over the complex numbers corresponds in a natural way to the multiset F of its roots ; we have f(z) = &,(z -0. If f(z) and g(z) are the polynomials corresponding to the finite multisets F and G of complex numbers, what polynomials correspond to F u G, F U G, and F n G? c) Find as many interesting identities as you can that hold between multisets, with respect to the three operations M, IJ, Il. 20. [M20] What are the sequences Si and Mij (0 2 i 2 r, 0 2 j 5 t) arising in Hansen s structural decomposition of star chains (a) of Type 3? (b) of Type 5? (The six types are defined in the proof of Theorem B.) b 21. [M25] (W. Hansen.) Let q be any positive integer. Find a value of n such that I(n) 2 l*(n) -4. 22. [MZ?O] Prove that the addition chain constructed in the proof of Theorem F is an lo-chain. 23. [MXI] Prove Brauer s inequality (50). b 24. [M.%?] Generalize the proof of Theorem G to show that l ((B -l)/(B -1)) 2 (n -1) 1 (B) + 1 (n), for any integer B > 1; and prove that 1(2 -1) 2 1(2m -1) + mn -m + l (n). 25. [ZVO] Let y be a fraction, 0 < y < 1, expressed in the binary number system as y = (.dr . . . c&)2. Design an algorithm to compute zy using the operations of multiplication and square-root extraction. b 26. [ML?41 Design an efficient algorithm that computes the nth Fibonacci number F,, modulo m, given large integers n and m.