2. Xn+i равно либо Xn-i + А„, либо Xn-i + Хп - т. Если Xn+i < An, то должно быть Хп+1 = Хп-1 +Хп - т; отсюда Xn+i < Xn-i-

3. (а) Подчеркнутые числа - это V[j] после шага МЗ.

Таким образом, потенциал может быть сведен к 1! (См. комментарии, приведенные в ответе к упр. 15.)

(Ь) Подчеркнутые числа - это Vlj] после шага В2.

В этом случае выход значительно лучше входа; он привносит повторяющийся цикл длиной 40 после 46 шагов: 236570 05314 72632 40110 37564 76025 12541 73625 03746 (30175 24061 52317 46203 74531 60425 16753 02647). Можно легко найти цикл, применяя методы из упр. 3.1-7 к приведенной выше таблице до повторяющихся столбцов.

4. Байты младшего порядка многих случайных последовательностей (например, линейная конгруэнтная последовательность с т = длина слова) намного менее случайны, чем байты высокого порядка (см. раздел 3.2.1.1).

5. Эффект рандомизации будет сведен к минимуму, потому что V[j] всегда будет содержать числа из определенного интервала, а именно - j/k < V[j]/m < [j + l)/k. Однако использование подобных подходов вполне допустимо. Можно положить \п - An -1 или выбрать j из An, извлекая некоторые цифры из середины числа, а не из его левой части. Никакое из этих предложений не будет удлинять период, как это делает алгоритм В. (В упр. 27 показано, однако, что алгоритм В необязательно увеличивает длину периода.)

6. Например, если Xn/m < , то Xn+i = 2Хп.

7. (Мантель В. [W. Mantel, Meuw Archief voor Wisknnde (2) 1 (1897), 172-184.]

00. ..01

Последовательность значений X

00.. .01 00...10

10.. .00 CONTENTS(A)

становится такой:

00. ..10

10.. .00 00.. .00 CONTENTS(A)

8. Можно предположить, что Ло = О и m = р", как и при доказательстве теоремы 3.2.1.2А. Сначала предположим, что последовательность имеет длину периода р". Отсюда следует, что период последовательности по модулю имеет длину р для 1 < / < е.

иначе некоторые вычеты по модулю никогда не будут встречаться. Ясно, что с не кратно р; с другой стороны, Хп должно быть кратно р. Если р < 3, то легко доказать необходимость условий (iii) и (iv) методом проб и ошибок, поэтому можно предположить, что р > 5. Если d О (по модулю р), то dx + ах + с = d{x + oi) + ci (по модулю р) для некоторых целых ai и ci и для всех целых х. Эта квадратичная форма принимает одни и те же значения в точках х и -х - 2ai, поэтому она не может принимать все значения по модулю р". Следовательно, d = О (по модулю р) и, если а 1, выполнялось бы равенство dx + ах + с = X (по модулю р) для некоторых х, а это противоречит тому факту, что последовательность по mod р имеет период длиной р.

Чтобы показать достаточность условий, можно воспользоваться теоремой 3.2.1.2А и рассмотреть несколько тривиальных случаев, когда т = р, где е > 2. Если р = 2, то ясно, что Хп+2 = Х„ + 2 (по модулю 4); если р = 3, получим Хп+з = Х„ - d + Зс (по мод>лю 9), используя (i) и (ii). Для р > 5 можно следующим образом доказать, что Хп+р = Хп + рс (по модулю р). Пусть d = рг, а = 1 + ps. Тогда, если Хп = сп + pYn (по модулю р), необходимо получить Yn+i = псг + ncs + Yn (по модулю р); поэтому Yn = (з)2сг + {)(сг + cs) (по модулю р). Таким образом, Yp modp = О, и соотношение доказано.

Сейчас можно доказать, что последовательность (Хп) целых чисел, определенная в "указании", удовлетворяет соотношению

X„pf = Хп + tp (по модулю р+), п > о,

для некоторых i с i modp / О и для всех / > 1. Этого достаточно для доказательства, что последовательность {Хп modp) имеет период длиной р°, если длина периода является делителем р, но не делителем р*". Соотношение, приведенное выше, уже было установлено для / = 1, и для / > 1 оно может быть получено по индукции следующим образом. Пусть

Х„р/ = Хп + tp + ZnP (по модулю pf+);

тогда из квадратичного закона для генерирования последовательности с d = рг, а = 1+ps следует, что Zn+i = 2rtnc + st + Zn (по модулю р). Поэтому Z„+p = Z„ (по модулю р). Следовательно,

Xn+kpf = Хп + k{tp + Z„p-+) (по модулю р+)

для к = 1, 2, 3, .... Если положить теперь к = р, го на этом доказательство будет завершено.

Замечание. Если f{x) - полином степени, более высокой, чем 2, и Хп+\ = f{Xn), анализ будет несколько сложнее, хотя можно использовать тот факт, что f{m + p) =

f{m) +pf(m) 4-p/"(m)/2! Н----, для доказательства того, что многие полиномиальные

последовательности дают максимальный период. Например, Ковэю (Coveyou) доказал, что период равен т = 2", если /(0) нечетно, /(j) = 1, f"{j) = О и f{j -I- 1) = /(j) + 1 (по модулю 4) для j = 0,1,2,3. [Studies in Applied M&th. 3 (Philadelphia: SIAM, 1969), 70-111.]

9. Пусть Xn = 4Yn + 2; тогда последовательность Yn удовлетворяет квадратичному рекуррентному соотношению Yn+i = (4Yn + ЬУп + 1) mod2~.

10. Случай 1: Хо = О, Xl = I; следовательно, Хп = Fn- Ищем наименьшее п, для которого F„ = О и Fn+i = 1 (по модулю 2"). Так как 2„ = F„(F„ i -I- F„+i), Fin+i = Fl + F+i, найдем индукцией по е, что для е > 1 3.2.-1 = О и Fg.j.-i+i =2-1-1 (по модулю 2). Это означает, что период является делителем З, но не 3-2". Следовательно, период

равен либо 3-2 , либо 2 Но fj- - всегда нечетное число (так как только Fzn - четное).

Случай 2: Хо = а, Xi = Ь. Тогда Хп = aFn-\ + bFn- Нужно найти наименьшее положительное п, такое, что a{Fn+\ - Fn) + bFn = а и aFn + bfn+i = Ь. Это влечет, что (6 - а6 - a)f„ = О, (Ь - аЬ - a)(f„+i - 1) = 0. И 6 - аЬ - нечетно (т. е. оно простое относительно тп). Итак, условие эквивалентно тому, что Fn = О, Fn+i = 1-

Метод определения периода Fn ддя любого модуля впервые был приведен в статье Д. Д. Волла (D. D. Wall, АММ 67 (1960), 525-532). Другие факты относительно последовательности Фибоначчи по модулю 2 найдены Б. Йенссеном (В. Jansson, Random Number Generators (Stockholm: Almqvist &c Wiksell, 1966), Section 3C1).

11. (a) Легко видеть, что = 1 +f{z)u{z)+pv{z) для некоторых u{z) и v{z), где v{z) ф О (по модулю /) (г) и р. По биномиальной теореме

= l+p+t;()+p+г;()(p-l)/2

плюс следующие члены, конгруэнтные нулю по модулям /(г) и р"*". Так как р > 2, то z" = 1 +pv{z) по модулям f{z) и р+. Если pv(z) = о по модулям f{z) и р+, должны существовать полиномы a{z) и b{z), такие, что p{v{z) + pa{z)) = f{z)b{z). Поскольку /(0) = 1, получаем, что b{z) кратно р" (по лемме Гаусса 4.6.1G). Отсюда v{z) = О по модулям f{z) и р. в итоге получено противоречие.

(b) Если z -1 = f{z)u{z) +pv{z), то

Giz) = uiz)/{z - \)+pv{z)lf{z){z - 1);

следовательно, А„+л = An (по модулю p) для больших п. Обратно, если (An) обладает последним свойством, то G{z) = u{z) + v{z)I{I - z) +pH{z) для некоторых полиномов u{z) и v{z) и некоторого степенного ряда H{z), таких, что ряд и полиномы имеют целые коэффициенты. Отсюда следует равенство 1-z = u{z)f{z){l-z) + v{z)f{z)+pH{z)f{z){l-z), и H{z)f(z){l - z) является полиномом, так как другой член равенства - полином.

(c) Достаточно доказать, что неравенство А(р) ф A(p+i) влечет такие соотношения Л(р+1) = рЛ(р) ф А(р+). Из (а) и (Ь) следует, что А(р+2) ф рА(р) и что A(p+i) является делителем рА(р), но не А(р). Следовательно, если А(р°) = pq, где q modp ф О, то A(p+i) должно равняться pd, где d - делитель q. Но сейчас A„+p/+i = Хп (по модулю р); значит, pd кратно pq и d = q. [Замечание. Предположение о том, что р > 2, необходимо; например, если ai = 4, аг = -1, к = 2, го (An) = 1, 4, 15, 56, 209, 780, ...; А(2) = 2, А(4) = 4, А(8) = 4.]

(d) g{z) =Хо + {Xl - aiAo) -!-••• + {Xk-i - aiXk-2 - UiXk-z-----ak-iXo)z-\

(e) Утверждение (b) можно обобщить для G{z) = g{z)/ f{z); следовательно, предположение, что длина периода равна А, влечет то, что g{z){l - z) = О по модулям f{z) и р. Выше был рассмотрен только частный случай для g{z) = 1. Но обе части этого сравнения можно умножить на полином Хенселя b{z) и получить, что 1 - z = О по модулям f{z) и р.

Замечание. Более "элементарное" доказательство результата в (с) можно получить без помощи производящих функций, если использовать метод, аналогичный примененному в ответе к упр. 8. Если Ах+п = А„ + рВп для п = г, г--1, ...,г--А;-1 и некоторых целых чисел Вп, то такое же соотношение имеет место для всех п > г, ест определить Вг+к, Вг+к+1, заданным рекуррентным соотношением. Так как полученная последовательность для Вп является линейной комбинацией смещений последовательности An, получим Вх+п = Вп (по модулю р) для всех достаточно больщих значений п. Теперь А(р") должно быть кратным А = А(р). Для всех достаточно больших п справедли-