MySQL Web Server, Tomcat, Jsp, Struts Hosting Blog

566 ANSWERS TO EXERCISES 4.1 either zero or one, there is obviously only one way to proceed, otherwise it has a unique reversing representation by induction. [It follows that every positive integer has exactly two such representations with decreasing exponents eo > el > . . . > et: one with t even and the other with t odd.] 28. A proof like that of exercise 27 may be given. Note that a + bi is a multiple of 1 + i by a complex integer if and only if a + b is even. This representation is intimately related to the dragon curve discussed in the answer to exercise 18. 29. It suffices to prove that any collection {TO, 7 1, T2, . . . } satisfying Property B may be obtained by collapsing some collection {SO, S1, S2, . . . }, where SO = (0, 1, . . . , b- 1) and all elements of S1, S2, . . . are multiples of b. To prove the latter statement, we may assume that 1 E TO and that there is a least element b > 1 such that b e TO. We will prove, by induction on n, that if nb @ TO, then nb + 1, nb f 2, . . . , nb + b -1 are not in any of the T3 s; but if nb E TO, then so are nb+ 1, . . . . nb+ b-1. The result then follows with S1 = {nb 1 nb E TO}, 5 2 = TI , & = T2, etc. If nb e TO, then nb = to + tl +. . . , where tl, t2, . . . are multiples of b; hence to < nb is a multiple of b. By induction, (to + k) + tl + t2 + . is the representation of nb + k, for 0 < k < b; hence nb + k @ Tj for any j. If nb E TO and 0 < k < b, let the representation of nb + k be to + tl + … . We cannot have t, = nb + k for j 2 1, lest nb + b have two representations (b -k) + . . . + (nb + k) + . . . = (nb) + . . . + b + . . . By induction, to mod b = k; and the representation nb = (to -k) + tl + . . . implies that to = nb + k. [Reference: AJieuw Archief voor Wiskunde (3) 4 (1956), 15-17. A finite analog of this result was derived by P. A. MacMahon, Combinatory Analysis 1 (1915), 217-223.1 30. (a) Let A3 be the set of numbers n whose representation does not involve b,; then by the uniqueness property, n E Ai iff n + bJ sf A3. Consequently we have n E A3 iff n f 2bj E Aj. It follows that, for j # k, n E Aj n Ak iff n + 2bjbk E A3 f-l Ak. Let m be the number of integers n E A3 n Ak such that 0 < n < 2bjbk. Then this interval contains exactly m integers that are in Aj but not Ak, exactly m in Ak but not Aj, and exactly m in neither Aj nor Ak; hence 4m = 2bjbk. Therefore b, and bk cannot both be odd. But at least one b3 is odd, of course, since odd numbers can be represented. (b) According to (a) we can renumber the b s so that bo is odd and bl, bz, . . are even; then Jbl, ib2, . . . must also be a binary basis, and the process can be iterated. (c) If it is a binary basis, we must have positive and negative dk s for arbitrarily large k, in order to represent f2n when n is large. Conversely, the following algorithm may be used: Sl. [Initialize.] Set k + 0. S2. [Done?] If n = 0, terminate. S3. [Choose.] If n is odd, include 2kdk in the representation, and set n + (n -dk)/2. Otherwise set n +-n/2. S4. [Advance k.] Increase k by 1 and return to S2. 1 At each step the choice is forced; furthermore step S3 always decreases In unless n = -dk, hence the algorithm must terminate. (d) Two iterations of steps S2-S4 in the preceding algorithm will change 4m -+ m, 4m+l+m+5,4m+2-+m+7,4m+3 + m -1. Arguing as in exercise 19, we need only show that the algorithm terminates for -2 5 n 5 8; all other values of n

4.1 ANSWERS TO EXERCISES 565 23. The set S = {c,,, akbek 1 ak E D} is closed as in exercise 18, hence it is measurable, and in fact % has positive measure. Since bS = u,,,(a + S), we have bp(S) = p(bS) 5 CaED p(a $ S) = CaED p(S) = bp(S), and we must therefore have da + S) II (a + S)) = 0 w h en a # a E D. Now T has measure zero since it is a union of countably many sets of the form 10k(n + ((a + S) n (a + S))), a # a , each of measure zero. [The set T cannot be empty, since the real numbers cannot be written as a countable union of disjoint, closed, bounded sets; cf. AMA4 84 (1977), 827-828. If D has less than b elements, the set of numbers representable with radix b and digits from D has measure zero. If D has more than b elements and represents all reals, T has infinite measure.] 24. { 2a.10k+a 10 2 a < 5,0 5 a < 2) or { 5a .10k+a 1 0 5 a < 5,0 2 a < 2}, for k 2 0. [R. L. Graham has shown that there are no more sets of integer digits with these properties. And Andrew Odlyzko has shown that the restriction to integers is superflous, in the sense .that if the smallest two elements of D are 0 and 1, all the digits must be integers. Proof: Let S = { c,,, akbk 1 ak E D } be the set of fractions, and let X = {(a,. . . aO)b 1 ak E D} be the set of whole numbers ; then [0, co) = U,,,b + S), and (x + S) n (2 + S) h as measure zero for 2 # Z E X. We have (0,l) c S, and by induction on m we will prove that (m, m + 1) C zm. + S for some xrn E X. Let z,,, E X be such that (m, m + E) n (2, + S) has positive measure for all E > 0. Then 2711 5 m, and z,,, must be an integer lest 21Zn~ f S overlap zrn + S too much. If zm > 0, the fact that (m–2,, m-z,,, f 1) n S has positive measure implies by induction that this measure is 1, and (m, m + 1) c zm + S since S is closed. If ~,=Oand(m,m+1)~S,wemusthavem<& 0, and the result follows by induction, since n/2 has a unique such representation. If n is odd, we must take eo = 0, and the problem reduces to representing -(n -1)/2; if the latter quantity is

564 ANSWERS TO EXERCISES 4.1 node if it is an initial subsequence of that node. By the infinity lemma this tree has an infinite path (ai, o2, as,. ), and it follows that c,,, ~166 is a limit point of - {YI,YZ,…} in S. By the answer to exercise 16, all numbers of the form (~+bi)/l6~ are representable, when a and b are integers. Therefore if z and y are arbitrary reals and k 2 1, the number sk = (]lS s] + ]16ky]i)/16k is in S + m + ni for some integers m and n. It can be shown that S + m + ni is bounded away from the origin when (m, n) # (0,O). Consequently if 1×1 and ]y] are fixed and k is sufficiently large, we have sk E S, and hk+rn zk = x + yi is in s. [B. Mandelbrot calls S the twindragon, since he noticed that it is essentially obtained by joining two dragon curves belly-to-belly; see his book Fracta1s: Form, Chance, and Dimension (San Francisco: Freeman, 19X ), 313-314. Other properties of the dragon curve are described in C. Davis and D. E. Knuth, J. Recr. Math. 3 (1970), 66-81, 133-149.1 19. If m > u or m < 1, find a E D such that m = a (modulo b); the desired representation will be a representation of m = (m -u)/b followed by a. Note that m > u implies 1 < m < m; m < I implies m < m < U; so the algorithm terminates. [There are no solutions when b = 2. The representation will be unique iff 0 E D; nonunique representation occurs for example when D = (-3, -1,7}, b = 3, since (o)s = (3773~)s. When b 2 3 it is not difficult to show that there are exactly 2b-3 solution sets D in which ]a] < b for all a E D. Furthermore the set D = (0, 1, 2-~b , 3 -E3bn, . . , b - 2 -Eb-2bn, b - 1 -b } gives unique representations, for all b 2 3 and n 2 1, when each ~j is 0 or 1. Reference: Proc. IEEE Symp. Comp. A&h. 4 (1978) l-9.1 20. (a) O.lll... = i.888... = i8.i:: . . . = i8i.i:; . . . = ... = i8:~~~~~.::: has nine representations. (b) A D-fraction .uius . . . always lies between -l/9 and +71/g. Suppose x has ten or more D-decimal representations. Then for sufficiently large k, 10kz has ten representations that differ to the left of the decimal point: 10kx = n1 +fl = . . . = nio + fro where each fj is a D-fraction. By uniqueness of integer representations, the n3 are distinct, say ni < . . . < nls, hence nlo -ni 2 9; but this implies fi -fl0 2 9 > 71/9 -(-l/9), a contradiction. (c) Any number of the form O.uiu2 . , where each uj is -1 or 8, equals i.u;u , . . . where u: = u3 + 9 (and it even has six more representations i8.u; u , . , etc.). 21. We can convert to such a representation by using a method like that suggested in the test for converting to balanced ternary. In contrast to the systems of exercise 20, zero can be represented in infinitely many ways, all obtained from f + c,, 1(-41) . 10wk (or from the negative of this representation) by multiplying it by a power of ten. The representations of unity are 11-4, 4 + 4, 5 -3$-f, 5 - 41-t f, 50-45-333-4, 50-45-441+$, etc., where &a = (&4$)(10-l + 10Y2 + …). [AIUiVf57 (1950) 90-93.1 22. Given some approximation b, . . . blbo with error COckcn bklOk -z > 10Ft for t > 0, we will show how to reduce the error by approximately 10et. (The process can be started by finding a suitable co < k < n bklOk > Z; then a finite number of reductions of this type will make the error less than t.) Simply choose m > n so large that the decimal representation of -lOma has a one in position 10Pt and no ones in positions 10-t+l. 10-t+2. . . 10 . Then 10mcw + fa suitable sum of nowers of 10 between 10 and 1On) + ~o

Fig. A-6. Fundamental region for quater-imaginary numbers. 13. (1.909090.. .)–10 = (0.090909.. .)-IO = A. 14. 11321 1; 1;; 11321 2 11321 11202 12123 11321 11321 010311201 [9 -4Oi] 15. [-g, &I, and the rectangle shown in Fig. A-6. 16. It is tempting to try to do this in a very simple way, by using the rule 2 = (1100),-i to take care of carries; but that leads to a nonterminating method if, for example, we try to add 1 to (11101),-i = -1. The following solution does the job by providing four related algorithms (namely for adding or subtracting 1 or i). If a is a string of zeros and ones, let cP be a string of zeros and ones such that (ap)z-i = (cx)~-~ + 1; and let (Y-~, a&, a-& be defined similarly, with -1, +i, and 4 respectively in place of +l. Then (cxO)P = al; (azl)p = CXQXO. (aO)Q = curl; (d)Q = a-QO. (crxo)-p = a-Q21; (al)-’= a(). @0)-Q =aQl; (al)-& = cpo. Here x stands for either 0 or 1, and the strings are extended on the left with zeros if necessary. The processes will clearly always terminate. Hence every number of the form a + bi with a and b integers is representable in the i -1 system. 17. No (in spite of exercise 28); the number -1 cannot be so represented. This can be proved by constructing a set S as in Fig. 1. We do have the representations 4 = (0.1111.. .)I+%, i = (100.1111.. .)I+%. 18. Let SO be the set of points (alasa5a4asa2a1~0)~-ll where each ak is 0 or 1. (Thus, SO is given by the 256 interior dots shown in Fig. 1, if that picture is multiplied by 16.) We first show that S is closed: If yi, ys, is an infinite subset of S, we have yn = c,,, -ank16-k, where each a& is in SO. Construct a tree whose nodes are (Gtl,.. . , anr), for 1 5 r 5 n, and let a node of this tree be an ancestor of another

562 ANSWERSTOEXERCISES 4.1 SECTION 4.1 1. 1010, 1011, 1000, . . . , 11000, 11001, 11110. 2. (a) -110001, -11.001001001001.. . , 11.0010010000111111.. . . (b) 11010011, 1101.001011001011.. . , 111.011001000100000.. . (c) iiiii, io.oiioiioiioii . . . . io.oiiiiiii… . (d) -9.4, -. . .7582417582413, . . .562951413. 3. (1010113.2)~,. 4. (a) Between rA and rX. (b) The remainder in rX has radix point between bytes 3 and 4; the quotient in rA has radix point one byte to the right of the least significant portion of the register. 5. It has been subtracted from 999. . .9 = lop -1, instead of from 1000. . . 0 = lop. 6. (a,c) 2p-1 -1, -(2p- -1); (b) 2p- -1, -2p-1. 7. A ten s complement representation for a negative number z can be obtained by considering 10n + z (where n is large enough for this to be positive) and extending it on the left with infinitely many nines. The nines complement representation can be obtained in the usual manner. (These two representations are equal for nonterminating decimals, otherwise the nines complement representation has the form . (a)99999. . . while the ten s complement representation has the form (a + 1)OOOO.. . .) The representations may be considered sensible if we regard the value of the infinite sum N = 9 + 90 + 900 + 9000 + . . as -1, since N -10N = 9. See also exercise 31, which considers padic number systems. The latter agree with the p s complement notations considered here, for numbers whose radix-p repre- sentation is terminating, but there is no simple relation between the field of padic numbers and the field of real numbers. 8. c, a,bj = ~,(ak,+kPlbk- +. . . + akj)bk3. 9. A BAD ADOBE FACADE FADED. [Note: Other possible number sentences would be DO A DEED A DECADE; A CAD FED A BABE BEEF, COCOA, COFFEE; BOB FACED A DEADDODO.] , a3,a2, al, a0; a-l, a-2, . . . 1 [ ,AB,Az,A~,Ao;A-1,A-z, . . if bs,bz,bl,bo; b-1, b-2 ,… = :::,BJ,B2,B1,Bo;B-1,B-2 ,… 1 akJ+l-lf ;:J+l-2j.. j ak, B3 = bk )+1-l .bk, , 3tl-2,…,bk3 1 where (kc) is any infinite sequence of integers with k,+l > k,. 11. (The following algorithm works both for addition or subtraction, depending on whether the plus or minus sign is chosen.) Start by setting k t an+1 + an+2 + bntl t b,+z + 0; then for m = 0, 1, , n + 2 do the following: Set cm t a, & b, + k; then if cm 2 2, set k + -1 and cm + cm -2; otherwise if cm < 0, set k + 1 and cm + cm + 2; otherwise (i.e., if 0 2 cm 2 l), set k e 0. 12. (a) Subtract *(. . . asOa10)-2 from *(. aJOazOao)-2 in the negabinary system. (See also exercise 7.1-18 for a trickier solution that uses full-word logical operations.) (b) Subtract (. . . b30b10)2 from (. . . b40bzObo)z in the binary system.

3.6 ANSWERSTOEXERCISES 561 36. Let b and k be arbitrary but fixed integers greater than 1. Let Y, = LbU,]. An arbitrary infinite subsequence (&) = (Ysn)R determined by algorithms S and R (as in the proof of Theorem M) corresponds in a straightforward but notationally hopeless manner to algorithms S and R that inspect Xt, Xt+l, . . . , Xt+, and/or select Xt, X t+1, . . . , Xt+mln(k–l,s) of (Xn) if and only if S and R inspect and/or select Y,, where us = (0.X,X,+.1 . . . X,+t,)z. Algorithms S and R determine an infinite l-distributed subsequence of (Xn) and in fact (as in exercise 32) this subsequence is co-distributed so it is (k, 1)-distributed. Hence we find that &(Z, = u) and Pr(2, = a) differ from l/b by less than 1/2k. [The result of this exercise is true if R6 is replaced consistently by R4 or R5 ; but it is false if Rl is used, since X(-) might be identically zero.] 2 37. For 7~ 2 2 replace U,2 by ~(U,Z + &), where 6, = 0 or 1 according as the set {Ucn–lj~+l,. , Un~~l} contains an even or odd number of elements less than 4. [Advances in Math. 14 (1974), 333-334.1 39. See Acta Arithmetica 21 (1972), 45-50. The best possible value of c is unknown. 40. If every one-digit change to a random table yields a random table, all tables are random (or none are). If we don t allow degrees of randomness, the answer must therefore be, Not always. SECTION 3.6 l.RANDI STJ 9F Store exit location. STA 8F Store value of Ic. LDA XFtAND rA+-X. MUL 7F rAX + ax. INCX 1009 rX + (ax + c) mod m. JOV *+I Ensure that overflow is off. SLAX 5 rA t (ax + c) mod m. STA XRAND Store X. MUL 8F rA + [kX/mJ. INCA 1 Add 1, so that 1 5 Y 5 Ic. 9H JMP + Return. XFUND CON 1 Value of X; X0 = 1. 8H CON 0 Temp storage of k. 7H CON 3141592621 The multiplier a. 1 2. Putting a random number generator into a program makes the results essentially unpredictable to the programmer. If the behavior of the machine on each problem were known in advance, few programs would ever be written. As Turing has said, the actions of a computer quite often do surprise its programmer, especially when a program is being debugged. So the world had better watch out. 7. In fact, you only need the a-bit values [Xn/216j mod 4; see D. E. Knuth, De- ciphering a linear congruential encryption, to appear. See also J. Reeds, Cryptologia 1 (1977), 20-26, 3 (1979), 83-95, for solutions to related problems.

560 ANSWERS TO EXERCISES 3.5 Fig. A-5. Directed graph for the construction in exercise 30. the cyclic path are numbered from 1 to 32, and the cyclic sequence is (00001000110010101001101110111110)(00001.. .). Note that Pr(Xz, = 0) = fi in th is sequence. The sequence is clearly (2lc)-distributed, since each (2/c)-tuple 2122.. . Z2k occurs 1 + f(zl,. . . ,zz~) + 1 - f(zl,. . . ,zz~) = 2 times in the cycle. The fact that Pr(X2, = 0) has the desired value comes from the fact that the maximum value on the right-hand side in the proof of the preceding exercise has been achieved by this construction. 31. Use Algorithm W with rule RI selecting the entire sequence. [For a generalization of this type of nonrandom behavior in R5-sequences, see Jean Ville, l&de Critique de Is notion de Collectif (Paris, 1939), 55-62. Perhaps R6 is also too weak, from this standpoint.] 32. If R, R are computable subsequence rules, so is R = RR defined by the following functions: fc(zo, . . . , ~~-1) = 1 iff R defines the subsequence x71, . . . , zTk of 20, . . . , ~~-1, where k 2 0 and 0 5 rl < . . . < rk < n and &(z~~, . . . , s7,) = 1. Now (Xn)R R is ((Xn)R)R . The result follows immediately. 33. Given E > 0, find NO such that N > NO implies that both Iv,(N)/N -pi < E and Iv,(N)/N--pi < E. Then find Nl such that N > Nl implies that tN is TM or S,U for some M > NO. Now N > Nl implies that 34. For example, if the binary representation of t is (1 Obh2 10 1 1 Oa2 1 . . . 1 Oak)z, where Oa stands for a sequence of a consecutive zeros, let the rule Rt accept U, if and only if [bU,+kj = al, . . . , [bU,-,J = ak. 35. Let a0 = SO and am+1 = max{ Sk 1 0 2 k < 2am }. Construct a subsequence rule that selects element X, if and only if n = Sk for some Ic < 2am, when n is in the range am 5 n < a,+l. Then limm+oo v(a,)/a, = 4.

3.5 ANSWERS TO EXERCISES 559 29. If 5 = x1×2.. xt is any binary number, we can consider the number v:(n) of times X, Xp-tt+l = x, where 1 5 p 5 n and p is even. Similarly, let y:(n) count the number of times when p is odd. Let v:(n) + v:(n) = v=(n). Now where the V S in these summations have 21c subscripts, 2k -1 of which are asterisks (meaning that they are being summed over-each sum is taken over 22k-1 combinations of zeros and ones), and where ~5 denotes approximate equality (except for an error of at most 2k due to end conditions). Therefore we find that where x = x1 x2k contains r(x) zeros in odd positions and s(x) zeros in even positions. By (2lc)-distribution, the parenthesized quantity tends to k(22k- )/22k = k/2. The re- maining sum is clearly a maximum if y?(n) = u,(n) when T(Z) > s(x), and v:(n) = 0 when r(x) < s(x). So the maximum of the right-hand side becomes O; n n 2n -1 min(r, s) = 2n22n-2 -n au r s ( n > r,s 30. Let f(xl, x2,. , x2k) = sign(xl -x2 +x3 -x4 f. -xzk). Construct a directed graph with 2 nodes labeled (E; x1, . , x2&-1) and (0; xl, , x2&1), where each x is either 0 or 1. Let there be 1 +f(xl, x2,. , xzk) directed arcs from (E; x1, , xZk-1) to (0; x2,. f , x2k), and 1 -f(x1, x2,. . , x2k) directed arcs leading from (0; xl,. , x2&1) to (E; x2,. , x2k). We find that each node has the same number of arcs leading into it as there are leading out; for example, (E; x1,. , x2k-l) has 1 -f(0, x1, , x2k-1) + l-f(l,xl,. ..,52k–1) leading in and l+f(xl,. .,x2k-l,O)+l+f(x1,. . . ,x2k-l,1) leading out, and f(x, xl,. . . , x2&1) = -f(xl, . , x2k-1, x). Drop all nodes that have no paths leading either in or out, i.e., (E; x1,. , xZk-1) if f(0, xl,. . , x2k-1) = +I, or (QXl,.. , XZk-1) if f(l, xl,. . . , x2&1) = -1. The resulting directed graph is seen to be connected, since we can get from any node to (E; 1, 0, 1, 0, ,I) and from this to any desired node. By Theorem 2.3.4.2G, there is a cyclic path traversing each arc; this path has length azk+ , and we may assume that it starts at node (E; 0,. ,O). Construct a cyclic sequence with X1 = … = X2&1 = 0, and Xn+2k-l = x2k if the nth arc of the path is from (E; x1,. , xzk-1) to (0; x2,. , x2k) or from (0; x1,. ,x2&-1) to (E; x2,. . . ,zz~). For example, the graph for k = 2 is shown in Fig. A-5; the arcs of

558 ANSWERS TO EXERCISES 3.5 16. (Solution by R. P. Stanley.) Whenever the subsequence S = (b -l), (b - 2), . . . , 1, 0, 0, 1, . , (b -2), (b -1) appears, a coupon set must end at the right of S, since some coupon set is completed in the first half of S. We now proceed to calculate the probability that a coupon set begins at position n by manipulating the probabilities that the last prior appearance of S ends at position 72 - 1, n -2, etc., as in exercise 15. 18. Proceed as in the proof of Theorem A to calculate fi and Pr. 19. (Solution by T. Herzog.) Yes; e.g., the sequence (Uln,s~) when (Un) satisfies R4 (or even its weaker version), cf. exercise 33. 21. Pr(& E Ml,. . . , i&+&l E Mk) = p(Ml). . .p(Mk), for all MI, , Mk E ht. 22. If the sequence is k-distributed, the limit is zero by integration and Theorem B. Conversely, note that if f(zl, . . , zk) has an absolutely convergent Fourier series f(X1,. . . , xk) = U(Cl, , Ck) eXp(%i(clzl + + ckxk)), c -co