AOP_Tom2 (1021737), страница 199
Текст из файла (страница 199)
В случае выбора наибольших остатков будут формироваться самые глубокие ветви дерева, !Похожие идеи в Н!вп Асад. Яс!. 23 (Вег!1п, 1768), 111-180, 958, ралсматривал Лагранж.) Дальнейшие результаты, относящиеся к рассматриваемому вопросу, изложены в работе Н. Г. де Брейна (Н. С. де Вгп1!и) и У, М. Зарин»а (ЧГ. М. Еа»1пб), опубликованной в .»7!епи Агсб!е/лоог 1Ив!»паде (3) 1 (1953), 105-112, а также в рабате Г. И. Ригера (С. 3, В1е8ег), опубликованной в Ма»Ь.
Обасбг. 82 (1978), 157-180, На многих компьютерах применение модифицированного алгоритма приводит к удлинению каждого шага деления. В таких случаях предпочтительнее воспользоваться идеей, изложенной в упр. 1. Применив ее, можно избежать выполнения всех шагов деления, когда частное равно единице. 31. Пусть ао = О, ал = 1, а»л» = 2а„+ а»! тогда а» = ((1 + л/2)" — (1 — л/2)")/2мг2. Наихудший случай (в смысле теоремы Р) имеет место, когда и = а„+ а„л, о = а„, и > 2. Этот результат получен Л. Дюпре (Л. Опрге) и опубликован в журнале з. де Ма»Ь. 11 (1846), 41-64.
В этой рабате Л. Дюпре исследовал также более общие процедуры »с предварительным просмотром", предложенные Ж. Бине (3. В»пе»). 32. (Ь) Член К»(хл,..., х~~-л) К»-» (х»лл»,..., х»»»„) соответствует тем словам длиной ги+ и в азбуке Морзе, для которых тире находится в т- н (т+ 1)-й позициях; другой член соответствует противоположному случаю. (Можно также воспользоваться упр. 2. Более общее тождество К э„(хл,...,хы»„)К»(х л»,...,х»») = К,„ь»(хл,..., х„»»)К (х„э»,..., х л ) + (-1)»К л(хм...,х л)К„-»-»(х ь»чз,...,х э ) также опъбликовано в работе Л.
Эйлера.) 33. (а) Новыми представлениями'являются х = т/д, у = (и — ги)/д, х = у = д = Всд(т, и — т) для -'п < т < и. (Ь) Отношение (и/х') — у < х < и/х' определяет х. (с) Подсчитаелг все элементы х, которые удовлетворяют условиям (Ь). (д) Пару целых чисел х > у > 0 с х з у можно записать единственным образом в виде х = К (хл,...,х ), у = К»(хь ..,хы»), где г» > 2 и т > 1; здесь у/х = //х,„,...,х»//. (е) Достаточно показать, что 2 л<»<„7» Т(У, и) = 2(и/2) + б(и); это следует из упр. 26. 34. (а) Деление х и у на Вод(х,у) дает д(и) = 2 „5(и/д).
Применим результат упр. 28, (с) н используем условие симметрии между переменными со штрихом и без него. (Ь) Для фиксированных у н ! представления с хд > х' обладают свойством х < л/идд; следовательно, имеется 0(~/и»!/у) таких представлений. Сумл»ируем теперь при условии 0 < Г < у < л/и/д. (с) Если з(у) есть данная сумма, то, к примеру, ~з»„з(д) = у(Н»„— Н») = !с(у); отсюда»(у) = 3 з „!с(у/д). Далее /г(у) = у1п2 — -' + 0(1/у). (с!) 2',„" с Эт(у)/у~ = 2 „" с[а!у] р(с1)/ус! = т,ы<„>с(с4)/гс1~. (Аналогично Я", а,(у)/уг = 0(1)) (е) ~ ~", т П(к)/Лг = б/Яг+ 0(1/и) (см УпР 452 10(6)), а 2 ь", П(Л) !об Л/Лг = 0(1) Следовательно, при с1 > 1 имеем Ь,с(п) = п((3 !и 2)/з г) 1п(п/с1) + 0(п) для с1 > 1.
В итоге Ь(тс) = 22„, с„тс(сГ)Ис(п/сс1) = Цб!п2)/яг)п(!пп — ~ — 2 ') + 0(па с(п) ), где остаточные суммы равны 2„= 2 сС„>с(сГ)!п(ссс)/гсс = 0 и 2 = 2„,„П,Н(сг)1пс/ссс = А(с1)/с1. [Известно, что т с(п) = О(!об!обп); см, работу Харди (Наес!у) и Райт (1уг>81>с) Ап 1>с!гас>пессоа со СЛе ТЛеог> оГ.таптЬегз, 522.9.] 35. См. Ртос. Вас, Асас). Яст'. 72 (1975), 4720-4722. М. Л. В. Пайтвэй (М. Е. 'т1 Р!гтестау) и К.
М. А. Кэстл (С. М. А. Саз11е) [Виру 1лзг. Масб. 'апс/ сгз Аррбсасюлз 24 (1988), 17-20] нашли убедительное, но требующее больших усилий эмпирическое свидетельство того, что сумма частичных отношений равна г 1 18(!и 2) б 4г +1 "— 1 — 2.542875 + 0(п Нг), 36. Выполняя алгоритм в обратном порядке и полагая, чта на шаге С2 для заданного значения й выполняется Ьг — 1 делений, получаем минимальное число и„, для которого бед(иь„.т,...,иэ) = Рсс...Рс, и ив ш Рсс . Рс„сРс,-с (помодулюбсд(итьс,...,и )); здесь все й > 2, !с > 3 и !с + -!-Г„с — — А'+ и — 1. При этих условиях можно минимизировать иь = Рст Рс„сс приняв Сс = 3, 1г = = С -г = 2, и = 2Ря- ег Если условиться также„что ис > иг » и, решение ис = 2Рл- тг + 1, иг = = и„с — — 2Рл- тг, и„= 2Рл „эг имеет минимум ис.
[См. САСМ 13 (1970), 433-436, 447-448.] 37. См. Рсоа Атег. Масб. Бос. Т (1956), 1014 — 1021; см. также упр. 6.1-18. 38. Положим тп = [и/ф], так что тп/и = ф '+с = //ас, аг,, //, где 0 < е < 1/и. Пусть Л— минимальное значение, такое, что ос > 2; тогда (ф' "+( — 1) Рь сс)/(ф — ( — 1)эРьс) > 2, отсюда Л четно и ф г = 2 — ф < ф~Рьэгс = (фг" г — ф )с/чГЬ. [Апа, Ро!ол. Ма!Л.
1 (1954), 203-206.] 39, Минимум 287, ни одна дробь со знаменателем < 287 не прине,ллежит //2, 1,95// = 96/287 ш .33449477, как и интервалу [3335...3345] = ]//2, 1, 666// .. //2, 1,94, 1, 1, 3//]. Чтобы решить основной вопрос для дроби с меньшим знаменателем в промежутке [а..Ь] в случае, когда 0 < а < Ь < 1, учтем, что в обозначениях, принятых для представления правильных цепных дробей.
будет иметь место соответствие //х с, хг,... // < //ус, ут,... // тогда и только тогда, когда ( — 1)тх, < ( — 1)тут для наименьших >, таких, что х, ЗЕ у, причем символ "со" помещается за последним частичным отношением рационального числа. Такилс образом, если а = //хс. хг,... // н Ь = //ус, уг,...
// и если > минимально прн х ф у,, в промежутке [а ..Ь] дробь принимает вид с = //хс,...,х, с, х,...,г //, где //г,,, х // лежит между //хт, х,тс,... // н //ут, у>ес,... // включительно. Положим, что К-с = О. Знаменатель т с(хс ' ' ' т с) — т;с (хт се ) + Кт-г(хс, хт — г)К вЂ” >(хттс,..., г ) числа с будет мнтснгсассьстьсм прн тп = > и г, = (> нечетно. ю у -'; [у „, ~оо] [х>ес фоо]). [Другой способ вывода этого метода основан на теории, изложенной в следующем упражнении.] 40. Можно доказать по индукции, что в каждом узле выполняется р,щ — Р~Ч, = 1, т. е. числа р~ и ф являются взаимно простыми.
Поскольку р/Ч < р /Ч, то р/Ч < (р+Р )/(Ч+Ч ) < р /Ч . Кроме того, понятно, что метки на всех левых вершинах ветвей для чисел р/Ч меньше этих значений р/Ч, в то время как метки на всех правых вершинах больше этих значений. Поэтому каждое рациональное число может появиться в качестве метки не более одного раза. Теперь остается показать, что каждое рациональное число должно обязательно появиться. Если р/Ч = //ап..., а„1//, где каждое из а; — положительное целое число., то по индукции можно показать, что узел с меткой р/Ч находится посредством перемещения а~ раз влево, затем — перемещения аг раз вправо, аг раз влево и т. д. [Впервые последовательность меток на сформированных уровнях исследовалась М. А. Штерном (М. А.
8сегп) в Сге!1е 66 (1858), 193 — 220, хотя в этой работе связь с бинарными деревьями не нрослежнвается. На получение всех возможных дробей при помощи интерполирования дроби (р+р')/(Ч+Ч') между соседними элементами р/Ч и р'/Ч' обратили внимание позже. Относящиеся к решению этой задачи важные идеи были опубликованы Даниэлем Швентером (Пап!е! БсЬневгег) [Ре!!с!те РЛуз!со-МаСЛетаС!сж (КбгпЬегб, 1636), Рэгт 1, РгоЫесп 87; Сеошесг!а Ргасс!са, Згс! ес!!с!оа (1641), 68; см.
М. Сап!от, Севой!сЛСе бег Масй, 2 (1900), 763-765) и Джоном Ъоллисом (,1оЬп сй!а!!!э) в его книге Тгеас!эе ог А!бебга (1685)„СЬарсегв 10-11. К. Гюйгенс (С. Наубепэ) использовал эти идеи при конструировании приводов для своего планетария [см. Пеэспрс!о А а!ослаб Р!алесагй (1703), опубликовано после его смерти[. Лагранж в работе Н!зс.
Асад. Ясб 23 (Вег!!и, 1767), 311-352, 324, и в дополнении к переводу на французский язык алгебры Эйлера (1774), 618-420, привел полное описание этой идеи. См. также упр. 1.3.2-19; А. Вгосог, Нес'ае СЛюлошбтг!Чае 6 (1860), 186 — 194; П. Н. ЬеЬшег, АММ 36 (1929), 59-67.) 41. Действительно, правильные цепные дроби для чисел, записываемых в общем виде 1 (-1)" (-1)" — — — + + Р! + !и!г! обладают интересной закономерностью, основанной на тождестве Ки+и+>(х~ ° .,х -с,х — 1,1,У 1,.У -п,уг) — х ы Кы - ~ (х и ° . °, х и — ) ) Ки ( у °, ус ) + (-1)и!с +и(хп . °, х — и О, — У, -У -и ..,, — У~).
Наибольший интерес это тождество представляет для случая, когда у„= х~ с, у -~ = -г и т. д., так как К„е~(гп..., гы О, гь+ц..., ги) = Ки с(гс,, гь с, гь + гьтп гээг,..., ги), В частности, если ри/Чи ии К„~(хг,...,х„)/К (хп...,х ) = //хс,...,хи//, то Ри/Ч + ( — 1) "/Чгг = //х„..., х„, г — 1, 1, х„— 1, хи и..., х,//. Заменяя последовательность //хп..., х„// последовательностью //хп, .., х„мхи — 1, 1//, можно управлять формированием знака (-1)". Например, для частичных сумм первого ряда получаем следующие цепные дроби четной длины: //1,1//; //1,1,1,1,0,1// = //1,1,1,2//; //1,1,1,2,1,1,1,1,1,1//; //1,1,1,2,1,1, 1, 1, 1, 1, 1, 1, О, 1, 1, 1, 1 . 1, 2, 1, 1, 1 // = // 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 1 // .
Далее последовательность упорядочивается и подчиняется простой закономерности . Для случаи, когда и — 1 = 209+ г при 0 < г < 20, найдем, что частичное отношение а может быть легко вычислено, если г = О, 2,4,5,6, 7,9, 10, 12, 13, 14, 15, 17 или 19; если г = 3 или 16, 1+ (д+ г) пюб2, если г = 8 или 11; 2 — Ию если г = 1; 1+ «ч+~~ если г = 18. Здесь И„ — "последовательность дракона", определяемая правилами 4~ = 1, Иэ„ = д„, Ы~ .ь~ — — О, 44 ьз = 1. Кривая дракона (рассматривалась в упр. 4.1-18) поворачивается вправо на и-м шаге тогда и только тогда, когда Ы„ = 1.
Числа Лиувилля при 1 ) 3 равны //1 — 1, 1+ 1, 1~ — 1, 1, 1, 1 — 1, 1'э — 1, 1, 1 — 2. 1, 1, 1 — 1, 1+ 1, 1 — 1, 1™ — 1,... //. и-е частичное отношение а„зависит от последовательности дракона, элементы которой представимы по и шоб 4 в следующем виде: если и шод 4 = 1, то частное равно 1 — 2+о ~+((и/2) шоб 4), если и пюс1 4 = 2, то оно равно 1+2 — И ьт — ((и/2) пюс(4); если п шоб 4 = О, то оно равно 1 или 1"д" Π— 1 в зависимости от того, будет ли Н = 0 или 1, где число 5 — наибольшая степень 2, которая делит и; если и шод 4 = 3, то оно равно 1~ М П вЂ” 1 илн 1 в зависимости от того, равно ли И„чч = 0 или 1, где число )г— наибольшая степень 2, которая делит и+1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
