AOP_Tom2 (1021737), страница 113
Текст из файла (страница 113)
// = //а, 26+ 2//с,... ////; 2// 2а + 1, Ь, с, ... // = // а, 1, 1 + 2//Ь вЂ” 1, с, ... ////. Используйте этот метод длн нахождения разложении в цепную дробь числа -'е, если известно разложение в цепную дробь числа е (зто разложение дается формулой (13)). ь 16.
(МЯ1] (Р. У. Госпер (Н. %'. Соврет).) Обобщая упр. 14, разработайте алгоритм, который вычисляет цепную дробь Ле + //Хы Хг,... // для (ах + 6)/(сх + 0) по заданному разложению числа х в цепную дробь хо+ //хм хг,... // и заданным целым чнг гам а, 6, с, 4, таким, что о4 ~ Ьс. Сделайте свой алгоритм таким, чтобы он выполнялся как "оперативная сопрограмма", которая перед вводом каждого из х, выводит как можно болыпе значений Х». Продемонстрируйте, как ваш алгоритм вычисляет (97х + 39)/( — 62х — 25), когда х = -1 + // 5, 1, 1, 1, 2, 1, 2//. 18.
[НМЗО] (Л. Эйлер, 1731.) Пусть /е(з) = (е' — е *)/(е*+ е ') = ЗапЪх и / эс(з) = 1//» (з) — (2п+ 1)/з. Докажите, что для всех и функция /»(з) есть аналитическая функция комплексной переменной з в окрестности начала координат, которая удовлетворяет дифференциальному уравнению /„'(х) = 1 — /»(з) — 2п/»(з)/з. Используя этот факт, докажите, что сапЪз =//з ', Зз ',5з ',7з ',...//. Затем докажите, используя правило Турника, что е 'с" = //1, (2т + 1)п — 1, 1//, сп > О. 24.
[МЯЯ] Каково среднее значение частичного отношения А» в разложении в цепную дробь случайного вещественного числа? 25. [НМЯ5] Найдите пример множества Х = 1с сс 1з О 1з и С [О .. 1], где все Х вЂ” непере- секающиеся интервалы, для которых (45) не выполняется. 29. [МЯУ] Покажите, что если числа (1/и, 2/и,..., [и/2]/и) выражены в виде правильных цепных дробей, то полученные результаты обнаруживают лево-правую симметрию в том смысле, что всякий раз одновременно с //Ас,..., Аз, Ас// появляется //Ас, Аз,, Ас// 27. [МЯ1] Выведите (55) из (49) и (54).
28. [МЯУ] Докажите следующие тождества, в которые входят три теоретико-числовые функции сз(п)с д(п), Л(п). и = ~ са(с)). Ъ) !пп = ) Л(с!), щ с»(п) = ~ д (-/ с). а) ~ )с(с)) = 6 с. щ» с) Л(п) = ~ д (-/ 1пс), щ» щ щ» 29. [МЯЛ] Полагая, что Т» задается формулой (55), покажите. что (57) равно (58). (Это общепринятое обозначение бесконечной цепной дроби // 1, и — 1, 1, 1, Зп — 1, 1, 1, бп — 1, 1, ... //.) Найдите также разложение в цепную дробь числа е Ю", где и > О нечетно. ь 17.
[МЯЛ) (а) Докажите, что //хс,-хз// = //хс — 1,1,хз — 1//. (Ъ) Обобщите это тождество, получив формулу для //хс, — хз, хз, — хс, хз, — хз,..., хз -с, — хз»//, в которой все частичные отношения являются положительными целыми числами при условии, что все х — большие положительные целые числа. (с) Из результата упр. 16 следует, что Сап1 = //1, -3, 5, — 7,... //. Найдите разложение Сап 1 в правильную цепную дробь. 18.
[Мдб] Покажите, что //ас, аз,..., а, хс, ас, аз,..., а, хз, ас, аю, а», хзс. //— //а ,.... аз, ас,хс, а ,..., аз,ас, хз, а ,..., аз,ас,хз,...// не зависит от хс,хз,хз,.... Указание. Умножьте обе цепные дроби на К (ас,аз, са ). 19. [МЯО] Докажите, что Н(х) =!обе(1+ я) удовлетворяет уравнению (24). 20. [НМЯО] Выведите (38) из (37). 21. [НМЯд] (Э. Вирсинг (Е. %)гз)пб).) Ограничения (39) были получены для функции )а, соответствующей функции д, с помощью оператора Тд(х) = 1/(х+ 1).
Покажите, что функция, соответствующая Тд(х) = 1/(х+с), при подходящей константе с > О обеспечивает лучшие оценки. 22. [НМ46] (К. И. Бабенко ) Разработайте эффективный способ вычисления точных приближений для величин Лс и срэ(х) в (44) при малых у > 3 и О < х < 1. 23.
[НМЯУ] Докажите (53), используя результаты, полученные при доказательстве теоремы %. Учитывая, что Ка(х1, хг, хз, х4) — полинам, равный Х1хзхзха + х1хз + Х1ха + хзха + 1, найдите н докажите простую связь между волиномом К (х1,..., х~) и словами длиной и в азбуке Морзе. (Ь) (Л. Эйлер, Хог1 Сонин. Асад. Яс!. Реа 9 (1762), 53-69.) Докажите, что К +„(хм...,х,„+„) = К (х1,...,х )К (х +1,...,х + ) + К ь 1(Х1 «., Хм-1)Ка-1(ХчЬЗ~ «;Хм+ ) ЗЗ. [МЯЯ) Пусть Ъ(и) — количество различных представлений числа и в виде и ы хх'+уу', х > у > О, х' > у' > О, х1 у, где х,х',у,у' целые.
а) Покажите, что если ослабить эти условия, допустив выполнение равенства х' = у', то количество возможных представлений числа и будет равняться И(и) + [(и — 1)/2). Ь) Покажите, что для фиксированных у > О и О < г < у, где 1 л у, и для любых фиксированных х', принадлежащих интервалу О < х' < и/(у+1) и таких, что х'г гв и (по модулю у), существует точно одно представление числа и, удовлетворяющее ограничениям в (а) и условию х ш 1 (по модулю у). с) Покажите, что /1(и) = 2 [(и/(у + 1) — С') /у) — [(и — 1)/2), где сумма берется по всем положительным целым числам у, г, 1', таким, что г Ъ у, 1 < у, Р < у, Н~ = и (по модулю у).
д) Покажите, что каждое из таких представлений Ъ(и) можно выразить единственным способом в виде у = Км-Г(Х1,..., Хм-Г), у' = Кь 1(х +з,,х ьь) д, х = К,„(х1,..., Хм), х' = Кь (х +1,..., х ьь) д, ГдЕ Ш, ХЧ д И ВСЕ Хз — ПОЛОжнтЕЛЬНЫЕ ЦЕЛЫЕ ЧИСЛа, дпя КОтерЫХ Х1 > 2, Х~а+Ь > 2, а д — делитель числа и. Теперь нз тождества, приведенного в упр. 32, следует, что и/д = к ьь(Х1,..., х ьь). Обратно, любой заданной последовательности целых чисел х1, ..., х эю такой, что х1 > 2, х ьь > 2, н для которой к ьь(х1,,х эь) делит и, ссютветствует, таким образом, тп+ Й вЂ” 1 представлений числа и. е) Покажите, что иТ„= [(би — 3)/2) + 26(и).
34. [НМ40[ (Г. Хайльбронн (Н. Не11Ъгопп).) Пусть Ьа(и) — количество представлений числа и, описанных в упр. 33, для которых хд < х', плюс половина количества представлений, для которых хд = х . а) Пусть д(и) — количество представлений, на которые не накладывается ограничение х ~ у. Докажите, что )г(и) = ~ д(д)дн, д(и) = 2~ ба( — ) . а1ч щч ь 30. [НМдд) Часто предлагается следующий вариант алгоритма Евклида; при выполнении шага деления вместо зал1ены о величиной и шод о заменить его величиной [(и шод о) — о[, если и шод с > -'о.
Так, например, если и = 26 и о = 7, то бед(26,7) = бед(-2, 7) = бед(7,2); когда кратные 7 вычитаются из 26, наименьшим иа абсалюглнад величине асгиаглкам будет — 2. Сравните эту процедуру с алгоритмом Евклида; оцените число шагов деления, сэкономленных в результате применения этого метода ь 31. [МИ) Найдите наихудший случай для модифицированного алгоритма Евклида, предложенного в упр. 30.
Каковы наименьшие исходные числа и > о > О, для обработки которых необходимо затратить и 1нагов деления? 32. [Яд[ (а) Словом длиной и в азбуке Морзе называется цепочка нз г точек н э тире, для которой г+ 2э = и. Например, словами длиной 4 в азбуке Морзе являются Ь) Обобщите результат упр. ЗЗ, (Ь), показав, что для В > 1 выполняется равенство Ьз(и) = х,(и/(у(у+ !))) + 0(и), где сумма берется по всем целым числам у и 1, для которых ! .~ у и О < ! < у <,/и/В. с) Покажите, что ~,„,(у/(у + !)) = >р(у)1п 2+ О(а,(у)), где сумма берется по ! из интервала О < ! < у, причем ! .1.
у и а, (у) = 2 В(у(1/л). й) По жите, что ] „", Р(у)/уз = 2 ", д(г!)Н~„>а>/Вз, е) Отсюда получаем асимптотическую формулу Т = ((12 ! 2)/я~)(1 — ~ Л(В)/В) + 0(~-~( ) ). 35. [НМ41] (Э. Ч. Яо (А. С. Уао) и Д. Э. Кнут (1>. Е. КппеЬ).) Докажите, что при 1 < т < и сумма по всем частичным частным для дробей т/и равна 2( [х/у]+ [и/2]), где суммирование берется по всем представлениям и = хх'+ уу', удовлетворяющим условиям упр.
33, (а). Покажите, что 2 [х/у] = Зл ри(!пи)г+ 0(и!оби(!об!оби)р), и примените полученный результат к "античному" виду алгоритма Евклида, в котором вместо операции деления используется только операция вычитания. 36. [МВВ] (Г. Х. Врвдли (С. Н. Вгаа!еу).) Каково наименьшее значение и, при котором для вычисления бей(ип..., п») по алгоритму 4.5.2С требуется ?д делений, если в процессе вычислений постоянно используется алгоритм Евклида? Предполагается, что?д > и > 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
