вы соотношения Л„+ул = Л„ + р(В„ + В„+л + В„+2Л + • • • + Вп+и-1)х) = An + jpBn

(по модулю р") при j = 1,2,3, Никакие/с последовательных В„ не кратны р; отсюда

немедленно следуют соотношения А(р+) = рА(р) ф А(р+) при е > 2. Необходимо еще доказать, что Л(р") # рА(р), когда р нечетно и е = 1. Положим Вл+п = В„ + рСп и заметим, что Сп+х = Сп (по модулю р), когда п достаточно велико. Тогда Л„+р = An (В„ + (2)Сп) (по модулю р), и доказательство окончено.

Историю решения этой задачи можно найти в работе Моргана Варда (Morgan Ward, Trans. Amer. Math. Soc. 35 (1933), 600-628); см. также работу Д. В. Робинсона (D. W. Robinson, AJVfJVf 73 (1966), 619-621).

12. Длина периода по модулю 2 не может быть больше 4. Длина периода по модулю 2" не может быть больше удвоенной длины максимального периода mod 2. Это следует из предыдущего упражнения. Поэтому длина максимального возможного периода равна 2". Она достигается, например, в тривиальном случае при а = 0, Ь = с = 1.

13, 14. Очевидно, что Zn+x = Zn, поэтому А является делителем А. Пусть наименьшее общее кратное А и Ai равно Al, а Аз определяется аналогично. Справедливы соотношения Хп + Yn = Zn = Zn+x = Хп +Yn+y , поэтому Al кратно Лз. Аналогично можно показать, что Лг кратно Ai. Это дает желаемый результат. (Он является "наилучшим из возможных" в том смысле, что последовательности, для которых А = Ао, могут быть построены так же, как последовательности, для которых А = А.)

15. Алгоритм М генерирует {Xn+k,Yn) на шаге Ml и дает на выходе Z„ = А„+к-,„ на шаге МЗ для всех достаточно больших п. Таким образом, (Zn) имеет период длиной А, где А - наименьшее положительное целое число, такое, что Хп+к-д„ = Хп+х+к-д,., для всех больших п. Так как А кратно Ai и Аг, отсюда следует, что А является делителем А. (Это заметил Алан Дж. Вотерман (Alan G. Waterman).)

Также справедливы соотношения п + к - qn = п + X + к - qn+x (по модулю Ai) для всех больших п из-за различия Хп. Предположение об ограниченности (qn) обеспечивает равенство qn+x = qn + с для всех больших п, где с = А (по модулю Ai) и с < Ai. Но с должно равняться О, так как (д„) ограничено. Значит, А = О (по модулю Ai) и д„+л - qn для всех больших п. Отсюда следует, что А кратно Аг и Ai, поэтому А = А.

Замечание. Из ответа к упр. 3.2.1.2-4 следует, что, если (У„) - линейная конгруэнтная последовательность максимального периода по модулю т = 2, длина периода Аг будет не больше 2", когда к - степень 2.

16. Существует несколько методов доказательства.

(1) Использование теории конечных полей. Рассмотрим поле, содержащее 2* элементов. Пусть f удовлетворяет соотношению = oif*" + + ak- Пусть /(bif*" -I- • • • -I- bk) = bk, где каждое bj равно нулю или единице, - линейная функция. Если слово X в порождающем алгоритме имеет вид (6162 • • • Ьк)2 до выполнения (10) и если bi~ -I- • • -I- bk° = f", то слово X после выполнения (10) будет иметь вид Значит, последовательность будет иметь вид f(C), f(C), /(Г+), и /(Г+*) = /(Г?) = /(air+*-i + .. • + акС) = аг!(е-"-) + • • • + а./(Г )•

(2) Использование грубой силы или элементарной изобретательности. Рассмотрим последовательность Xnj, п > О, 1 < j < к, удовлетворяющую соотношениям

X(n+i)j = Xnu+i) + ajXni, l<j<k; A(„+i)fc = akXni (no модулю 2).

Необходимо показать, что Хпк = aiX(n-\)k + + акХ(п-к)к для п > к. В самом деле,

получаем, что Xnj = a\X(n-\)j +----1- akX(n-k)j, когда I < j < к < п. Это очевидно для

3 = 1, так как A„i = aiA(„ i)i -I- А(„ 1)г = aiA(„ i)i -I- а2А(„ г)2 + А(„ 2)з и т. д. Для

j > 1 по индукции получим

Xnj = Х(„+1)у 1) - Qj-lXnl

= "Y aiA(„+j i)(j i)-aj i a,A"(„ i)i

= at(A(„+i i)(j i) - aj iA(„ i)i) i<»<*

= aiX(n-i)j H-----l-aj,A(„ A.)j.

Доказательство не зависит от того, как будут рассматриваться операции: по модулю 2 либо по модулю, равному любому простому числу.

17. (а) Когда последовательность закончится, (к - 1)-мерная строка (An+i,..., An+fc i) появится (m + 1)-й раз. Для данной {к - 1)-мерной строки (Ar+i,..., Ar+*:-i) существует только m предшественников Аг, поэтому один из них должен появиться при г = 0. (Ь) Так как строка размерности (/с - 1) (О,..., 0) встречается (т -I-1) раз, к&ждый возможный предшественник появится обязательно. Поэтому строка размерности к (ai,0,... ,0) появляется для всех oi, О < ai < m. Пусть 1 < s < /с, и предположим, что доказано, что все строки размерности к (oi,.,., Os, О,..., 0) появились в последовательности при Os ф 0. По построению эта строка размерности к (oi,..., а, О,..., О, у) не .может появиться раньше строки (ai,..., , О,..., О, у) для 1 < у < т. Следовательно, строка размерности (А; - 1) (ai,..., Os, О,..., 0) появилась т раз, и все m возможных предшественников также появились. Это означает, что строка (а, ai,..., а. О,..., 0) появилась для О < а < т. Доказательство завершается по индукции.

Результат также следует из теоремы 2.3.4.2D, если использовать ориентированные графы из упр. 2.3.4.2-23. Множество дуг из (xi,... ,Xj,0,... ,0) в (жг,... 0,0,... ,0), где Xj ф v. \ < j <к, образуют ориентированное поддерево, четко связанное с десятичными обозначениями Девея.

18. Третий из старших двоичных разрядов f/n+i полностью определяется первым и третьим двоичными разрядами f/„. Поэтому появляются только 32 из 64 возможных пар ([8f/nJ, [8t/n+iJ). {Замечание. Если бы использовались, скажем, 11-разрядные числа f/„ = (.Aii„Aiin+i ... Aiin+io)2, то последовательность была бы удовлетворительной для многих случаев применения. Если другие, имеющие более одного двоичного разряда, постоянные появятся в регистре А, то последовательность будет удовлетворять обобщенному спектральному критерию. (См. упр. 3.3.4-24; необходимо проверять ut при t = 36, 37, 38, ]

21. [J. London Matb. Soc. 21 (1946), 169-172.] Любая последовательность с длиной периода т* - 1 без к последовательных нулей приводит к образованию последовательности с длиной периода т*, если вставить нули в подходящие места, как в упр. 7. Обратно, можно начинать с последовательности с длиной периода и удалять подходящие нули из периода, чтобы сформировать последовательность другого типа. Назовем эти (т, А;)-последовательности последовательностями типа А и В. Предположения обеспечивают существование (р, А;)-последовательностей типа А для всех простых чисел р и всех к>1. Таким образом, существуют последовательности (р, А) типа В для всех таких р и к.

Чтобы получить последовательность (р, к) типа В, возьмем е = qr, где q - степень р, а г не кратно р. Начнем с (р, дгА;)-последовательности типа А, а именно - с Ао, Al, Хг,...; тогда с помощью системы счисления с основанием р сгруппированные цифры (Хо ... X, i)p, (X, ... A29-i)p,... образуют последовательность (р, гк) типа А, так как q и р - 1 - взаимно простые числа и последовательность имеет период длиной р - 1. Это приводит к получению (р, гА;)-последовательности (Уп) типа В, а (УоУх.. .Уг-1)рч, (УгУг+1.. V2r-i)p«, • • являются (р"", А;)-последовательностями типа В. Доказывается аналогично, так как г и р* - взаимно простые числа.

Чтобы получить (m, А;)-последовательность типа В для произвольного т, можно объединить (р, А;)-последовательности для каждой степени простого множителя т, используя китайскую теорему об остатках, но существует более простой метод. Пусть (Х„) - это (г, А;)-последовательность типа В и пусть (F„) - (s, А;)-последовательность типа В, где г и S - взаимно простые числа. Тогда {sXn + Yn) является (rs, А;)-последовательностью типа В.

Простая равномерная конструкция, которая производит (2, /г)-последовательности для произвольного к, была открыта А. Лемпелем (А. Lempel, IEEE Trans. С-19 (1970), 1204-1209).

22. С помощью китайской теоремы об остатках можно найти константы ai,...,ak, имеющие желаемые вычеты по модулю, равно.му каждому простому делителю т. Если т = pip2 .. - Pt, длина периода равна lcm(pi - 1, ..., р* - 1). В самом деле, можно получить приемлемо длинный период для произвольного т (необязательно свободного от квадратов), как показано в упр. 11.

23. Вычитание может происходить быстрее суммирования (см. упр. 3.2.1.1-5); длина периода все еще равна 2~(2** - 1) согласно упр. 30. Р. Брент (R. Brent) отметил, что при использовании чисел с плавающей точкой вычисления можно произвести точно в [О.. 1) (см. упр. 3.6-11).

24. Обратите последовательность. Другими словами, если Zn - Y-n, то Zn = {Zn-k+i - Zn-k) mod 2 = (Zn-k+i + Zn-k) mod 2.

25. Эта идея поможет избежать больщинства затрат времени на обращение к программам. Например, предположим, что программа А вызывается командой JMP RANDM, где

RANDM STJ IF

LDA Y,6

ENT6 55 IH JMP ♦

Программа A.

Цена использования таких случайных чисел составляет 14 -Ь единиц времени. Но предположим, что мы обращаемся не к этой программе, а к программе получения случайных чисел RNGEN: DEC6 1; J6Z RNGEN;LDA У.б.

RNGEN STJ IF ENT6 31

"eNTS 24 LDA Y,6

LDA Y+31,6 ADD Y+24,6

ADD Y,6 STA Y.6

STA Y+31,6 DEC6 1

DEC6 1 J6P ♦-4

J6P ♦-4 ENT6 55

IH JMP * I

Сейчас цена равна всего (12 + )и. [Подобное обращение на языке С используется в Tiie Stanford GrapiiBase (New York: ACM Press, 1994), GB JLIP.] Действительно, во многих случаях предпочтительней генерировать весь массив случайных чисел одновременно. Более того, приведенный выще подход обязателен, когда случайность усиливается методом Лю-щера (Liischer) (см. программы на алгоритмических языках С и FORTRAN в разделе 3.6).

27. Пусть Л = 1кХп/т\.

Лемма. После того как (к + 7к - 2)/2 последовательных значений

Qk+2 ф+1 2 0* ... (А; 1) о