Случай 3, т > п + 2. Вероятности, полученные для этого случая, приведены в следующей таблице.

{т-\,п): l/2-3/2"-"+*-6„i/2"+;

(m -t,n): 1/2 + 3/2"-"++, \<t<n;

{m-n,n): l/2" + l/2", n>l;

{m-n-t,n): l/2"+ + <5ti/2"-\ \<t<m-n;

(0,n): 1/2"-.

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

21. Покажите, что при фиксированном t; и при 2"" < и < 2"" для больших т каждый цикл "вычитание и сдвиг" рассматриваемого алгоритма уменьшает [Ig и\ в среднем на два.

22. После выполнения операции сдвига вправо числа и, лежащего в интервале 1 < и < 2, до тех пор, пока оно не станет нечетным, ровно для {N - т)2"""*""° целых чисел выполняется равенство [Ig и\ = т. Следовательно,

(2 - 1)2с = ЛгСоо + 2ЛГ (ЛГ-п)2"-С„о

l<n<Af

+ 2 (iV-m){iV-n)2"+"-C,n„+ (iV-n)2"-C„„.

\<n<m<N l<n<N

(Та же формула справедлива для D в обозначениях Dmn •)

Средняя сумма равна 2" 12o<m<n<N mn2~"~"{{a + P)N+j-am-Pn). Поскольку

Y 12-"" = 2-{п + 1)2-" и Y т(т-1)2-" =4-{п+п + 2)2-",

0<т<п 0<т<п

сумма ПО т равна

22JV-2 Y n2-"((7-a-/3n+{a+/3)iV)(2-(n+l)2-")-a(4-(n + n+2)2-"))

0<n<N

= 2"- f(a4-/9)iV n2-"{2-{n+l)2-")+Cl(l)] .

n>0

Таким образом, в ответе коэффициент при {а + P)N равен 2-(4 - ()) =

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

вычислений на основе общей формулы суммирования по частям:

23. При а; < 1 выполняется соотношение Pr{u > v к v/u < х) = ~{\ - Gn{x)). Если же а; > 1, то I + Pr{u <v и vju >\jx) = \ + \Gn{llx); в соответствии с (40) это также равно \{\-Gr,{x)).

24. 5Z*;>i 2-*G{l/(2* + 1)) = S(l). Это значение, не имеющее отношения к классической константе, приближенно равно 0.5432582959.

25. Как заметил Ричард Брент (Richard Brent), функция (3(6"") - нечетная аналитическая функция для всех вещественных значений у. Если положить G{e~) = Aiy + Хзу + Хьу + • = р{е~ - 1), то получим -р\ = Ai = А, рг = А, -рз = jA + Аз, р4 = А -f- Аз, -Р5 = А+ IA3-I-A5;

Приведем несколько первых значений:

Al и .3979226812, Аз и -.0210096400, As « .0013749841, А7 « -.0000960351.

Фантастическое предположение: limk-tooi-X-zk+i/X-zk-i) = I/tt.

26. Согласно (39) левая часть равна 25(l/2;)-55(l/22;)+25(l/4a;)-25(a;)+5S(2a;)-2S(4a;); согласно (44) правая часть равна S(2x) - 25(4а;) + 2S(l/x) - S(l/2x) - 2S(x) + 4S(2a;) -45(l/2a;) + 23(1/4х). Самыми интересными являются, вероятно, случаи, когда х = 1, X = 1 2 п X = ф. Например, при х = ф получаем 2G(4<) - 5G(2<) + 0{фУ2) - С(ф) = 20{2ф).

27. При п > 1 в соответствии с упр. 1.2.11.2-4 имеем

2ф„=п.х:2-* Е =Е2-*("+х:-""

*;>0 >=0 (>0 *>! J=0

= E2-=("+xi(")2**""V"

*;>1 (=0 \ /

и, конечно, 1:*>1 2-*(+ = 1/(2+ - 1).

28. Следуя обозначениям упр. 6.3-34(b), положим, что Sn

1/(6"/- 1). Получаем 8„{т) = Г„(т) + 0(e-"/"n/m2) и 2.+1 = E,>i 2-S„(20 = Тп + 0{п-), где Тп = J2j>i 2-Tn{V). Из того, что t„+i < т„, а 4г2„ - т„ = 1/(е" - 1) положительное, но малое число, следует Тп = Q{n~). Более подробную информацию можно получить, если записать

1 1 j Г-" az)T(z)n- и =J- Г"*" сыг(г)п-Z.2.e"/2-l 2,гЛ/2-.ос 2Я2-.) 27rii3/2-icc 2--1

Интеграл равен сумме вычетов 2 + 27rifc/ln2, т. е. произведению п~ и 7г7(61п2) -f- /(п), где

/(п) = 2 Е Ж(с(2 + 27rifc/ In 2)Г(2 + 27rifc/ In 2) exp(-27rifc Ig n)/ In 2)

есть периодическая функция Ig n со "средним" значением, равным нулю.

29. (Решение П. Флажоле (Р. Flajolet) и Б. Балле (В. Vallee).) Если при соответствующих условиях fix) = Е.>1 2-*р(2=х) и д(s) = д{х)х-Чх, то /*(«) = E*>i 2->+g\s) = 5*(s)/(2+ - 1) и fix) = 2 /j;+ fis)x-ds. В этом случае, полагая, что д{х) = 1/(1 +ж), найдем преобразование в виде gis) = ж/smns при О < < 1. Таким образом.

2*1 + 2*ж 27ггЛ/2 , (2+1-1)sintts

Отсюда следует, что f{x)-сумма вычетов гх /(2 - 1) при < О, т. е. 1 +xlgx + ix + xP{lgx) - fx + x* - fx + • • , где функция

(0 = 1ЙЕ;т

\п2 sinh{2m7r2/ln2)

m=l

есть периодическая функция, абсолютные значения которой никогда не превышают 8 X 10". (Ввиду малости функции P(t) Брент в своей первой работе не обратил на нее внимания.)

Преобразование Меллинафункции /(1/х) имеет вид /*(-s) = я-/((1 -2-)8шя-8) при -l<its< О, поэтому /(1/х) = ji. ="ds/(l - 2"). Найдем теперь при

На < -1 вычеты подынтегральной функции /(1/х) = х - х Н----. [Эта формула может

быть получена и непосредственно.] Имеем Si(x) = 1 - /(х), и отсюда следует

Ог(х) = fix) - /(1/х) = xlgx + ix + xP(lgx) - + (1 - х)<(х),

2 1 + X

где ф{х) = ЕГ=о(-1)*7{2*+ - 1).

30. Имеем Giix) = Si(x) - ri(l/x) + Щх) - Щг/х), где

""Ж* 1 + 2Ч1 + 2*х) """i 1 + 2+2«=х Преобразования Меллина будут иметь вид

= sl"()/(" - () = -

.. (1 + 2-)- /8-1\ 1

ад=х:(2+1)-=ЕС;)2й:г-

(>1 к>0

Таким образом, при О < х < 1 получаем следуюш;ие выражения:

Г1(х) = а(0) + a(-l)x(lgx+i) - а(1)х/1п2 + xAHgx)JcL{-k)i-x)\

к>2

Г2(х) = 6(0) + 6(-l)x(l6x+i) -б(1)х/1п2 + хВ(1бх) - Y £zb{~k){-xf,

к>2

Si{i/x) = 2 ,

к>1

2(1/-) = Е (l6- - - \ - + + .