AOP_Tom2 (1021737), страница 145
Текст из файла (страница 145)
По достижении цепочкой 2~ "' + х(2"' " + . + 2" -' з') продолжаем построение, добавив х и удвоив результирующую сумму у, — уьь1 раз. и получаем 2 з-з,ч, + х(2ю-з,-г + ., + 2м — зьы) Если зта построение выполнено для ! = 1, 2, ..., о, приняв для удобства, что у ег = О, получаем требовавшуюся аддитивную цепочку лля 2 + ху.
1 л Теорема г позволяет найти значения п, для которых !(и) < 1*(и), поскольку теорема Н дает то шое значение !" (и) в некоторых случаях. Например, пусть х = 2гош, 1 у 2гозг „1 и пусть и 2шоз + 2юоз + 2зозз + 2гозг + 2гогв + ! Согласно теореме Е имеем !(и) < 6106. Однако применима и теорема Н с' гп = 508, а эта доказывает, что !'(и) = 6107. Обширные компьютерные вычисления показали, что п = 12509 нвляется наименьшим значением с !(и) < !'(п). Для него нет более короткой звездной цепочки, чем последовательность 1, 2, 4, 8, 16, 17, 32, 64, 128, 256, 512, 1024, 1041, 2082, 4164, 8328, 8345, 12509.
Наименыиее п, с и(п) = 5 и !(и) ф !*(п)--. 16537 = 2ы + 9. 17 (см. упр,.15). Ян Ван Лиивен (.1ал сап 1,еепнеп) обобщил теорему Н, показав, что !'(й2'") + ! < !'(йп) < !*(й2"') + ео — ез + г для всех фиксированных у > 1, если показатели степени ео » ег достаточно различны (Сге!!е 295 (1977), 202-207). Некоторые предположения. Хотя, на первый взгляд, разумно предположить, что !(и) = 1*(п),мы убедились, что оно неверно. Другое правдоподобное предположение, впервые сделанное А.
Голардом (А. Сап!агб) и "доказанное" Э. де жанкиэресом (Е. Ое Запс!шстез) в 1ЧпсегпгеЯ. г!ев таВь 2 (1895), 125-126, состоит в том, что !(2п) = !(п)+1. Удвоение настолько эффективно, что не представляется возможным, чтобы могла существовать некоторая более короткая цепочка лля 2п, чем'цепочка, получаемая в результате добавления удвоения к кратчайшей цепочке для а.
Однако компьютерные вычисления показывают, что это предположение также неверно, поскольку !(191) = !(382) = 11. (Не так трудно найти звездную цепочку длиной 11 для 382, например 1, 2, 4, 5, 9, 14, 23, 46, 92, 184, 198, 382. Число 191 — минимальное из чисел, таких, что 1(п) = 11, и доказательство того, что 1(191) > 10, вручную представляется весьма нетривиальным. Так, компьютерное доказательства автором этого факта с использованием метода отката, который будет рассмотрен в разделе 7.2.2, требует детального изучения 948 случаев.) Наименьшими четырьмя значениями и, такими., что 1(2п) = 1(п), являются и = 191, 701, 743, 1111. Э.
Г. Тюрбер доказал в Рас16с Х АХаГЛ. 49 (1973), 229-242, что третье из этих чисел является членом бесконечного семейства таких и, а именно . — 23 2ь+7 для всех 1г > 5. Представляется разумным предположение о том, что 1(2п) > 1(п), но даже оно может оказаться ложным. Кевин Р. Хебб (Кет1п В. НеЬЬ) показал, что 1(п) — 1(тп) может быть сколь угодно большим при всех фиксированных целых числах т, не являющихся степенями 2 (Хобсеа Ашег. МаГЛ. Яос. 21 (1974), А-294). Наименьшим значением, для которого 1(тп1 < 1(п), является 1((2~э + 1)/3) = 15. Обозначим через с(г) наименьшее значение п, такое, что 1(п) = г.
Вычисление 1(п) представляется более трудным для этой последовательности и, начинающейся следующим образом. Для г < 11 значение с(г) приблизительно равно с(г — 1) + с(г — 2), и этот факт привел ряд исследователей к мысли о том, что с(г) растет, как функция фг. Однако из результата теоремы Р (с п = с(г)) вытекает, что г/18с(г) -э 1 при г -+ со.
Значения, перечисленные здесь для г > 18, были вычислены Ахямом Фламменкампом (АсЬпп Р1апгшепМашр), кроме вычисленного Даниэлем Блейхенбахером (Вап1е( В1е1сЬепЬасЬег) значения с(24). Фламменкамп заметил, что с(г) хорошо аппроксимируется формулой 2' ехр( — Ог/18 г) для 10 < г < 27, где 9 близко к 1п 2. Это вполне согласуется с верхней гранью (25). Некогорые исследователи одно время полагали, что с(г) всегда представляет собой простое число (исходя из метода множителя): однако с(15), с(18) и с(21)' делятся на 11.
Возможно, любое предположение об аддитивньж цепочках неверно! Табуляция значений 1(п) показывает, что эта функция на удивление гладкая; например, для всех и в диапазоне 1125 < и < 1148 значение функции 1(п) = 13. Компьютерные вычисления показали, что таблица 1(п) может быть построена для значений 2 < и < 1000 с использованием формулы (48) 1(п) = ппп(1(п — 1) + 1, 1 ) — б„, где 1„= ж, если и — целое число, в противном случае 1„= 1(р) +1(п/р), если р — наименьшее простое число, делящее и; и наконец, б„= 1 для и из табл. 1, в противном случае — 5„= О.
г с(г) 1 2 2 3 3 5 4 7 5 11 6 19 7 29 8 47 9 71 г с(г) 10 127 11 191 12 379 13 607 14 1087 15 1903 1б 3583 17 6271 18 11231 г с(г) 19 18287 20 34303 21 65131 22 110591 23 196591 24 357887 25 685951 26 1176431 27 2211837 Таблица 1 ЗНАЧЕНИЯ и ДЛЯ СПЕЦИАЛЪНЫХ АДДИТИВНЫХ ЦЕПОЧЕК Пусты!(т) обозначает количество решений и уравнения !(и) = т. В следующей таблице перечислено несколько первых значений этой функции согласно Фламменкампу. т сС(т) т сс(т) т с1(т) т сс(т) т с((т) 1 1 6 15 11 246 16 4490 21 90371 2 2 7 26 12 432 17 8170 22 165432 3 3 8 44 13 772 18 14866 23 303475 4 5 9 78 14 1382 19 27128 24 558275 5 9 10 136 15 2481 20 49544 25 1028508 Конечно, с((т) должно быть возрастающей функцией от т, но не существует ясного способа доказательства этага кажущегосн таким простым утверждения и тем более — определения асимптотического роста г1(т) для больших т.
Наиболее знаменитая проблема, связанная с аддитивными цепочками и все еще нерешенная,— гине?пега Шольца-Брауэра, гласящая, что !(2" — 1) < и — 1+!(и). (49) Компьютерные вычисления показывают, что в действительности в (49) выполняется равенство для 1 < и < 24. Вычисления, проведенные Э. Г.
Тюрбером (Иэсгеге МаСЬ. 16 (1976), 279 — 289), показали, что равенство справедливо также для и = 32. Множества исследований алдитивных цепочек посвящено попыткам доказать (49). Аддитивные цепочки для чисел 2" — 1, которые имеют так много единиц в их двоичном представлении, вызывают особый интерес, поскольку они являются наихудшим случаем для бинарного метода. Арнольд Шольц (АгпаЫ ЯсЬо!г), придумавший название "алдитивные цепочки", поставил в 1937 году задачу (49) [3аЬгеэЬегссЬС с!ег с!еасэсЬеп МасЬешасйег-)теге!и!Впп8, Абсе!!пп8 П, 47 (1937), 41-42); Альфред Брауэр (А!(тес! Вганег) в 1939 году доказал, что (50) 1'(2ь — 1) < и — 1+1" (п). Теоремы Хансена показывают, чта ((п) может быть меньше, чем !'(и), так что, определенно, потребуется много работы, чтобы доказать или опровергнуть (49).
В качестве шага в этом направлении Хансен определил концепцию со-цепочки, которая лежит 'между"!- и !*-цепочками. В !о-цепочке некоторые элементы подчеркнуты; условие заключается в том, что а, = а, + аь, где а — наибольший подчеркнутый элемент, меньший, чем аь В качестве примера !о-цепочки (конечно, не минимальной) рассмотрим 1„2, 4, 5, 8, 10, 12, сд. (51) 23 163 43 165 59 179 77 203 83 211 107 213 149 227 229 319 233 323 281 347 283 349 293 355 311 359 317 367 371 413 373 419 377 421 381 423 382 429 395 437 403 451 453 553 455 557 457 561 479 569 503 571 509 573 551 581 599 645 707 741 611 659 709 749 619 667 ?11 759 623 669 713 779 631 677 715 787 637 683 717 803 643 691 739 809 813 849 825 863 835 869 837 887 839 893 841 899 84э 901 903 905 923 941 947 955 983 Легко убедиться, что разность между каждым элементом и предшествующим ему подчеркнутым элементом принадлежит цепочке.
Обозначим через (е(и) минимальную длину (е-цепочки для и. Ясно, что 1(и) < (е(и) < 1'(и). Цепочка, построенная в теореме Р, является 1е-цепочкой (см. упр. 22); следовательно, имеем 1е(и) < 1" (и) для некоторого и. Неизвестно, выполняется лн равенство 1(и) = (е(и) во всех случаях. Если оно истинно, то предположение Ш1ольцБрауэра должно быть справедлива вследствие еще одной теоремы Хансена. Теорема С. 1е(2" — 1) < и — 1+ 1е(и).
Доказатиельстиео. Пусть 1 = ае, а,, ..., а„= и — 1е-цепочка минимальной длины для и и пусть 1 = Ье, Ьы..., 6~ — — и — последовательность подчеркнутых элементов. (Можно считать, что и подчеркнуто.) Тогда (о-цепочку для 2" — 1 можно получить следующим образом. а) Включить (е(и) + 1 чисел 2сч — 1 для 0 < 1 < г, подчеркнуть их тогда и только тогда, когда а, будет подчеркнуто. Ь) Включить числа 2'(2ь' — 1) для 0<7 <1 и 0 <1<6.+1 — 6 и подчеркнуть их все.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
