между интервалами. При оперировании 64-битовыми словами общая длина числителя и знаменателя ограничивается величиной 64 - 6 = 58 бит.]

14. Количество чисел, кратных п в интервале (а.. 6], равно [6/nJ - [a/nj. Отсюда, используя метод включений и исключений, получаем рещение задачи в виде 5о - 5i

52----, где 5* равно E([2/PJ - \M\IP\){\N2lP\ - L-iZ-PJ). просуммированному по

всем произведениям Р различных простых чисел к. Можно также выразить ответ в виде

min(m2,A2)

Y ([Л2/п] - LMi/nJ) (LJV2/nJ - [JVi/nJ).

РАЗДЕЛ 4.5.2

1. Везде замените min, max, на gcd, 1cm, х соответственно (предварительно убедитесь, что все тождества справедливы и тогда, когда любая переменная равна нулю).

2. Для простого числа р пусть Ир, uip, Vnp - степени числа р в каноническом разложении чисел и, ui, ..., i;„. По предположению Up < v\p Л- + Vnp- Необходимо показать, что Up < min(up,i;ip) -I- min(up,i;„p), но это неравенство действительно выполняется, если Up не меньще каждого Vjp или Up меньще некоторого Vjp.

3. Решение 1. Если п = pj... р"", это число в каждом случае равно (2ei 1)... (2ег + 1). Решение 2. Если положить и - gcd(d, п) и i; = n/lcm(d, п) для каждого делителя d числа п, то можно получить взаимно однозначное соответствие. [Е. Cesaro, kanali di Matematica Рига ed Applicata (2) 13 (1885), 235-250, §12.]

4. См. упр. 3.2.1.2-15(a).

5. Будем выполнять сдвиг вправо чисел и и i; до тех пор, пока не получим, что ни одно из них не кратно 3. Запоминаем соответствующее значение степени 3, которое появится в наибольщем общем делителе. Затем на каждой итерации присваиваем t - и + v или t <- и - V {в зависимости от того, какая из этих величин кратна 3), сдвигаем t вправо до тех пор, пока оно не перестанет быть кратным 3, после чего заменяем max(u, i;) полученным результатом.

Свидетельство того, что gcd(40902, 24140) = 34, поразительно!

6. Вероятность того, что оба числа и и i; четны, равна 1; вероятность того, что оба числа кратны четырем, равна , и т. д. Таким образом, величина А имеет распределение, задаваемое производящей функцией

4 16 64 1 - г/4

Среднее значение равно , а среднеквадратичное отклонение - v + -5 = . Если и и V независимо и равномерно распределены в интервале 1 < и, i; < 2, необходимо внести

в расчет небольшие поправки, тогда среднее в действительности будет равно (2 - 1)- Е (2-* - 1)2 = 1 - 1(2 - 1)- + JV(2 - 1)-.

7. Если числа и и i; не являются оба четными, то равновероятен каждый из случаев (четное, нечетное), (нечетное, четное), (нечетное, нечетное) и при этом имеем соответственно В = 1, О, 0. Следовательно, в среднем В = j. Если уж быть совсем точным, то, когда 1 < U, i; < 2, необходимо внести небольшую поправку: вероятность того, что В = 1, в действительности будет равна

(2 - 1)- Е (2-* - 1)2- = \ - -как следует из упр. 6.

8. Обозначим через F число шагов вычитания, в которых и> v. Тогда Е - F + В. Если заменить исходные данные (и,х>) на (v,u), то значение С не изменится, а число F станет

равным С - \ - F. Следовательно, jEave = 5(Cave - + Bave-

9. В первый раз бинарный алгоритм попадает на шаг В6 при значениях и = 1963, v = 1359; тогда t <- 604, 302, 151 и т. д. Наибольший общий делитель равен 302. Применяя алгоритм X, находим, что 2 31408 - 23 2718 = 302.

10. (а) Два целых числа взаимно просты тогда и только тогда, когда оба они не делятся одновременно ни на одно простое число. (Ь) Перегруппируем сумму в (а), принимая знаменатели равными А; = pi .. .рг. (Каждая из сумм в (а) и (Ь) на самом деле конечна.) (с) Так как {n/kf - [п/к = 0(п/к), то д„ - Efc=i р{к){п/кУ = ELi Ок) = 0{пНп). Далее, Ек>п(/) ~ 0(п). (d) E,d\nli) ~ [Фактически имеет место более общий, чем в (Ь), результат

где суммирование в правой части берется по простым делителям тг, и эта сумма равна п{1 - 1/pf)... (1 - 1/р,), если n = pV.. .р/.]

Замечание. По аналогии найдем множество целых чисел к, которое с вероятностью 1/С(к) = 1/(12„>1 V"*) является множеством, состоящим из простых чисел. Это доказательство теоремы D предложено Ф. Мертенсом (F. Mertens, Crelle 77 (1874), 289-291). Такая методика дает гораздо более строгий результат, а именно: для произвольных /ид 6тг~тп + O(nlogm) пары целых чисел и € [/(т) .. /(т) -I- т), v € [д{п).. д{п) + п) являются взаимно простыми при т <п.

11. (а) Искомая вероятность равна б/тг, умноженному на 1-(--(-, т. е. 49/(б7г) « .82746.

(Ь) Среднее значение равно б/тг, умноженному на 1/14-2/4-1-3/9-1----, т. е. оо. (Это верно,

несмотря на результаты упр. 12 и 14.)

12. [AnnaJi di JVfat. (2) 13 (1885), 235-250, §3.] Пусть (т(п) - количество положительных делителей числа п. Тогда ответ будет таким:

[Следовательно, среднее значение меньше 2, хотя в случае, когда и и i; не являются взаимно простыми, они имеют по меньшей мере два общих делителя.]

13. 1 + 1 + + ••• = 1 + +! + •••-И1 + 5 + 5 + ---)-

14. (а) L = (б/тг) Ed>i d- Ind = -C(2)/C{2) = Ep„p„„oe(lnp)/{2 " 1) « 0.56996. (b) (8/7г) Ed> 1И нечетное] d-2 In d = L- i In 2w 0.33891.

15. Dl = ±v/u3, V2 = Ци/из (знак зависит от того, четно или нечетно число итераций). Это следует из того факта, что числа vi и взаимно просты (на протяжении всего процесса выполнения алгоритма) а viu = ~V2V. [Следовательно, в момент завершения выполнения алгоритма viu = lcm(u,v), но такой метод-не лучший путь вычисления наименьшего общего кратного. Обобщение этого метода рассмотрено в упр. 4.6.1-18.]

Более подробно с данным вопросом можно ознакомиться, рассмотрев упр. 4.5.3-48.

16. В результате применения к числам t; и m алгоритма X вычисляем такие значения х, при которых XV = 1 (по модулю тп). (Это можно сделать путем упрощения алгоритма X за счет отказа от вычисления U2, V2 и <2, поскольку данные величины в ответе не присутствуют.) Затем присвоим w их mod тп. [Отсюда следует, как в упр. 4.5.3-45, что для реализации этого процесса при его применении к большим п-битовым числам необходимо затратить 0{п) единиц времени. В упр. 17 и 39 рассмотрены алгоритмы, альтернативные алгоритму X.]

17. По аналогии с методом Ньютона можно положить, что и = {2и - t)u)mod2 (см. окончание раздела 4.3.1). Точно так же при ut; = 1 + 2ш (по модулю 2") полагаем и = 1 -1-2= ((-иш) mod 2").

18. Пусть в дополнение к числам и и t; числа ui, U2, из, vi, V2, из - переменные с многократной точностью. Расширенный алгоритм будет выполнять над числами из и гз те же операции, что и алгоритм L над числами и я v. Новыми операциями многократной точности будут: присвоение на шаге L4 < <- Auj, t <- t + Bvj, w -t- Cuj, w <- u> + Dvj, Uj <r- t, Vj i- w для всех j. Кроме того, если на этом шаге В = О, выполняем присвоение t i- Uj - qvj, Uj -f- Vj, Vj <- t для всех j я для q = [из/ад]. При малых значениях из подобным образом модифицируется и шаг L1. Внутренний цикл (шаги L2 и L3) остается неизменным.

19. (а) Пусть tl = х + 2у + 3z. Тогда 3ti + у + 2z = 1, 5ti - Зу - 20z = 3. Исключим у, я тогда 14*1 - 14г = 6. Рещений нет. (Ь) На этот раз 14ti - 14 = 0. Выполняем деление на 14 и исключаем ti; общее решение имеет вид х = 8z - 2, у = 1 - 5z (z выбирается произвольно).

20. Предположим, что т > п. При m > п = О получим (т - t,0) с вероятностью 2~\ а при 1 < t < m получим (0,0) с вероятностью 2"". Valida vi* при п > О можно получить следующие значения.

Случай 1, т - п. Из (п, п) при 2 < t < п переходим в (п - t,n) с вероятностью

i/2 - 5/2+ -1-3/2. (Этими значениями будут , , ----) Вероятность попадания

в интервал (О, п) равна п/2"" - 1/2"" + 1/2"". Вероятность попадания в интервал (п, к) такая же, как и вероятность попадания в интервал (к, п). Вероятность прекращения выполнения алгоритма равна 1/2"".

Случай 2, т = п + 1. Из интервала (п + 1,п) в интервал (п, п) можно попасть при п > 1 с вероятностью или при п = 1 с вероятностью 0. Вероятность попадания в интервал

(n-t, п) равна 11/2+ -3/2+для 1 < t < п-1. (Этими значениями будут -, \, ----)

Вероятность попадания в интервал (1,п) при п > 1 равна 5/2"+ - 3/2"" ; вероятность попадания в интервал (О, п) равна 3/2" - 1/2"".

* Здесь: после соответствующих усилий (лат.). - Прим. перев.