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

b) Имеется простая связь значений, расположенных в правых столбцах, со значениями, расположенными в левых столбцах. Видит ли читатель эту связь? Она заключается вот в чем:

1 - х1,Х2,...,Хп = 1,Х1 - 1, Х2, ...,х„ ; (47)

см. упр. 9.

c) Между левыми и правыми числами в первых двух столбцах наблюдается симметрия: если встречается Ai,A2,..., At , то встречается также At, А2,А\ . Так происходит всегда (см. упр. 26).

d) Если исследовать все частные в таблице, то обнаружится, что всего их имеется 96 и из них II = 40.6% равны 1, Ц = 21.9% равны 2, = 8.3% равны 3. Эти данные хорошо согласуются с приведенными выше значениями вероятностей.

Число шагов деления. Вернемся теперь к исходной проблеме и исследуем величину Тп - среднее число шагов деления при v = п (см. формулу (19)). Приведем отдельные значения Т„.

п= 95 96 97 98 99 100 101 102 103 104 105 Г„= 5.0 4.4 5.3 4.8 4.7 4.6 5.3 4.6 5.3 4.7 4.6

п= 996 997 998 999 1000 1001 ••• 9999 10000 10001 Г„= 6.5 7.3 7.0 6.8 6.4 6.7 ••• 8.6 8.3 9.1

п= 49998 49999 50000 50001 ••• 99999 100000 100001 Тп= 9.8 10.6 9.7 10.0 ••• 10.7 10.3 11.0

Обратите внимание на некоторую неустойчивость поведения. Если п простое, то соответствующее ему значение Г„ больше соседних значений. И это значение соответственно меньше соседних, если п содержит много делителей. (В приведенном списке числа 97, 101, 103, 997 и 49999-простые числа; 10001 = 73 • 137; 49998 = 2-З-13-641; 50001 = 3-7-2381; 99999 = 3-3-41-271 и 100001 = 11-9091.) Нетрудно понять причину такого поведения. Если gcd(«, v) = d, то алгоритм Евклида выполняет операции с числами и \и v так же, как и с числами u/d и v/d. Поэтому, когда число V = п имеет несколько делителей, существует много способов выбора такого и, для которого п ведет себя так, как будто его значение меньше значения, которое есть на самом деле.

Соответственно рассмотрим другую величину, г„, которая является средним числом шагов деления, для случая, когда v - пни есть число, взаимно простое с п. Тогда

0<т<п тХп

Отсюда следует, что

Тп = -У,ти. (49)

Ниже приводится таблица значений г„ для тех же значений п, которые были рассмотрены выше.

п= 95 96 97 98 99 100 101 102 103 104 105 г„= 5.4 5.3 5.3 5.6 5.2 5.2 5.4 5.3 5.4 5.3 5.6

п= 996 997 998 999 1000 1001 ••• 9999 10000 10001 Тп = 7.2 7.3 7.3 7.3 7.3 7.4 • • • 9.21 9.21 9.22

п= 49998 49999 50000 50001 ••• 99999 100000 100001 г„= 10.59 10.58 10.57 10.59 • 11.170 11.172 11.172

Очевидно, что г„ ведет себя значительно лучше, чем Г„, и оно должно значительно легче поддаваться анализу. При внимательном изучении таблицы значений г„ при малых п обнаруживается ряд серьезных отклонений, например Г50 = тюо и Тбо = 7"i20- Но по мере роста числа п значения г„ становятся вполне нормальными, как это видно в приведенной выше таблице, и не указывают ни на какую особую зависимость от свойств разложимости на простые множители числа п. Если построить график значений г„ как функций Inn по приведенным выше данным, то окажется, что эти значения расположены очень близко к прямой линии:

г„ «0.843 In п + 1.47. (50)

Это свойство будет учтено чуть позже, при исследовании процесса формирования правильной цепной дроби. Учитывая выражение (15), для алгоритма Евклида получаем

Uo Uy Ut-i Uo

поскольку Uk+1 = Vfc. Далее, если U = Uo иУ = Vo взаимно просты и если имеется t шагов деления, то

XoXi...Xt-i = l/U.

Полагая U = NHV = m<N, найдем, что

\nXo+\nXi+---+lnXt-i=-\nN. (51)

Так как известно распределение величин Хо, Ху, Х, это уравнение можно использовать для оценки величины

t = T{N; тп) = Г(т, N) - 1.

Возвращаясь к формулам, приведенным перед теоремой W, находим, что среднее значение величины In Хп в случае, когда Ао - вещественное число, равномерно распределенное в интервале [0.. 1), равно

f\nxFix)dx= [\nxfnix)dx/{l+x), (52)

Jo Jo

где /п{х) определено в уравнении (33). Отсюда, рассуждая так же, как и ранее (см. упр. 23), получаем

/п(а:) = j+CI(2-"). (53)

Следовательно, среднее значение величины 1п Хп очень хорошо аппроксимируется величиной

In 2 Уо 1 + а; In 2 Уо 1 + е""

ln2V 4 "9 16 "25 ")

= -Ы2( + 4 + 9 + --Ч4-16-36--))

= -2ПГ2(-4 + 9 + -) = -7rV(121n2).

Поэтому в силу (51) следует ожидать, что приближенная формула будет иметь вид

-7г2/(121п2) » -InTV,

т. е. t должно приближенно равняться величине ((12 In 2)/тг) In Ж Эта константа (121п2)/7г = 0.842765913 ... полностью согласуется с эмпирической формулой (50), полученной ранее, так что есть веские основания полагать, что формула

121п2 , Тп W -5- In п + 1.47

(54)

описывает истинное поведение г„ при п -¥ оо.

Если предположить, что вьшолняется приближенное равенство (54), получим следующую формулу:

где A(d)-функция фон Мангольдта, определяемая правилами

если п = р, где р- простое число и г > 1; в противном случае.

(См. упр. 27.) Например,

121п2/, 1п2 1п2 1п5 1п5>

= {о

(55)

(56)

r.oo-i(lnlOO-

+ 1.47

2 4 5 25 « (0.843) (4.605 - 0.347 - 0.173 - 0.322 - 0.064) + 1.47 к 4.59;

точное значение Тюо равно 4.56.