196 ARITHMETIC 4.1 27. [M.Zl] Show that every
196 ARITHMETIC 4.1 27. [M.Zl] Show that every nonzero integer has a unique reversing binary representa- tion 2-3 -2el + . + (-1)9, where es < el < .. < et. b 28. [M24] Show that every nonzero complex number of the form a + bi where a and b are integers has a unique revolving binary representation (1 + i) + i(l + i) -(1 + i) -i(1 + i) + . . + ?(l + i) , where es < el < ... < et. (Cf. exercise 27.) 29. [M35] (N. G. de Bruijn.) Let SO, S1, Ss, be sets of nonnegative integers; we will say that the collection {SO, ,571, Sz, . } has Property B if every nonnegative integer n can be written in the form n = so + Sl + s2 + . , s3 E s,, in exactly one way. (Property B implies that 0 E S, for all j, since n = 0 can only be represented as 0 + 0 + 0 + . . . .) Any mixed-radix number system with radices bo, bl, bz, . provides an example of a collection of sets satisfying Property B, if we let S, = (0, B3, , (b, -l)B,}, where B, = bobI . . b,-1; here the representation of n = so + Sl + s2 + '.. corresponds in an obvious manner to its mixed-radix repre- sentation (9). Furthermore, if the collection {SO, Si, Sz, . } has Property B, and if Ao, AI, A2, . . is any partition of the nonnegative integers (so that we have A0 U A1 U A2 U . = (0, 1,2,. . } and A, n A3 = 0 for i # j; some A3 s may be empty), then the collapsed collection {TO, ZJ, 7 2, . } also has Property B, where ? , is the set of all sums x2eA s, taken over all possible choices of si E S,. Prove that any collection {TO, T1, 7 2, , } that satisfies Property B may be obtained by collapsing some collection {SO, S1 , S2, . . } that corresponds to a mixed-radix number system. 30. [A4391 (N. G. de Bruijn.) The radix-(-2) number system shows us that every integer (positive, negative, or zero) has a unique representation of the form (-2)el + (--2)Q + . . + (--2)Q, el > e2 > f.. > et 2 0, t 2 0. The purpose of this exercise is to explore generalizations of this phenomenon. a) Let bc, bl, b2, . . be a sequence of integers such that every integer n has a unique representation of the form n = beI + be, + . . + b,, , el > e2 > … > et 2 0, t > 0. (Such a sequence (b,) is called a binary basis. ) Show that there is an index j such that b, is odd, but bk is even for all Ic # j. b) Prove that a binary basis (bn) can always be rearranged into the form do, 2di, 4dz, . . . = (2nd,), where each dk is odd. c) If each of do, di, ds, . in (b) is fl, prove that (b,) is a binary basis if and only if there are infinitely many +1 s and infinitely many -1 s. d) Prove that 7, -13. 2, 7 3 2 , -13. 23, . . , 7. 22k, -13. 22k+1, . is a binary basis, and find the representation of n = 1.