► 9. [М24] (P. P. Ковэю (R. R. Coveyou).) Используйте результаты упр. 8 для доказательства-того, что длина периода модифицированного метода средин квадратов (4) равна

2е-2

10. [М29] Покажите, что если Ао и Al - такие простые числа, что по крайней мере одно из них нечетно, и га = 2", то период последовательности Фибоначчи (5) равен 3 • 2~.

11. [М36] Назначение этого упражнения состоит в анализе определенных свойств последовательности целых чисел, удовлетворяющих рекуррентному соотнощению

Хп = aiXni-\-----i-aXn-k, п>к.

Если можно вычислить длину периода данной последовательности по модулю т = р, когда р - простое число, то длина периода этой последовательности по отнощению к произвольному модулю т равна наименьшему общему кратному длин периодов последовательностей, для которых модуль равен степеням простых сомножителей т.

a) Если f(z), a{z), b{z) - это полиномы с целыми коэффициентами, то запишем a{z) = b{z) по модулям f{z) и т, если a(z) = h{z) + f{z)u{z) + mv{z) для некоторых полиномов u{z) и v(z) с целыми коэффициентами. Докажите, что имеет место следующее утверждение, когда /(0) = 1 и > 2: если 2 = 1 по модулям f{z) и и 1 по модулям /(г) и р+, то = 1 по модулям /(г) и р+ и г 1 по модулям f{z) и р+2.

b) Пусть /(г) = 1 - aiz-----a/tz*" и

G{z) = l (z) = Ао + Aiz + Лгг + • • •.

Пусть Л(т) обозначает длину периода {An mod га). Докажите, что Л(т) - наименьшее положительное Л, такое, что = 1 по модулям f{z) и т.

c) Дано: р - простое число, р > 2 и Л(р) ф Л(p""). Докажите, что Х{р) = рЛ(р) для всех г > 0. (Таким образом, чтобы найти длину периода последовательности (Л„mod2°), можно подсчитывать Л(4), Л(8), Л(16), пока не будет найдено наименьшее е > 3, такое, что Л(2) ф Л(4). Тогда длина периода будет определена по mod 2 для всех е. В упр. 4.6.3-26 объясняется, как вычислить Хп для больших п за O(logn) операций.)

d) Покажите, что любая последовательность целых чисел, которая удовлетворяет рекуррентному соотношению, сформулированному в начале этого упражнения, имеет производящую функцию 9{z)lf{z) для некоторого полинома g{z) с целыми коэффициентами.

e) Дано, что полиномы f{z) и g{z) в п. (d) взаимно просты по модулю р (см. раздел 4.6.1). Докажите, что последовательность (АГ„ modp) имеет ту же длину периода, что и специальная последовательность {An modp) в (b). (Нельзя увеличить длину периода путем выбора любых Хо,... ,Хк-\, так как общая последовательность является линейной комбинацией "сдвигов" специальной последовательности.) [Указание. Из

упр. 4.6.2-22 (лемма Хенселя) следует, что существуют полиномы, такие, что а(г)/(2;)--b{z)g{z) = 1 (по модулю р).] ► 12. [М28] Найдите целые числа Хо, Xi, а, 6 и с, такие, что последовательность

Хп+1 = {аХп -I- 6Х„ 1 + с) mod 2% п > 1,

имеет Самый длинный период среди всех последовательностей этого типа. [Указание. Можно показать, что Хп+2 = {{а + l)X„+i + {Ъ - в)Х„ - 6Xn-i) mod2; см. упр. И, (с).] 13. [М20] Пусть (Хп) и (Fn) - последовательности целых чисел по mod га с периодами длиной Ai и Л2. Объединим их, положив Zn = {Хп + Уп) modm. Покажите, что если Ai и Л2 - взаимно простые числа, то последовательность (Zn) имеет период длиной А1Л2.

14. [М24] Пусть Xn,Y„, Zn, Xi а A2 определены так же, как в предыдущем упражнении. Предположим, что разложение Ai на простые множители имеет вид 22 3*5"... и аналогично А2 = 235 .... Пусть др = (тах(ер, /р), если Ср ф fp, в других случаях - 0) и пусть Ао = 2*3*5*.... Покажите, что длина периода А последовательности (Zn) кратна Ао и является делителем А = lcm(Ai, А2). В частности. А = А, если (ср ф fp или ер = fp = 0) для каждого простого р.

15. [М27] Пусть последовательность (Хп) в алгоритме М имеет длину периода Ai и все элементы в этом периоде различны. Пусть qn = тт{г г > О и \ кУп-т/т} = [кУп/тп\}. Предположим, что qn < Ai для всех п > по и что последовательность (qn) имеет длину периода А2. Пусть А - наименьшее общее кратное Ai и А2. Докажите, что последовательность на выходе (Zn), полученная с помощью алгоритма М, имеет длину периода А.

► 16. [М28] Пусть в методе (10) СОДЕРЖИМОЕ (А) равно (0102 ... ак)2 в бинарной записи. Покажите, что последовательность, генерируемая младшими разрядами Хо, Xi, ..., удовлетворяет соотношению

Хп = (aiXn-i -1-а2Хп-2 -I-----i-akXn-k) mod 2.

[Это можно рассматривать как другой способ определения последовательности, хотя связь между данным соотношением и программой (10), на первый взгляд, не заметна!]

17. [МЗЗ] (М. X. Мартин (М. Н. Martin), 1934.) Пусть тик - положительные числа и пусть Xi = Х2 = = Хк - 0. Для всех п > О положим Хп+к равным наибольшему неотрицательному числу у < т, такому, что /с-мерная строка (Xn+i,... ,Xn+k-i,y) еще не появилась в последовательности. Другими словами, (Xn+i, , Xn+k-i,y) должна отличаться от (Хг+1,... ,Хг+к) для О < г < п. При этом каждая возможная /с-мерная строка встретится по крайней мере один раз в последовательности. В конце концов процесс закончится, когда будет достигнуто такое значение п, при котором строка (X„+i,..., Xn+k-i,y) уже появлялась в последовательности для всех неотрицательных у < т. Например, если m = /с = 3, такой последовательностью будет 00022212202112102012001110100и процесс закончится в этой точке, (а) Докажите, что, когда последовательность закончится, будут выполняться равенства Xn+i = ••• = Xn+k-i - 0. (b) Докажите, что каждая Л-мерная строка элементов [ai,a2,.. • ,ajt), таких, что О < а- < т, появляется в постедова-тельности. Поэтому последовательность окончится при п - т*. [Указание. Докажите, что /с-мерная строка (ai,..., Os, О,..., 0) появляется, когда as ф О, используя индукцию по s\ Заметим, что если сейчас определить /(Хп,... ,Хп+к-\) = Хп+к для 1 < п < т°, полагая Xm+к - 0> то получится функция С максимальным возможным периодом.

18. [М22] Пусть (Х„) - это последовательность двоичных разрядов, генерируемая методом (10), с /с = 35 и СОДЕРЖИМОЕ (А) = (00000000000000000000000000000000101)2.

Пусть Un - бинарная дробь {.XnkXnk+i . Xnk+k-i)2. Покажите, что эта последовательность (Un) не удовлетворяет сериальному критерию пар (раздел 3.3.2В), когда d = 8.

19. [M4I] Для каждого простого числар из первого столбца табл. 2 раздела 4.5.4 найдите подходящие константы ai и 02, как предлагается в разделе, чтобы длина периода (8) при к = 2 равнялась р - 1. (Например, см. рекуррентное соотношение 3.3.4-(39).)

20. IM40] Вычислите подходящие константы для использования в качестве содержимого регистра А (СОДЕРЖИМОЕ(А)) в методе (10), имеющие приблизительно то же количество нулей, что и константы для 2 < А; < 64.

21. [М35] (Д. Рис (D. Rees).) В разделе объясняется, как найти функции /, такие, что последовательность (11) имеет длину периода тп* - 1, если т - простое число и не все Хо,...,Х* 1 равны нулю. Покажите, что такие функции могут быть изменены для получения последовательности наподобие (И) с длиной периода т* для всех целых т.

[Указание. Рассмотрите лемму 3.2.1.2Q, трюк из упр. 7 и последовательность вида {рХ2п +

X2n+l).]

► 22. [М24] В разделе нет обширных обсуждений способов расширения линейной последовательности (8) до случая, когда т является простым числом. Докажите, что достаточно длинный период может быть получен, когда т "свободно от квадратов", т. е. является произведением различных простых чисел. (Из табл. 3.2.1.1-1 ясно, что т = w ± 1 часто удовлетворяет этим предположениям. Многие из результатов, приведенных в настоящем разделе, могут поэтому быть распространены на случай, который в некоторой степени более удобен для вычислений.)

► 23. [20] Рассмотрите последовательность Хп = {Хп-55 - Хп-24) mod тп как альтернативу последовательности (7).

24. [М20] Пусть О < I < к. Докажите, что последовательность двоичных разрядов, определенная рекуррентным соотношением Хп = {Xn-k+i -Ь Xn-i) mod 2, имеет длину периода 2*-1 всякий раз, когда такой же период имеет последовательность, определенная соотношением Yn = {Yn-i + Yn-k) mod 2.

25. [26] Рассмотрите альтернативу для программы А, состоящую в том, что все 55 входов в таблице Y-B заменяются 55 раз требуемыми случайными числами.

26. [М48] (Дж. Ф. Рейзер (J. F. Reiser).) Пусть р - простое число и к - положительное число. Пусть заданы целые числа ai,... ,ак и xi,... ,хк, пусть Ха - период последовательности (Хп), заданной рекуррентным соотношением

Ап = Хп modp", 0<п<к; Х„ = (aiX„ i------h aA:Xn-fc) modp", п>к,

и пусть Na равно числу нулей, которые встречаются в периоде (числу индексов j, таких, что < j < + Хо, и Xj = 0). Докажите или опровергните следующее утверждение: существует константа с (зависящая, возможно, от р, к и ai,...,ak), такая, что Na <

[Замечание. Рейзер доказал, что если рекуррентная последовательность имеет максимальную длину периода по модулю р (т. е. если Ai = р* - 1) и если утверждение имеет место, то /с-мерное расхождение (Хп) будет равно 0(a*p~°v~) при а оо. Таким образом, аддитивный генератор, подобный (7), был бы распределен в 55 измерениях, когда т = 2 и рассматривается полный период. (См. раздел 3.3.4, в котором определено понятие расхождения в к измерениях.) Утверждение является слабым условием, если (Хп) принимает каждое значение примерно одинаково часто и если Ха = р°"(р* - 1). Величина Na « (р* - 1)/р не увеличивается, вообще говоря, когда а возрастает. Рейзер проверил это утверждение для к = 3. С другой стороны, он показал, что можно найти необычайно плохие (зависящие от а) начальные значения xi,.. .,Хк, такие, что N2a > р", обеспечивающие Ха = р"~Чр ~ l)i к >3, а достаточно большое.]

27. [МЗО] Предположим, что алгоритм В применяется к последовательности (Хп) с длиной* периода А, где А /с. Покажите, что для фиксированного к и всех достаточно больших А последовательность на выходе будет периодичной с той же самой длиной периода А, если (Хп) не является слишком случайной. [Указание. Найдите структуру последовательных значений [кХп/т\, которая обеспечивает "синхронизацию" дальнейшего поведения алгоритма В.]

28. [40] (А. Дж. Вотерман (А. G. Waterman).) Исследуйте линейную конгруэнтную последовательность с т, равным квадрату или кубу длины компьютерного слова, в то время как а и с заданы с обычной точностью.

► 29. [40] Найдите хороший метод вычисления функции f{xi,... ,Хк), определенной последовательностью Мартина (Martin) в упр. 17, если задана только строка (xi,... ,хк) размерности к.