b) Обобщите результат упр. 33, (b), показав, что для d > 1 выполняется равенство ha{n) = {п1{у{у +1))) + 0(п), где сумма берется по всем целым числам у ut, для которых t LynQ <t<y< y/nfd.

c) Покажите, что J2y=iiy/iy + 0) = v(j)lii2 + 0{cr-i{y)), где сумма берется по t из интервала О <t <у, причем t ± у и cr-i{y) = J2d\y{i/d).

d) Покажите, что Ei {уУу = Ed=i p{d)Hn/ai/d.

e) Отсюда получаем асимптотическую формулу

Т„ = ((12 In 2)/1г2)(Inп - A(d)/d) + 0(а 1 (п)).

35. [ЯМ./](] (Э. Ч. Яо (А. С. Yao) и Д. Э. Кнут (D. Е. Knuth).) Докажите, что при 1 <т <п сумма по всем частичным частным для дробей т/п равна 2(53[а;/г/] + [»г/2]), где суммирование берется по всем представлениям п = хх + уу, удовлетворяющим условиям упр. 33, (а). Покажите, что 2[/у1 = 37г"п(1пп) + 0(п logn (log log п)), и примените полученный результат к "античному" виду алгоритма Евклида, в котором вместо операции деления используется только операция вычитания.

36. [М25] (Г. X. Брэдли (G. Н. Bradley).) Каково наименьщее значение Un, при котором для вычисления gcd(ui,..., Un) по алгоритму 4.5.2С требуется Л делений, если в процессе вычислений постоянно используется алгоритм Евклида? Предполагается, что N >п>3.

37. [М38] (Т. С. Моцкин (Т. S. Motzkin) и Е. Г. Штраус (Е. G. Straus).) Пусть ai,..., а„ - положительные целые числа. Покажите, что найдется niax/ifn(ap(i)j... lap(n)) по всем перестановкам р{1). ..р{п) для всех {1,2,... ,п}, когда Opi) > ар(„) > ар(2) > an-i) >, и минимум будет при ap(i) < Ор(„) < ар(з) < ар(„ 2) < ар(5) < • • • < ар(в) < ар(„ з) < ар(4) < ap(n-i) < ар(2).

38. [М25] (Я. Микусинский (J. Mikusinski).) Пусть L{n) = rtaXm>o Т(т, п). Из теоремы F следует, что Цп) < logф{VЬn + 1) - 2. Докажите, что 2L{n) > log(\/5 п + 1) - 2.

► 39. [М25] (Р. У. Госпер.) Среднее количество ударов, которые выполняет бейсболист, равно .334. Каково минимально возможное число ударов, которое он выполняет? [Напомним читателям, не являющимся приверженцами бейсбола, что среднее количество ударов = (количество бросков)/(число битов), округленное до трех десятичных знаков.]

► 40. [М28] (Дерево Штерна-Броко (Stem-Brocot).) Рассмотрим бесконечное бинарное дерево, в котором каждый узел связан с дробью (pi + Pr)/(qi + qr), где pi/qi -метка узла, ближайщего к левому предшественнику, ирг/Зг -метка узла, ближайшего к правому предшественнику. (Левый предшественник расположен перед узлом в симметричном порядке, в то время как правый предшественник расположен за узлом. Определение симметричного порядка приведено в разделе 2.3.1.) Если для узла левые предшественники отсутствуют, то pi/qi = 0/1; при отсутствии правых предшественников Pr/qr = 1/0. Таким образом, метка корневого узла есть 1/1; метками узлов, порожденных корневым узлом, будут 1/2 и 2/1; метками четырех узлов второго уровня слева направо будут 1/3, 2/3, 3/2 и 3/1; метками восьми узлов третьего уровня будут 1/4, 2/5, 3/5, 3/4, 4/3, 5/3, 5/2, 4/1 и т.д.

Докажите, что для каждой метки p/q число р является взаимно простым с q; более того, узлы с метками p/q предшествуют узлам с метками p/q в симметричном порядке тогда и только тогда, когда метки удовлетворяют неравенству p/q < p/q. Найдите связь между цепной дробью для метки узла и пути к узлу, показав таким образом, что любое положительное рациональное число появляется как метка точно одного узла дерева.

41. [М40] (Дж. Шэллит (J. Shallit), 1979.) Покажите, что разложение в правильную цепную дробь выражения

1.11. V" 1

21 23 2 22"-1

п>1

содержит только единицы и двойки и представляется в исключительно простом виде. Докажите, что в случае, когда I - любое целое число > 2, частичные отношения чисел Лиувилля имеют регулярный вид. [Эти числа, введенные Ж. Лиувиллем (J. Liouville) в J. de Math. Tmes et Appl. 16 (1851), 133-142, впервые были строго определены как трансцендентные. Первым доказал трансцендентность такой формы числа и подобных констант О. Дж. Кемпнер (А. J. Kempner) в TVans. Amer. Math. Soc. 17 (1916), 476-482.]

42. [МЗО] (Ж. Лагранж, 1798.) Предположим, что разложение числа X в правильную цепную дробь имеет вид Ai, Аг,... , и пусть q„ = Kn{Ai,..., An)- Обозначим через Ijxjj расстояние от х до ближайшего целого числа minp х ~ р\- Покажите, что qA > Jlqn-iAjj для 1 < q < qn- (Таким образом, знаменатели qn так называемых сходящихся дробей p„/q„ = Al,..., А„ представляют собой целые числа, "обрывающие ряд", что приводит к приобретению \\qX\\ новых свойств.)

43. [МЗО] (Д. В. Матула (D. W. Matula).) Покажите, что описываемое уравнением 4.5.1-(1) правило "медианного округления" для чисел, представленных в формате с фиксированной и плавающей дробными чертами, в случае, если число х > О не представимо, может быть введено следующим простым образом. Пусть разложение числа х в правильную цепную дробь имеет вид ао -t- ai, аг,... и пусть р„ = АГп+1(ао,..., Оп), qn = Kn{ai, -. - ,ап)- Тогда round(x) = (p./gi), где дробь (pi/qt) представима, а дробь (Pi+i/gi+i) - нет. [Указание. См. упр. 40.]

44. [М25] Предположим, что выполняются арифметические операции в формате с фиксированной дробной чертой с медианным округлением, в которых дроби (и/и) представимы тогда и только тогда, когда и <М,0<и < N и и ± и - Докажите или опровергните тождество {{и/и) ® {v/v)) Q {v/v) = {и/и) для всех представимых дробей {и/и) и {v/v), обеспечивающих выполнение условия и и отсутствие переполнения.

45. [М25] Покажите, что алгоритм Евклида (алгоритм 4.5.2А) в случае применения к двум двоичным числам при п оо требует для выполнения О(п) единиц времени. (Такая же верхняя оценка справедлива и для выполнения алгоритма 4.5.2В.)

46. [М4З] Можно ли уменьшить верхнюю границу О(п) в упр. 45, если для вычисления наибольшего общего делителя использовать другой алгоритм?

47. [М40] Разработайте компьютерную программу нахождения как можно большего числа частичных отношений для вещественного числа х, задаваемого с высокой точностью. Примените ее для вычисления первых нескольких тысяч частичных отношений для постоянной Эйлера 7, которые можно вычислить по алгоритму, описанному Д. В. Суини (D. W. Sweeney) в Math. Сотр- 17 (1963), 170-178. (Если 7 есть рациональное число, то можно найти числитель и знаменатель этой константы, решив таким образом знаменитую математическую проблему. Согласно теории, изложенной в разделе, если рассматривать исходное число как случайное, следует ожидать получения около 0.97 частичных отношений на каждый десятичный разряд. При этом не возникает необходимости в операциях деления с многократной точностью. (См. алгоритм 4.5.2L и статью Дж. У. Ренча (J. W. Wrench) и Д. Шэнкса (D. Shanks), Math. Сотр. 20 (1966), 444-447.)

48. [М21] Пусть То = (1,0, и), Ti = {0,l,v), ..., T„+i = {{-l)"+v/d, (-l)"u/d, 0) представляют последовательности векторов, вычисляемых по алгоритму 4.5.2Х (расширенный алгоритм Евклида), и пусть ai,... ,ап - правильная цепная дробь для v/u- Выразите Tj через континуанты, включающие oi, ..., а„, где 1 < j < п.

49. [МЗЗ] Откорректируйте последнюю итерацию алгоритма 4.5.2х так, чтобы можно было заменить элемент an двумя частичными отношениями (а„ - 1,1). Подразумевается, что число итераций п подчиняется заданной закономерности. Продолжая предыдущее упражнение, положим, что А и fi - произвольные положительные вещественные числа, и пусть в = л/Xfw/d, где d = gcd(u,и). Докажите, что если число п четно и если Tj = («j, Viто min"+i\Xxj + fizj - [j even] в\<в.

► 50. [M25] Для данного иррационального числа q € (о.. 1) и вещественных чисел /3 и 7, таких, что о < /3 < 7 < 1, положим, что /(0,,7)-наименьшее неотрицательное целое число п, такое, что Р < an mod 1 < 7. (Такое целое число всегда существует в силу теоремы Вейля (Weyl), упр. 3.5-22.) Разработайте алгоритм для вычисления /(q,/3,7).

► 51. [МЗО] [Рациональная реконструкция.) Число 28481 превращается в число 41/316 (по модулю 199999) в том смысле, что 316-28481 = 41. Как это можно обнаружить? Объясните, как для заданных целых чисел а и m при то > а > 1 найти целые числа х и у, такие, что ах = у (по модулю то), х ± у, о < х < \frnj2 и у < \fmj2, или определить, что таких чисел X и у нет. Может ли существовать более одного решения?

4.5.4. Разложение на простые множители

В основу ряда вычислительных методов, которые рассматривались в этой книге, положен тот факт, что любое положительное целое число п можно однозначно выразить в виде

п=: pip2-.pt, Р1 <Р2 < ••• <Pt, (1)

где каждое р -простое число. (В случае, когда п = 1, это равенство выполняется при f = 0.) К сожалению, довольно сложно найти это разложение на простые множители или определить, является ли число п простым. Общеизвестно, что разложить на простые множители большое число значительно труднее, чем найти наибольший общий делитель двух больших чисел тип. Поэтому там, где это возможно, следует избегать разложения больших чисел на простые множители. Но, учитывая, что разработан целый ряд оригинальных методов, позволяющих ускорить процесс разложения чисел на простые множители, проанализируем некоторые из 5ТИХ методов. [Всесторонний исторический обзор методов разложения чисел на простые множители, известных до 1950 года, выполнен X. К. Уильямсом (И. С. Williams) и Дж. О. Шэллитом (J. О. Shallit), Ргос. Symp. Applied Math. 48 (1993), 481-531.]

Деление и разложение на множители. Прежде всего рассмотрим самый очевидный алгоритм разложения на простые множители. Если число п > 1, то его можно делить на последовательные простые числа р = 2, 3, 5, ... до тех пор, пока не будет обнаружено наименьшее число р, для которого п mod р = 0. Тогда р и будет наименьшим простым множителем числа п. Тот же процесс можно применить к числу п п/р и попытаться разделить полученное значение числа п на р и на большие простые числа. Если на некотором этапе обнаружится, что п mod р ф О, но [п/р\ < р, можно сделать следующий вывод: число п - простое, так как если п не является простым числом, то в силу равенства (1) должно быть п > pf. Но из условия pi > р следует, что Pi>(p+ 1) > р(р + I) > р 4- (nmodp) > [n/pjp + (пmodp) = п. В результате получаем следуюшую процедуру.