Итак, для рассматриваемой разности получена точная формула. При \2z\ < 1 множитель е + 1 отличен от нуля, Дп(2г) < еп!/(2п + 1)! и

1и.,.. ,. {О -СГ)- СТ) - С: »)-)

> (Мл-1-1-

- п! V 4 16 64 у 3 п!

Таким образом, сходимость очень быстрая даже для комплексных значений z.

Для перехода от этой цепной дроби к цепной дроби для можно воспользоваться равенством tanh г = 1 - 2/{е + 1). После несложных выкладок получим представление (е + 1)/2 в виде цепной дроби. Правило Гурвица дает разложение в цепную дробь функции е + 1, из которого остается вычесть единицу. Для нечетных п

е-2/n 2J, (12m + 6)n, (3m + 2)n + [n/2j, 1 , m > 0.

Еще одно доказательство было предложено К. С. Дэвисом (С. S. Davis) и опубликовано в журнале J. London JVfath. Soc. 20 (1945), 194-198. Впервые разложение числа е в цепную дробь было получено эмпирически Роджером Коутсом (Roger Cotes), Philosophiced Transactions 29 (1714), 5-45, Proposition 1, Scholium 3. Эйлер прокомментировал эти результаты в письме Гольдбаху (Goldbach) от 25 ноября 1731 года [Correspondance JVfathematique et Physique, edited by P. H. Fuss, 1 (St. Petersburg, 1843), 56-60], a также опубликовал батее подробное описание этих результатов в Commentarii Acad. Sci. Petropolitanse 9 (1737), 98-137; 11 (1739), 32-81.

17. (b) xi - 1, 1, Жг - 2, 1, жз - 2, 1, ..., 1, жгп-i - 2, 1, Жгп - 1 . [Примечание. Отрицательные параметры могут быть исключены из континуантов при помощи тождества

i<m+n+l(Xi,. . .,Хт, -Х,Уп, ,У\)

= {-\)"~- Km+n+2{Xl, . . . ,Хт-\,Хт - 1, 1, Ж - 1, -J/n, . . . , -J/l),

из которого после повторного применения можно получить

Km+n+l{xi, Хт, -Ж, J/n, . . . , J/l)

= -Кт+п+з{Х1,. . .,Хт-1,Хт - 1, 1, Ж - 2, 1, J/„ - l,J/n-l, . . ,У\).

Похожее тождество встречается в упр. 41.]

(с) 1 -I- 1,1,3,1,5,1, ... = 1 -I- 2т -I-1, III, m>0.

18. Поскольку в силу тождеств (5) и (8) выполняется

Кт{а\,ач,.. .,ат) а1,аг,... ,ат,ж

= Кт-\{а2, ...,ат) -I- (-l)"/(Am-i(ai,.. .,am-i) + Кт{а\,а2,.. .,ат)х),

будет выполняться и

Km{ai,a2,... ,ат) 11(4,0.2,... ,ат,х\,а\,а2,... ,ат,Х2,а.\,а2,... ,am,X3,ai,... II

= Km-i{a2, ...,ат) + (-1)"(С + Ах,), С + Ажг, (-1)"(С + Ахз),... Ц,

где А = Km{ai,a2,...,am) и С = Km-i{a2,... ,ат) + Km-i{ai,.. .,am-i). Соответственно в силу (6) искомая разность равна

(Am-i(a2, •.. ,ат) - Кт-\{а\,... ,am-i))IKm{ai,a2,... ,ат).

[Случай, когда m = 2, рассматривался Эйлером в Commentarii Acad. Sci. PetropoUtanae 9 (1737), 98-137, §24-26.]

19. Сумма для 1 < < iV равна logb((l -I- x){N + \)I{N -I-1 -I- ж)).

20. Пусть Я = SG, д{х) = (1 + x)G(x), h(x) = (1 + х)Н{х). Тогда из (37) следует, что h(x + 1)/(х + 2) - h(x}/(x + 1) = -(1 + x)-s(l/(l + х))/(1 + 1/(1 + х)).

21. <р{х) = с/(сж + 1) + (2 - с)/((с - 1)а; + 1), Uip(x) = 1/(х + с). При с < 1 минимум функции ip{x)/U(p{x) достигается в точке а; = О и 2с < 2. Если с > ф, минимум достигается в точке X = 1 и < ф. Когда с и 1.31266, значения функции при а; = О и а; = 1 почти одинаковы и минимум > 3.2; получены границы: (0.29)" < J7" < (0.31)". Улучшение оценок границ произошло за счет хорошо подобранных линейных комбинаций в формуле Tg{x) = j:aj/i + cj).

23. Основное тождество Rn(x) = {Rn{x) - Rn(0))/x + а;Д(бп(а;)) для вп(х), значения которого изменяются от О до а;, получим, используя интерполяционную формулу из упр. 4.6.4-15 для Хо = О, Xl = X, Х2 = X + е и полагая, что б -> 0. Функция Rn в этом тождестве имеет непрерывную вторую производную. Следовательно, в этом случае Л;(а:) = 0(2-).

24. 00. [А. Хинчин, в Compos. Math. 1 (1935), 361-382, доказал, что эта сумма Ai Н-----1-А„

первых п частичных отношений вещественного числа X будет равна примерно п Ig п почти для всех X В упр. 35 показывается, что для рациональных чисел X ситуация будет иной.]

25. Всякое объединение интервалов можно записать как объединение непересекающихся интервалов, поскольку имеем \Jk>ih = Ufc>i(-fc \Ui<j<fc-j)i это есть объединение

непересекающихся множеств Ik \ Ui<j<fc-j каждое из которых может быть выражено в виде конечного числа непересекающихся интервалов. Поэтому можно, пронумеровав каким-либо образом функциональные числа отрезка [0..1], взять I - \yik, где Ik - некоторый интервал длиной 6/2*°, содержащий /г-е рациональное число. В этом случае p(Z) < б, но 1 П Рп = п для всех п.

26. Цепные дроби Ai,..., Atfj, которые появляются при представлении наших чисел,- это именно те дроби, для которых Ai > 1, At > 1, а Kt{Ai,A2, ...,At) есть делитель числа п. Поэтому (6) завершает доказательство. [Замечание. Если mi/n = Ai,..., А и тг/п = l/At,...,A\ , где т\ и тпг взаимно просты с п, то mimz = ±1 (по модулю п). Это и есть условие, определяющее рассматриваемое соответствие. В случае, когда Ai = 1, согласно (46) имеет место аналогичная симметрия.]

27. Сначала докажем результат для п = р, а затем-для п = rs, где числа г и s взаимно просты. Альтернативный путь - использовать формулу из следующего упражнения.

28. (а) Левая часть - мультипликативная функция (см. упр. 1.2.4-31). Она легко вычисляется, когда п является степенью простого числа, (с) С учетом (а) имеем формулу обращения Мёбиуса (Mobius): если /(п) = Yld\n9{<I), то д{п) = Ed\n

29. Сумма приближенно равна

(((121п2)/7г) \uN\)lN - Ed>imicP + 1.47;

здесь Yld>i A{d)/(f сходится к постоянному значению -С(2)/С(2), в то время как согласно приближению Стирлинга In iV! = NlnN - N + О (log N).

30. Предлагаемая модификация алгоритма влияет на вычисления только в том случае, когда при выполнении следующего шага деления немодифицированным алгоритмом получается частное, равное 1. В таком случае этот следующий шаг деления будет пропущен модифицированным алгоритмом. Вероятность того, что данный шаг деления будет пропущен, равна вероятности того, что Afc = 1 и что этому частному предшествует четное число частных, равных 1. Учитывая условия симметрии, получаем, что это есть вероятность того, что А*, = 1 и что за ним следует четное число частных, равных 1. Последнее имеет место тогда и только тогда, когда Xk-i > ф - 1 = 0.618..., где ф -

отношение золотого сечения: действительно, А*. = 1 и Ak+i > 1 тогда и только тогда, когда 1 < Xk-i <1; Ак = Ак+1 = Ак+2 = 1 и Ак+з > 1 тогда и только тогда, когда < Xk-i < , и т. д. Таким образом, экономится приблизительно - Рк-1{ф- 1) « 1 -\gф ~ 0.306

шагов деления. Среднее число шагов деления в случае, когда v = п и и взаимно просто с п, приблизительно равно {{121пф)/п)\пп.

К. Вален (К. Vahlen) в работе СгеЛе 115 (1895), 221-233, рассматривал все алгоритмы, которые при и mod v ф О пг. каждой итерации заменяют значения (и, и) значениями (v, (±u)modii). Для и ± V существует ровно v таких алгоритмов, и они могут быть представлены в виде бинарного дерева с v ветвями. Самые мелкие ветви дерева будут формироваться, если на каждой итерации выбирать самые маленькие остатки-это соответствует наименьшему возможному числу итераций вьшолнения всех таких алгоритмов определения наибольшего общего делителя. В случае выбора наибольших остатков будут формироваться самые глубокие ветви дерева. [Похожие идеи в Hist. Acad. Sci. 23 (Berlin, 1768), 111-180, §58, рассматривал Лагранж.] Дальнейшие результаты, относящиеся к рассматриваемому вопросу, изложены в работе Н. Г. де Брейна (N. G. de Bruijn) и У. М. Заринга (W. М. Zaring), опубликованной в Nieuw Archief voor Wislcunde (3) 1 (1953), 105-112, a также в работе Г. И. Ригера (G. J. Rieger), опубликованной в JVfath. Nachr. 82 (1978), 157-180.

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

31. Пусть ао = О, ai = 1, a„+i = 2а„ + an-i; тогда an = ((1 + \/2)" - (1 - \/2))/2ч/2. Наихудший случай (в смысле теоремы F) имеет место, когда и = о„ -I- an-i, v = an, п > 2. Этот результат получен А. Дюпре (А. Dupre) и опубликован в журнале J. de Math. 11 (1846), 41-64. В этой работе А. Дюпре исследовал также более общие процедуры "с предварительным просмотром", предложенные Ж. Бине (J. Binet).

32. (b) Член Km-i(xi,... ,Xn,-i}Kn-i{xm+2,...,Хт+п) соответствует тем словам длиной m -t- п в азбуке Морзе, для которых тире находится в т- и (т 1)-й позициях; другой член соответствует противоположному случаю. (Можно также воспользоваться упр. 2. Более общее тождество

Km+n{Xi, . . . ,Хт+п)Кк(Хт+1, . . . , Хт+к)

= Km+k{Xl, . . . , Хт+к)Кп(Хт + 1, . . . , Хт+п)

+ { - l)Km-l(xi, . . . , Xm-l) Kn-k-l{Xm+k+2, . ,Хт+п)

также опубликовано в работе Л. Эйлера.)

33. (а) Новыми представлениямиявляются х = m/d, у = {п - Tn)/d, х = у = d = gcd(m, п - т) для \п < т < п. (Ь) Отношение (п/ж) - у < х < njx определяет х. (с) Подсчитаем все элементы ж, которые удовлетворяют условиям (Ь). (d) Пару целых чисел ж>у>0сж1.у можно записать единственным образом в виде х = Кт{х\,..., im), у = Km-i{xi,.. .,Xm-i), где ц > 2 И m > 1; здесь у/х = хт, ,Xi. . (е) Достаточно показать, что Z]i<a,<„/2 С", п) = 2[n/2j + h(n); это следует из упр. 26.

34. (а) Деление i и у на gcd(x,y) дает д{п) = Y!,d\n(",/d). Применим результат упр. 28, (с) и используем условие симметрии между переменными со штрихом и без него. (Ь) Для фиксированных у а t представления с xd > х обладают свойством х < Nd; следовательно, имеется 0{\/nd/y) таких представлений. Суммируем теперь при условии О < t < у < y/njd. (с) Если s{y) есть данная сумма, то, к примеру, Eci\y *() = у{Н2у - Ну) = к{у); отсюда s{y) = Zd\yHy/d)- Далее к(у) = у\п2 - \ + 0{1/у).