Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 36
Текст из файла (страница 36)
Аналогично М»» = (хь».»»хь+з, ",хм) н т. д. Процесс легко визуализируется в двоичной системе счисления, как показано в следующем примере. Пусть М» содержит тз элементов (с учетол» кратности); тогда»п» < 2Х вЂ” Х, поскольку 5, имеет не более 2Х элементов и разбито на 1+ 1 непустых мультимножеств. Из (38) видно, что В качестве примера такой детализированной конструкции рассмотрим звездную цепочку 1, 2, 3, 5, 102 20. 23. для которой з = 3, г = 6, 21 = 3, Х = 3.
Получим следуюншй набор мультимножеств. (2ХО, Иы -, 2ХО): (ао, ам..., аб ): (Моз, М4з, Мбз) 2 (Мог.ЛХ4г2 ",Мбг): (М „М„2...,М,): ()2ХОО, М»02 2 вХОО): зо ез =О, тз =1 ег = 1, тг = 1 е2 =22тз =1 Мз 3Хг Мз )аб ео =4 то =2 Яз Бг 5з 5» бз Юб Таким образом, М»о = (2, 2) н т, д. Из построения можно увидеть2 что 424 является наибольшим элементом Яп следовательно, (4) 242 е 2«Х20 Наиболее важная часть этой структуры следует из (40) и одним из непосредственных ее следствий является лемма К. Лемма К.
Если Мб и ЛХ„б оба содержат общее число х, то -тб < (е — е,) — (2Մ— 2Х») < ту. $ (,12) Хотя лемма К и ие выглядит особо "сильной", она утверждает (когда тз и гпб обоснованно малы и когда МО содержит общий с М„„элемент), что количество удвоений между шагами и и з примерно равно разности между показателями еб и ез. Это производит впечатление некоторой регулярности в адаптивной цепочке и наводит на мысль о том, что можно доказать результат, аналогичный приведенной выше теореме В, а именно — что 1'(и) = ео + с, если показатели степеней еХ достаточно различны.
Следующая теорема показывает, как это можно сделать. Теорема Н (Ж. Нэпзеп, СгеИе 202 (1959), 129-136). Пусть и = 2" + 2" + ° ° ° + 2"', где со >е1 ». е» >О. Если со > 2ез+ 2.27ЦХ-1) и е; 4 > е»+2т для 1 < з < з, (43) где т = 2(з.гги' гй — 1, то 1'(и) = ео + а Доказательство. Положим, что З > 2, поскольку результат теоремы при Х < 2 нстинен без наложения ограничений на е. Допустим, что имеется звездная цепочка 1 = ао < аз « а„= и для и с г < ео + З вЂ” 1. Пусть ее структуру отражают целые числа 2Х, Х, 2ХО, ..., 2(„и мультимножества МО н 54, как было определено выше. Согласно следствию из теоремы А известно, что Х < 13.271(з — 1)).
Поэтому значение т является настоящей верхней гранью числа элементов зпз каждого мультимножества М . В сумме ( г'2)2(З 2)2 2(г 2') не будет переносов из члена, соответствующего М,", к члену, соответствующему Мщ О, если рассматривать ее как выполняющуюся в двоичной системе счисления, поскольку е достаточно далеко разнесены (см. (40)). В частности, сумма всех членов лля у ф 0 не даст переносов к членам для у = О, так что мы должны получить а; > ~~ 2*>2"<"), 0<1<г.
(44) ьеми Для доказательства теоремы Н необходимо показать, что в некотором смысле 1 дополнительных степеней и должны размещаться "по одной", чтобы можно было определить, на каком шаге каждый из этих членов, по существу, включается в эддитивную цепочку. Пусть у представляет собой число между 1 и 1. Поскольку Меу пусто, а ММ = Мз не пусто, можно найти первый шаг з, для которого Мб не пусто. Из способа, которым определяется М,, известно, что шаг 1 ие является удвоением: а, = а; ~ + а„для некоторого и < 1 — 1. Также известно, что все элементы МВ являются элементами 5„. Докажем, что а„должно быть относительно мало по сравнению с а,, Пусть ху является элементом Моь Тогда, поскольку х. б 5„, существует е, для которого х е М„,.
Отсюда следует, что (45) А — Аи ) гп~ т. е. между шагами и и 1 встречается как минимум гп+ 1 удвоений: если 4-а~„< т, лемма К гласит, что )е — е,) < 2гл; следовательно, е = у. Однако это невозможно, потому что М„у пусто в соответствии с нашим выбором шага 1. Все элементы 5 не превышают е1+ 41 — И. Действительно, если х б 5„С 5; н х > е~ + 4 — 4, то х б М„е и х е М;е согласно (40), так что из леммы К следует, что )4 — и'„! < т,. а это противоречит (46). Значит, это рассуждение доказывает, что М е не имеет общих с 5„элементов и Мб це = Мю, Из (44) имеем а, 1 > 2"~" ~. и поэтому шаг 1 является малым шагом.
Теперь выведем ключевой факт во всем этом доказательстве: все элементы 5„ явлнютсл элементамп М,е. Действительно, если это не так, пусть х будет элементом 5„, таким;что х ф М„е. Поскольку х > О, из (40) следует, что е1 > 4 — Н„и ее = У + И вЂ” э < 2.271э + 4 < 2.271(1 — 1) + е1 + Ы . Из гипотезы (43) получаем, что с1„> ем Однако Н„Е 5„в соответствии с (41) и не может находиться в ЛХ;е.
Поэтому Ыь < е~ + 4 — 4 < ем что приводит к противоречию. Возвращаясь к элементу х из Мб, получаем, что х б М„„. К тому же было доказано, что е = О. Поэтому, используя (40) еще раз, получим ее+4~ — Ы) хт ) со+Ни — 4 — п1о.
Теперь для всех у = 1, 2, ..., Г определено число х~, удовлетворяющее (46), н малый шаг 1, на котором в аддитнвную цепочку вводится член 2'~. Если у ~ У, шаг 1, на котором это происходит, не может быть одним и тем же и для у, и для у'. Из (46) следует, что!ху -х ) < т, в то время как элементы М; и М; должны отличаться более чем на гп, поскольку еу и еу существенно различны. Мы вынуждены заключить, что цепочка содержит как минимум ! малых шагов, но зто приводит к противоречию. ! Теорема Р (В. Хансен (%. Напоен)). Ц2" +ху) < А+и(х)+и(у) — 1, если Л(х)+Л(у) < А.
(47) Доказапзельспюо. Адаптивная цепочка (в общем случае нс звездная) может быть построена путем комбинирования бинарного метода и метода множителя. Пусть х = 2"' + + 2 " и у = 2ю + + 2»", где х1 » х„> 0 и у1 » . у„> О. Первые шаги цепочки представляют собой последовательные степени 2, пока не достигнуто значение 2л з'; между зтими шагами в соответствующих местах вставляются дополнительные значения 2'"-' + 2'", 2»"-' + 2'"-' + 2'", ... и х, По достижении цепочкой 2л "' + х(2"' "' + + 2м-' "') продолжаем построение, добавив х и удвоив результирующую сумму у; — уг ы раз, и получаем 2"- "'+х(2 — '+" +2" ' '), Если зто построение выполнено для з = 1, 2,, и, приняв для удобства, что у,»1 — — О, получаем требовавшуюся алдитивную цепочку для 2л +:гу.
! Теорема Г позволяет найти значения я, для которых Цп) < 1*(и), поскольку теорема Н дает точное значение !" (и) в некоторых случаях. Например, пусть х =- 2'о'в+1 у = 2хоз'+1 и пусть и 2щоз+ „2щоз+2золз+2еозз+21оы+1 Согласно теореме г имеем Цп) < 6106. Однако применима и теорема Н с пз = 508, а зто доказывает, что 1*(п) = 6107.
Обширные компьютерные вычисления показали, что и = 12509 является наименьшим значением с Цп) < !'(и). Для него нет более короткой звездной цепочки, чем последовательность 1, 2, 4, 8, 16, 17, 32, 64, 12$, 256, 512, 1024, 1041, 2082, 4164, $328. 8345, 12509. Наименьшее и с и(п) = 5 и Цп) »4 !*(и) — 16537 = 2'~ + 9. 17 (см.
упр..15). Ян Ван Дннвен (,1ап кап 1,еепнеп) обобщил теорему Н, показав, что ! (х2'")+Ф < 1*(йп) < !'(52")+ео-ез+! для всех фиксированных Й > 1, если показатели степени ео » . е~ достаточно различны (Сге!!е 295 (1977). 202-207). Некоторые предположения.
Хотя, на первый взгляд, разумно предположить, что Цп) = ! (и), мы убедились, .что оно неверно. Другое правдоподобное предположение, впервые сделанное А. Голардом (А. Ооп1агб) и "доказанное" Э. де Жонкизресом (Е. Ое Зопс~шеггя) в 1.ЧпзегшеН. Иез таНь 2 (1895), 125" 126, состоит в том, что Ц2п) = 1(п)+1.
Удвоение настолько зффектнвно, что не представляется возможным, чтобы могла существовать некоторая более короткая цепочка для 2п, чем цепочка, получаемая в результаге добавления удвоения к кратчайшей цепочке для и. Однако компьютерные вычисления показывают, что зто предположение также неверно, поскольку Ц191) = Ц382) = 11. (Не так трудно найти звездную цепочку длиной 11 для 382, например 1, 2, 4. 5, 9, 14, 23, 46, 92, 1$4, 198, 3$2.
Число 191- — минимальное из чисел, таких, что!(и) = 11, и доказательство того, что !(191) > 10, вручную представляется весьма нетривиальным. Так, компьютерное доказательство автором этого факта с использованием метода отката, который будет рассмотрен в разделе 7.2.2, требует детального изучения 948 случаев.) Наименьшими четырьмя значениями и, такими, что 1(2п) = !(и), являются и = 191, 701, 743, 1111.
3. Г. Тюрбер доказал в Расйбс з. 54а!!ь 49 (1973), 229-242, что третье из этих чисел является членом бесконечного семейства таких и, а именно — 23 2" +7 для всех й > 5. Представляется разумным предположение о том, что ((2п) > 1(и), но даже оно может оказаться ложным. Кевин Р, Хебб (Кеэбп К, НеЬЬ) показал, что 1(п) — 1(шп) может быть сколь угодно большим при всех фиксированных целых числах т, не являющихся степенямн 2 (Л1обсеэ Лшег. Май.
Яос 21 (1974), Л-294]. Наименьшим значением, для которого Е(пш) < ((и), является !((21э+1)/3) =- 15. Обозначим через с(г) нанменыпее значение и, такое, что !(и) = г, Вычисление !(и) представляется более трудным для этой последовательности и, начинающейся следующим образом. Для г < 11 значение с(г) приблизительно равно с(г — 1) + с(г — 2), и этот факт привел ряд исследователей к мысли о том, что с(г) растет, как функция й'.
Однако из результата теоремы 0 (с и = с(г)) вытекает, что г7!8с(г) -э 1 при г -+ со. Значения, перечисленные здесь для г > 18, были вычислены Ахимом Фламмеикампом (АсЬпп Р!а1пшеп)шп1р), кроме вычисленного Даниэлем Блейхенбахером (Пап!е! В1е!сЬепЬасЬег) значения с(24). Фламменкамп заметил, что с(г) хорошо аппроксимируется формулой 2" ехр(-йг~!8 г) для 10 < г < 27, где д близко к !п 2.
Это вполне согласуется с верхней гранью (25), Некоторые исследователи одно время полагали, что с(г) всегда представляет собой простое число (исходя нз метода множителя); однако с(15), с(Г8) и с(21) делятся на 11. Возможно, любое предположение об алдитнвных цепочках неверно! Табуляция значений 1(п) показывает, что эта функция на удивление гладкая; например, для всех и в диапазоне 1125 < и < 1148 значение функции !(и) = 13. Компьютерные вычисления показали, что таблица 1(п) может быть построена для значений 2 < и < 1000 с использованием формулы (48) 1(п) = ш!п(1(п — 1) + 1, !я) — 5„, где 1„= оо, если и — целое число, в противном случае 1„= 1(р) + 1(п/р), если р — наименьшее простое число, делящее и; и наконец, 5„= 1 для и из табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
