Таким образом, из (32) и (36) следует, что доказана следующая теорема.

Теорема W. При п оо распределение F„{x) равно lg(l + х) + 0(2~"). В дея-ствнтельностн Fn(x) - lg(l + х) лежит между (-l)"+5~"(ln(l + х)) (In 2/(1 + х)) и (-1)"+12-"(1п(1 + а;))(1п2/(1 + а;)) для О < а; < 1.

Если несколько изменить функцию tp, можно получить более сжатые границы (см. упр. 21). На самом деле Вирсинг пошел гораздо дальше, доказав в своей работе, что

F„{x) = lg(l + х) + {-ХГ9{х) + 0{х{1 - х){Х - 0.031)"), (40)

Л = 0.3036630028987326585974481219015562331109-

(41)

= 3,3,2,2,3,13,1,174,1,1,1,2,2,2,1,1,1,2,2,1,... .

Это фундаментальная постоянная (к счастью, никак не связанная с более известными постоянными), где Ф - интересная функция, аналитическая в комплексной плоскости за исключением отрицательной вещественной оси от -1 до -оо. Функция Вирсинга удовлетворяет соотношениям Ф(0) = Ф(1) = О, Ф(0) < О и 5Ф = -АФ. Таким образом, с учетом (37) эта функция удовлетворяет тождеству

Ф(г)-Ф(г-И) = ф(). (42)

Далее Вирсинг показал, что

ф(--(-) =сА-" log-1-0(1) при TV00, (43)

где с-константа, an = T{u,v) - число итераций алгоритма Евклида при вьшолнении операций над целыми числами и> v > 0.

Полное решение проблемы Гаусса было найдено несколькими годами позже К. И. Бабенко [ДАН СССР 238 (1978), 1021-1024], который использовал мощный аппарат функционального анализа для доказательства следующей формулы:

Fnix) = lg{l + x) + Y2"9ji) (44)

для всех 0<а;<1, п>1. В этой формуле [Аа] > Аз > jA] > ••• каждая из функций Ф(г)-аналитическая функция на комплексной плоскости за исключением [-00.. - 1]. Функция Фа-это функция Вирсинга Ф, а Аа = -А, в то время как Аз « 0.10088, А4 « -0.03550, А5 » 0.01284, Ае » -0.00472, А7 « 0.00175. Бабенко установил также дополнительные свойства собственных значений Aj, доказав, в частности, что они являются экспоненциально убывающими при j оо и что их сумма в (44) при j > к ограничена величиной (7Г/6)Ак"~* min(a;, 1 - х). [Дополнительная информация содержится в работах Бабенко и Юрьева, опубликованных в ДАН СССР 240 (1978), 1273-1276, в работах Майера (Mayer) и Роепсторфа (Roepstorff), J. Statistical Physics 47 (1987), 149-171; 50 (1988), 331-344; Д. Хенсли (D. Hensley), J. Number Theory 49 (1994), 142-182; a также в работах Доде (Daude), Флажоле (Flajolet) и Балле (Vallee), Combinatorics, Probability and Computing 6 (1997), 397-433; Flajolet, Vallee, Theoretical Сотр. Sci. 194 (1998), 1-34.] Джон Хершбергер (John Hershberger) вычислил 40-значное значение A в (41).

От непрерывного к дискретному. Выше были получены результаты, относящиеся к распределению вероятностей для цепных дробей в случае, когда X - вещественное число, равномерно распределенное в интервале [0.. 1). Однако вероятность того, что вещественные числа являются рациональными, равна нулю (почти все числа являются иррациональными), так что эти результаты непосредственно к алгоритму Евклида неприменимы. Прежде чем применять теорему W для решения задачи, необходимо преодолеть некоторые технические затруднения. Рассмотрим следующий результат, основанный на элементарной теории меры.

Лемма М. Пусть h, I2, . , Ji, J2, • - попарно непересекающиеся подынтервалы, содержащиеся в интервале [О.. 1), и пусть

I=[jh, J=[jJk, IC = [0..1]\{IUJ).

к>1 к>1

Предположим, что К, имеет меру нуль. Пусть Рп означает множество {0/п, 1/п, ... (п-1)/п}. Тогда

Ит lMI)- (45)

п-юо п

Здесь р(1)-мера Лебега множества I, т. е. Z,k>i length(/fc), а 1ПР„ обозначает число элементов множества IП Р„.

Доказательство. Пусть 1 = Ui<*;<n h ч Jn = \Ji<k<n к- Для заданного б > О найдем Л, достаточно большое, чтобы выполнялось соотношение р{Хм) + p{Jn) > 1 - б, и положим

fCN = ICU [j h и и Л.

k>n k>n

Ясно, что если I - любой из интервалов (а..Ь), [а..Ь), {а..Ь] и [а..Ь], то р{1) = b - а и

пр{1)-1<\1пРп\<пр{1) + 1. Пусть теперь г„ = \In П Р„, s„ = \ Jn П Р„, t„ = \ICn П Р„; тогда

n+Sn + tn = Щ

пр{Хы) -N<rn< пр{Хм) + Л; np{JN) -N<sn< npiJN) + N.

Значит,

п п п п

= 1--<1-МЛ) + -<М2:) + + е.

п п п

Это неравенство справедливо для всех п и для любого е; следовательно,

lim Гп/п = р{Х). I

п-юо

В упр. 25 показано, что лемма М нетривиальна в том отношении, что для справедливости формулы (45) необходимо принимать какие-то довольно ограничивающие предположения.

Распределение частичных отношений. Объединив теорему W и лемму М, докажем теперь несколько фундаментальных свойств, касающихся алгоритма Евклида.

Теорема Е. Пусть п и к-положительные целые числа; пусть также pt(a,n) - вероятность того, что {к + 1)-е частное A+i в алгоритме Евклида равно а, когда V = п и и выбирается случайно. Тогда

lim pkia,n) = FJ-) -fJ-), n-юо \а/ \а + 1/

где Fk{x) -функция распределения (22).

Доказательство. Множество I всех X в [0..1), для которых Ak+i = а, есть объединение непересекающихся интервалов, как и множество J всех X, для которых Ak+i Ф а. Поэтому применима лемма М, причем множество 1С - множество всех А, для которых Ак+1 не определено. Далее, Ек{1/а) - Fk{l/{a + 1)) есть вероятность того, что 1/(а -I- 1) < Хк < а это не что иное, как р{1), т. е. вероятность того, что Ак+1 = а. I

Из теорем Е и W следует, что частное, равное а, встречается с вероятностью lg(l + 1/а) - lg(l + 1/{а + 1)) = lg((a + 1)У{{а + if - 1)).

Так,

частное 1 встречается примерно в lg() = 41.504% случаев;

частное 2 встречается примерно в lg() = 16.993% случаев;

частное 3 встречается примерно в lg(Yf) = 9.311% случаев;

частное 4 встречается примерно в lg() = 5.889% случаев.

В действительности, если алгоритм Евклида формирует частные Ах, Лг, At, приведенное доказательство гарантирует такое поведение только для тех Ак, к которых мал по сравнению с t. На значения At-x, Л( 2, ... это доказательство не распространяется. Однако можно показать экспериментально, что распределение последнего ряда At-x, At-2, частных, по существу, такое же, как и первого ряда.

Рассмотрим, например, разложение в правильную цепную дробь ряд правильных дробей со знаменателем, равным 29.

В этой таблице следует обратить внимание на несколько моментов, а) Как указывалось ранее, последнее частное всегда равно 2 или более. Далее, имеем очевидное тождество

хх, ...,Хп-Х, Хп + 111 = Цхх,... III, (46)