(d) Е;=,{у)1у = Try=M\y]id)yd = J:ы<nid)cd\ (Аналогично ЕГ=1 <-1(у)/у = 0(1)-) (е) ELi/WA=6/7r + 0(l/n) (cM.ynp.4.5.2-10(d)),aELiMfc)logfc c=O(l). Следовательно, при d > 1 имеем hd{n) = n((3 In 2)/7г) ln(n/d) + 0(n) для d > 1. В итоге

/!(") = 2 Ecd\" Kd)hc{n/cd) = ((6 In 2)/7г)п(1пn - E - E) + (nf),

где остаточные суммы равны Е = Еы\п/С) = О и Е = Ecd\n/С) 1"/ -

Ed\nA(d)/d. [Известно, что <T-i(n) = O(loglogn); см. работу Харди (Hardy) и Райт (Wright) An Introduction to the Theory of Numbers, §22.9.]

35. Cm. Proc. Nat. Acad. Sci. 72 (1975), 4720-4722. M. Л. B. Пайтвэй (M. L. V. Pitteway) и К. М. A. Кэстл (С. М. А. Castle) [Bull. Inst. Math, and its Appiications 24 (1988), 17-20] нашли убедительное, но требующее больших усилий эмпирическое свидетельство того, что сумма частичных отношений равна

г/ 1 18(1п2)У 6 у /4г р+1р-1\

- 2.542875 + 0(п"/).

36. Выполняя алгоритм в обратном порядке и полагая, что на шаге С2 для заданного значения к выполняется tfc - 1 делений, получаем минимальное число Un, для которого gcd(ufc+i,--.,un) = Ftk HUfc = F(i .. (no модулю gcd(ufc+i,Un)); здесь

все ti > 2, tl > 3 и tl 4-----1- t„ i = iV + n - 1. При этих условиях можно минимизировать

Un = F(] Ft„ y, приняв tl = 3, tj = • = tn 2 = 2, u„ = 2fn-n+2- Если условиться также, что ui > uj > • • > Un, решение ui = 2F.v „4.3 + 1, U2 = • = Un-i = 2лг-п+з, Un = 2fn-n+2 имеет минимум гц. [См. CACJVf 13 (1970), 433-436, 447-448.]

37. См. Proc. Amer. Ma.th. Soc. 7 (1956), 1014-1021; см. также упр. 6.1-18.

38. Положим m = [п/ф], так что т/п = +е = ai, 02,... , где О < е < 1/п. Пусть к - минимальное значение, такое, что а*, > 2; тогда (ф" + {-1)Рк-1е)/{ф~ - {-lFke) > 2, отсюда к четно иф = 2-ф< фРк+2(. = (Ф" - ф~)е/у/5. [Ann. Polon. Math. 1 (1954), 203-206.]

39. Минимум 287; ни одна дробь со знаменателем < 287 не принадлежит 2,1,95 = 96/287 я; .33449477, как и интервалу

[.3335 .. .3345] = [ 2,1,666 .. 2,1,94,1,1,3 ].

Чтобы решить основной вопрос для дроби с меньшим знаменателем в промежутке [а..Ь] в случае, когда О < о < 6 < 1, учтем, что в обозначениях, принятых для представления правильных цепных дробей, будет иметь место соответствие xi ,Х2,. < yii 2/2,. • • тогда и только тогда, когда {-lyxj < (-l)-t/j для наименьших j, таких, что Xj ф yj, причем символ "оо" помещается за последним частичным отношением рационального числа. Таким образом, если о = xi,X2,... и 6 = j/i, t/2,. • • и если j минимально при Xj ф yj, в промежутке [а .. 6] дробь принимает вид с = xi,... ,Xj-i,Zj,... ,Zm , где zj,..., Zmll лежит между llxj,Xj+\,... и j/j, J/j+i, • - • включительно. Положим, что К-I = 0. Знаменатель

Aj-l(a;i, . . . ,Xj-l)Km-j + \{Zj, ...,«„)+ Kj-2{XI,. . . ,Xj-2)Km-j{Zj + l, . ..,Zni)

числа с будет минимальным при т = j и Zj = {j нечетно. yj + [t/j+1/00]; Xj + [xj+i 5100]). [Другой способ вывода этого метода основан на теории, изложенной в следующем упражнении.]

40. Можно доказать по индукции, что в каждом узле выполняется рг9(-Р(9г = 1, т. е. числа Р( и qi являются взаимно простыми. Поскольку p/q < p/q, то p/q < {p+p)/{q+q) < p/q-Кроме того, понятно, что метки на всех левых вершинах ветвей для чисел p/q меньше этих значений p/q, в то время как метки на всех правых вершинах больше этих значений. Поэтому каждое рациональное число может появиться в качестве метки не более одного раза.

Теперь остается показать, что каждое рациональное число должно обязательно появиться. Если p/q = ai,..., Or, 1 , где каждое из ai - положительное целое число, то по индукции можно показать, что узел с меткой p/q находится посредством перемещения ai раз влево, затем - перемещения ог раз вправо, оз раз влево и т. д.

[Впервые последовательность меток на сформированных уровнях исследовалась М. А. Штерном (М. А. Stern) в Crelle 55 (1858), 193-220, хотя в этой работе связь с бинарными деревьями не прослеживается. На получение всех возможных дробей при помощи интерполирования дроби (p+p)/(q + q) между соседними элементами p/q и р/q обратили внимание позже. Относящиеся к решению этой задачи важные идеи были опубликованы Даниэлем Швентером (Daniel Schwenter) [Delicise Physico-MathemsiticBe (Niirnberg, 1636), Part 1, Problem 87; Geometria Practica, 3rd edition (1641), 68; см. M. Cantor, Geschichte der Math. 2 (1900), 763-765] и Джоном Уоллисом (John Wallis) в его книге Treatise of AJg-ebra (1685), Chapters 10-11. K. Гюйгенс (С. Huygens) использовал эти идеи при конструировании приводов для своего планетария [см. Descriptio Autonjati Pianetarii (1703), опубликовано после его смерти]. Лагранж в работе Hist. Acad. Sci. 23 (Berlin, 1767), 311-352, §24, и в дополнении к переводу на французский язык алгебры Эйлера (1774), §18-§20, привел полное описание этой идеи. См. также упр. 1.3.2-19; А. Brocot, Revue Chronometrique в (1860), 186-194; D. Н. Lehmer, АММ 36 (1929), 59-67.]

41. Действительно, правильные цепные дроби для чисел, записываемых в общем виде обладают интересной закономерностью, основанной на тождестве

Km+n+l.{Xi, . . . , Хт-1,Хт - 1, Ij Уп - ii Уп-1, , tjl)

= XmKrn-liXi, . . . , Xrn-l)Kn(yn, . ,yi)

+ {-!)" Кт+п(хи- .,Xrn-uO, -Уп,-Уп-1,. . . , -yi).

Наибольший интерес это тождество представляет для случая, когда уп = Xm-i, Vn-i = Жт-2 и т. д., так как

K„+l{zi,. ..,Zk,0, Zk+l, ...,Z„) = K„-l{zi,. ..,Zk-l,Zk+ Zk+l,Zk+2, • • ,Zn). в частности, если Pn/qn = Кп-\{Х2, . . ,Xn)/Kn{xi,. . . ,Ж„) = Xl, . . .,Xn , TO Pn/qn + {-iT/qlr = Xi,...,Xn,r- 1, 1, Xn - 1, Xn-l,. , Xl .

Заменяя последовательность xi,..., Xn последовательностью xi,... ,Xn-i,Xn - 1,1 1 можно управлять формированием знака (-1)".

Например, для частичных сумм первого ряда получаем следующие цепные дроби четной длины: 1,1 ; 1,1,1,1,0,1 = 1,1,1,2 ; 1,1,1,2,1,1,1,1,1,1 ; 1,1,1,2,1,1, 1,1,1,1,1,1,0,1,1,1,1,1,2,1,1,1 = 1,1,1,2,1,1,1,1,1,1,1,2,1,1,1,1,2,1,1,1 . Далее последовательность упорядочивается и подчиняется простой закономерности. Для случая.

когда n - 1 = 20q + г при О < г < 20, найдем, что частичное отношение Оп может быть легко вычислено:

1, если г = 0,2,4, 5,6, 7,9,10,12,13,14,15,17 или 19;

2, если г = 3 или 16;

1 + [q + г) mod 2, если г = 8 или 11;

2 - dq, если г = 1; 1 + dq+i, если г = 18.

Здесь dn - "последовательность дракона", определяемая правилами do = 1, djn = dn, din+i = О, d4n+3 = 1. Кривая дракона (рассматривалась в упр. 4.1-18) поворачивается вправо на п-м шаге тогда и только тогда, когда dn = 1.

Числа Лиувилля при / > 3 равны /- 1, / +1, / - 1, 1, /, /- 1, - 1, 1, Z- 2, /, 1, 1, 1+1,1 - 1, - 1, ... . п-е частичное отношение Оп зависит от последовательности дракона, элементы которой представимы по п mod 4 в следующем виде: если п mod 4 = 1, то частное равно / -2+dn-i + (Ln/2j mod4), если n mod4 = 2, то оно равно Z+2-dn+2 -([п/2] mod4); если nmod4 = О, то оно равно 1 или /С-) - 1 в зависимости от того, будет ли dn = О или 1, где число к - наибольшая степень 2, которая делит п; если nmod4 = 3, то оно равно - 1 или 1 в зависимости от того, равно ли dn+i = О или 1, где число к -

наибольшая степень 2, которая делит п+1. Для I = 2 применяются те же правила, но из рассмотрения исключаются нули; поэтому в зависимости от п mod 24 получаются более сложные закономерности..

[См. 3. О. Shallit, J. Number Theory 11 (1979), 209-217; Allouche, Lubiw, Mendes FVance, van der Poorten, and Shallit, Acta Arithmetica 77 (1996), 77-96.]

42. Предположим, что gA = \qX-p\. Можно всегда найти такие целые числа и и v, что q = Щп-1+vqn ир = ирп-1+vpn, где р„ = Kn-i(A2, . ,А„), так как qr„pn i-qr„ ip„ = ±1. При V = О результат очевиден. В противном случае должно быть uv < О, т. е, знак числа u(qn-iX-pn-i) совпадает со знаком числа«(пА-рп), а \qX-p\ равно \и\ jn-i А-p„ i + \v\ \qnX - Pn. Поскольку u / О, доказательство на этом завершается. Обобщение данного результата дается теоремой 6.4S.

43. Если число X представимо, оно родственно числу х в дереве Штерна-Брокота из упр. 40, поэтому представимые числа образуют поддерево бинарного дерева. Положим, что числа (и/и) и (v/v) - соседние представимые числа. Тогда одно из них является предшественником другого. Пусть, например, число (и/и) является предшественником числа (v/v), поскольку другой вариант аналогичен. Тогда (и/и) - ближайший левый предшественник для (v/v), так что все числа между и/и и v/v будут для числа (v/v) его потомками, а этим числом порождается медианное число ((u + v)/(u +v)). Учитывая зависимость между правильной цепной дробью и бинарным деревом, медианное число и все его левые потомки будут иметь в качестве последнего представимого числа pi/qfi число (и/и), в то время как все потомки справа от медианного числа будут иметь в качестве последнего представимого числа pi/gi число (v/v). (Числа pi/qr; помечают родителей узлов "точек превращения" на пути к х.)

44. Контрпример для М = N = 100 выглядит так: (и/и) - \, (v/v) = Ц. Тем не менее в силу уравнения (12) тождество почти всегда справедливо; оно нарушается только тогда, когда и/и + v/v очень близко к дроби, более простой, чем (и/и).

45. При использовании обычного длинного деления для определения таких А и г, чтобы выполнялось равенство и = Av + г при О < г < v, требуется 0((1 + log A)(logu)) единиц