Анимация
JavaScript


Главная  Библионтека 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 [ 135 ] 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261

b) Докажите, что для всех п > N, где N - некоторое целое число, зависящее от X, выполняются неравенства О < [/„ < \/D, О < V„ < 2\/D. Следовательно, представление квадратичной иррациональности правильной цепной дробью в конечном счете периодично. [Указание. Покажите, что

{-Vd - U)/V = Ао + Ль . ,Ап,-V„/i/d + и„) ,

и, используя равенство (5), докажите, что при больщих значениях п величина положительна.

c) По.тожим Рп = Kn+i{Ao, Al,... ,Ап) и qn = Kn{Ai,..., An)- Докажите тождество Vpl + lUpnqn + {(U - d)IV)ql =

d) Докажите, что представление иррационального числа X правильной цепной дробью в конечном счете периодично тогда и только тогда, когда число X есть квадратичная иррациональность. (Это утверждение относительно цепной дроби является аналогом утверждения о том, что разложение вещественного числа X в десятичную дробь в конечном счете периодично тогда и только тогда, когда X рационально.)

13. [МЩ (Ж. Лагранж, 1767.) Пусть /(х) = а„х" + + ао, an > О -полином с целочисленными коэффициентами, у которого нет рациональных корней и имеется точно один вещественный корень f > 1. Разработайте компьютерную программу для нахождения примерно первой тысячи частичных отнощений числа f с помощью следующего алгоритма (который включает в себя только сложение).

L1. Присвоить А <- 1.

L2. Для fe = О, 1, ..., п - 1 (в таком порядке) и j = п - 1, ..., fc (в таком порядке) присвоить aj <- Oj+i -I- aj. (На этом шаге функция f(x) заменяется функцией д{х) = /(х -1-1), полиномом, корни которого на единицу меньще корней полинома /.)

L3. Если an + a„~i -Ь • • • -I- oq < О, то присвоить Л <- А -I- 1 и возвратиться к шагу L2.

L4. Вывести А (которое является значением следующего частичного отношения). Заменить коэффициенты {ап,ап-\,- •. ,ао) на (-ао, -ai,.. ., -йп) и возвратиться к шагу L1. (На этом шаге вьшолняется замена /(х) полиномом, корни которого обратны корням полинома /.)

Например, начав с f{x) = х - 2, алгоритм выведет сначала "1" (заменив f{x) на х - Зж- За: - 1), затем- "3" (заменив f{x) на 10х - 6х - 6х - 1) и т. д.

14. [М22] (А. Гурвиц (А. Hurwitz), 1891.) Покажите, что при помощи следующих правил можно найти разложение в цепную дробь числа 2Х, если известны частичные отношения числа X:

2/1 2а, Ь, с, ... = а, 2Ь + 2 с, ... ; 2 2а + 1, Ь, с, ... = а, 1, 1 + 2 Ь - 1, с, ... .

Используйте этот метод для нахождения разложения в цепную дробь числа \е, если известно разложение в цепную дробь числа е (это разложение дается формулой (13)).

► 15. [М31] (Р. У. Госпер (R. W. Gosper).) Обобщая упр. 14, разработайте алгоритм, который вычисляет цепную дробь Ао + Xi, Аг,... для (ах + Ь)/ (сх + d) по заданному разложению числа х в цепную дробь хо + xi,X2, • • и заданным целым числам а, Ь, с, d, таким, что ad ф be. Сделайте свой алгоритм таким, чтобы он выполнялся как "оперативная сопрограмма", которая перед вводом каждого из Xj выводит как можно больше значений Xk- Продемонстрируйте, как ваш алгоритм вычисляет (97х -t- 39)/(-62х - 25), когда а: = -1+ 5,1,1,1,2,1,2 .



16. [НМЗО] (Л. Эйлер, 1731.) Пусть /о(г) = (е - е-)1{е +е~) = tanhz и fn+i{z) = 1/fn{z) - {2n-\-\)/z. Докажите, что для всех п функция fn(z) есть аналитическая функция комплексной переменной z в окрестности начала координат, которая удовлетворяет дифференциальному уравнению(г) = \-in{zf- 2nin{z)lZ. Используя этот факт, докажите, что

tanh Z = l/z-\ Ъг-\ bz~\ 7г"\ ... .

Затем докажите, используя правило Гурвица, что

е-" = l,(2m + l)n-l,l , m>0.

(Это общепринятое обозначение бесконечной цепной дроби 1,п-1, 1, 1,Зп-1, 1, 1,5п-1, 1, ... .) Найдите также разложение в цепную дробь числа е"", где п > О нечетно.

► 17. [М23] (а) Докажите, что xi,-X2 = xi - 1,1,Х2 - 1 . (b) Обобщите это тождество, получив формулу для Xl, -Х2,Хз, -Х4,Х5, -Хб, . . . ,Х2п-1, -Х2п , В КОТОрОЙ ВСе

частичные отнощения являются положительными целыми числами при условии, что все X - большие положительные целые числа, (с) Из результата упр. 16 следует, что tanl = 1, -3, 5, -7,... . Найдите разложение tan 1 в правильную цепную дробь.

18. [М25] Покажите, что ai, 02,..., Om, xi, ai, 02,..., Om, X2, ai, a2,..., Om, хз,... -

om,..., 02, ai, xi, am,..., a2, ai, X2, Om,..., a2, ai, X3,... не зависит от xi, X2, хз,----

Указание. Умножьте обе цепные дроби на Кт(а\, 02,..., От).

19. [М20] Докажите, что F(x) = log(,(l + х) удовлетворяет уравнению (24).

20. [НМ20] Выведите (38) из (37).

21. [НМ29] (Э. Вирсинг (Е. Wirsing).) Ограничения (39) были получены для функции (р, соответствующей функции д, с помощью оператора Тр(х) = 1/(х -t- 1). Покажите, что функция, соответствующая Тд{х) = 1/{х+с), при подходящей константе с > О обеспечивает лучшие оценки.

22. [НМ46] (К. И. Бабенко.) Разработайте эффективный способ вычисления точных приближений для величин Aj и Ф>(х) в (44) при малых j>3h0<x<1.

23. [НМ23] Докажите (53), используя результаты, полученные при доказательстве теоремы W.

24. [М22] Каково среднее значение частичного отношения An в разложении в цепную дробь случайного вещественного числа?

25. [НМ25] Найдите пример множества Z = Ji U /2 U /з U • С [О .. 1], где все / - непересекающиеся интервалы, для которых (45) не выполняется.

26. [М23] Покажите, что если числа {1/п, 2/п,..., [п/2\/п} выражены в виде правильных цепных дробей, то полученные результаты обнаруживают лево-правую симметрию в том смысле, что всякий раз одновременно с At,... ,А2,А\ появляется А\,А2,... ,At .

27. [М21] Выведите (55) из (49) и (54).

28. [М23] Докажите следующие тождества, в которые входят три теоретико-числовые функции V5(n), ц{п), Л(п).

a)p(d) = J„i. b)lnn=A(d), n = (d).

d\n d\n d\n

c)A(n) = pQ)lnd, v,(n) = pg)d.

d\n d\n

29. [M23] Полагая, что Тп задается формулой (55), покажите, что (57) равно (58).



► 30. [НМ32] Часто предлагается следующий вариант алгоритма Евклида: при выполнении шага деления вместо замены v величиной и mod v заменить его величиной \{и mod v)-v\, если и mod V > и. Так, например, если и = 26 и и = 7, то gcd(26, 7) = gcd(-2, 7) = gcd(7, 2); когда кратные 7 вычитаются из 26, наименьшим по абсолютной величине остатком будет -2. Сравните эту процедуру с алгоритмом Евклида; оцените число шагов деления, сэкономленных в результате применения этого метода.

► 31. [М55] Найдите наихудший случай для модифицированного алгоритма Евклида, предложенного в упр. 30. Каковы наименьшие исходные числа и > v > О, для обработки которых необходимо затратить п шагов деления?

32. [20] (а) Словом длиной п в азбуке Морзе называется цепочка из г точек и а тире, для которой г + 2а = п. Например, словами длиной 4 в азбуке Морзе являются

Учитывая, что К{х1,Х2,хз,Х4) - полином, равный 11X2X3X4 + х\Х2 -Н xix -Н Х3Х4 -Н 1, найдите и докажите простую связь между полиномом Kn{xi,... ,Хп) и словами длиной п в азбуке Морзе. (Ь) (Л. Эйлер, JVovi Comm. Acad. Sci. Pet. 9 (1762), 53-69.) Докажите, что

Кт+п{х1, . . . ,Хт+п) = Km{xi, . . . ,Хт)Кп{Хт+1, ,Хт+п)

-Н Кт-1 {Xl,. . , Xm-l)Kn-l{Xm+2, ,Хт+п)-

33. [М32] Пусть/г(п) - количество различных представлений числа п в виде

п = хх + уу, х>у>0, х> у> О, х1у, где х,х, у, уцелые.

a) Покажите, что если ослабить эти условия, допустив выполнение равенства х = у, то количество возможных представлений числа п будет равняться h{n) + [{п - 1)/2J.

b) Покажите, что для фиксированных y>QvLQ<t<y, где t L у, и для любых фиксированных х, принадлежащих интервалу О < х < n/(j/ -Н <) и таких, что xt = п (по модулю J/), существует точно одно представление числа п, удовлетворяющее ограничениям в (а) и условию X = t (по модулю у).

c) Покажите, что h{n) = 3 \{п/{у + t)- t) /у] -[{п - 1)/2J, где сумма берется по всем положительным целым числам у, t, t, таким, что t ± у, t < у, t < у, tt = п (по модулю у).

d) Покажите, что каждое из таких представлений h{n) можно выразить единственным способом в виде

X = Km{Xi, . . . ,Хт), у = Km-l{Xi, . . . ,Xm-l),

X = АГ)ь(Хт+1, • • . ,Xm4-)c)d, У = Kk-l{Xm+2, .,Xm+k)d,

где т, к, d И все Xj-положительные целые числа, для которых xi > 2, Хт+к > 2, а d-делитель числа п. Теперь из тождества, приведенного в упр. 32, следует, что n/d = Km+k{xi,... ,Хт+к)- Обратно, любой заданной последовательности целых чисел

Xl, Хт+к, такой, что XI > 2, Хт+к > 2, и для которой АГт+*(Х1,. .. ,Хт+)с) ДбЛИТ

п, соответствует, таким образом, т + к - 1 представлений числа п.

e) Покажите, что пТп = [{Ьп - 3)/2j -t- 2h{n).

34. [НМ40] (Г. Хайльбронн (Н. Heilbronn).) Пусть hd{n) - количество представлений числа п, описанных в упр. 33, для которых xd < х, плюс половина количества представлений, для которых xd = х.

а) Пусть д{п) - количество представлений, на которые не накладывается ограничение X ±у. Докажите, что

h(n) = p(d)gg), g(n) = 2h,Q).

d\n d\n



0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 [ 135 ] 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261