Abyss web server - 530 ANSWERS TO EXERCISES 3.2.2 (al, . ,
530 ANSWERS TO EXERCISES 3.2.2 (al, . , a,, 0,. . . , 0) has appeared m times, and all m possible predecessors appear; this means (a,al,…, a,,0 ,…, 0) appears for 0 5 a < m. The proof is now complete by induction. The result also follows from Theorem 2.3.4.2D, using the directed graph of exercise 2.3.4.2-23; the set of arcs from (~1,. . . , z3, 0, , 0) to (~2, . . . , x3, 0, . . . , 0, 0), where Z~ # 0 and 1 2 j < k, forms an oriented subtree related neatly to Dewey decimal notation. 18. The third-most-significant bit of U,+l is completely determined by the first and third bits of U,, so only 32 of the 64 possible pairs (LSU,], [SV,+,J) occur. (Notes: If we had used, say, 11-bit numbers U, = (.XI~~X~~~+~ . . .Xlln+lO)z, the sequence would be satisfactory for many applications. If another constant appears in A having more one bits, the generalized spectral test might give some indication of its suitability. See exercise 3.3.4-24; we could examine it in dimensions t = 36,37,38, . . .) 21. [J. London Math. Sot. 21 (1946), 169-172.1 Any sequence of period length mk -1 with no k consecutive zeros leads to a sequence of period length mk by inserting a zero in the appropriate place, as in exercise 7; conversely, we can start with a sequence of period length mk and delete an appropriate zero from the period, to form a sequence of the other type. Let us call these (m, k) sequences of types A and B. The hypothesis assures us of the existence of (p, k) sequences of type A, for all primes p and all k 2 1; hence we have (p, k) sequences of type B for all such p and k. To get a (p , k) sequence of type B, let e = qr, where q is a power of p and r is not a multiple of p. Start with a (p, qrk) sequence of type A, namely X0, X1, X2, . ; then (using the p-ary number system) the grouped digits (X0.. . Xq–l)p, (X, . . . XZ~–~)~, . . . form a (pq, rk) sequence of type A, since q is relatively prime to pqrk -1 and the sequence therefore has a period length of pqrk -1. This leads to a (pq,rk) sequence (Y,) of type B; and (YoK . . Y7–l)pq, (Y,Y,+1 . . Y27–l)p4, . . . is a (pqr, k) sequence of type B by a similar argument, since r is relatively prime to pqk. To get an (m, k) sequence of type B for arbitrary m, we can combine (p , k) sequences for each of the prime power factors of m using the Chinese remainder theorem; but a simpler method is available. Let (Xn) be an (r, k) sequence of type B, and let (Y%) be an (s, k) sequence of type B, where r and s are relatively prime; then (sX, + Y,) is an (TS, k) sequence of type B. A simple, uniform construction that yields (2, k) sequences for arbitrary k has been discovered by A. Lempel [IEEE Bans. C-19 (1970), 1204-12091. 22. By the Chinese remainder theorem, we can find constants al, . . . , ak having desired residues mod each prime divisor of m. If m = plp2.. .pt, the period length will be lcm(pf -1, . . . , p: -1). In fact, we can achieve reasonably long periods for arbitrary m (not necessarily squarefree), as shown in exercise 11. 23. Period length at least 255 -1; possibly faster than (7), see exercise 3.2.1.1-5. Furthermore, R. Brent has pointed out that the calculations can be done exactly on floating point numbers in [ 0,l). 24. Run the sequence backwards. In other words, if 2, = Y-, we have 2, = (2%~m+k + zn-m) mod 2. 25. This actually would be slower and more complicated, unless it can be used to save subroutine-calling overhead in high-level languages. (See the FORTRAN program in Section 3.6.)