не будет переносов из члена, соответствующего Mij, к члену, соответствующему Mj(jv.i), если рассматривать ее как выполняющуюся в двоичной системе счисления, поскольку е достаточно далеко разнесены (см. (40)). В частности, сумма всех членов для j фО не даст переносов к членам для j = О, так что .мы должны получить

ai> >2("<), 0<г<г. (44)

Для доказательства теоремы Н необходимо показать, что в некотором смысле t дополнительных степеней п должны размещаться "по одной", чтобы можно было определить, на каком шаге каждый из этих членов, по существу, включается в аддитивную цепочку.

Пусть j представляет собой число между Int. Поскольку Mqj пусто, а Mrj=Mj не пусто, можно найти первый шаг i, для которого Mij не пусто.

Из способа, которым определяется Му-, известно, что шаг г не является удвоением: Ot = Oj-i + йи для некоторого и < i - 1. Также известно, что все элементы Mij являются элементами Su- Докажем, что а„ должно быть относительно мало по сравнению с Oj.

Пусть Xj является элементом Mij. Тогда, поскольку Xj € Su, существует v, для которого Xj G Muv Отсюда следует, что

di-du> т, (45)

т. е. между шагами и и i встречается как минимум т+1 удвоений: если di - du < т, лемма К гласит, что ej - el < 2m; следовательно, v = j. Однако это невозможно, потому что Muj пусто в соответствии с нашим выбором шага г.

Все элементы 5и не превышают ei + di - d. Действительно, если х £ Su С Si и X > в! + di - d, то X е Мио п X е Mio согласно (40), так что из леммы К следует, что \di - du\ < m, а это противоречит (45). Значит, это рассуждение доказывает, что Mjo не имеет общих с Su элементов и M(j i)o = Mjq. Из (44) имеем Ot-i > 2-(" и поэтому шаг i является малым шагом.

Теперь выведем ключевой факт во всем этом доказательстве: все элементы Su являются элементами Мо Действительно, если это не так, пусть х будет элементом 5и, таким,-что X Мио- Поскольку а; > О, из (40) следует, что ei > d - du и

= f + d- s< 2.271s + d< 2.271(t - 1) -- ei -- du.

Из гипотезы (43) получаем, что du > ei. Однако du £ Su в соответствии с (41) и не может находиться в Mjo. Поэтому du < ei + di - d < ei, что приводит к противоречию.

Возвращаясь к элементу Xj из Mij, получаем, что Xj € Muv К тому же было доказано, что v = 0. Поэтому, используя (40) еще раз, получим

ео + du - d> Xj > eo + du- d- mo. (46)

Теперь для всех j = 1, 2, t определено число Xj, удовлетворяющее (46), и малый шаг г, на котором в аддитивную цепочку вводится член 2. Если j ф j, шаг i, на котором это происходит, не может быть одним и тем же и для j, и для j. Из (46) следует, что \xj-Xji < m, в то время как элементы My и Му должны отличаться более чем на т, поскольку Cj и Cji сушественно различны. Мы вынуждены

заключить, что цепочка содержит как минимум t малых шагов, но это приводит к противоречию.

Теорема F (В. Хансен (W. Hansen)).

1{2 + ху)<А + и{х) + и{у)-1, если Х{х) + Х{у) < А. (47)

Доказательство. Аддитивная цепочка (в общем случае не звездная) может быть построена путем комбинирования бинарного метода и метода множителя. Пусть а; = 24- • • • + 2" и 2/ = 2 + • • • -I- 2", где xi > • • • > > О и 2/1 > • • • > 2/ > 0.

Первые шаги цепочки представляют собой последовательные степени 2, пока не достигнуто значерше 2"*"; между этими шагами в соответствующих .местах вставляются дополнительные значения 2"- + 2", 2"- + 2"- + 2", ... их.

По достижении цепочкой г"" + х{2уУ +----h 2"-i") продолжаем построение,

добавив X и удвоив результирующую сумму 2/г - yt+i раз, и получаем

2A-j/,4-! а;(2~+ + • • + 2"+).

Если это построение выполнено для i = 1, 2, v, приняв для удобства, что 2/t;+i = О, получаем требовавшуюся аддитивную цепочку для 2"* + ху.

Теорема F позволяет найти значения п, для которых 1{п) < 1*{п), поскольку теорема Н дает точное значение 1*{п) в некоторых случаях. Например, пусть х =

п - 21° +ху = 21° + 2° + 22°32 4- 2i°i6 + 1

Согласно теореме F имеем 1{п) < 6106. Однако применима и теорема Н с m = 508, а это доказывает, что 1*{п) = 6107.

Обширные компьютерные вычисления показали, что п = 12509 является наименьшим значением с 1(п) < 1*{п). Для него нет более короткой звездной цепочки, чем последовательность 1, 2, 4, 8, 16, 17, 32, 64, 128, 256, 512, 1024, 1041, 2082, 4164, 8328, 8345, 12509. Наименьшее п с z/(n) = 5 и 1{п) ф Г(п) -16537 = 2" -h 9 17 (см. упр..15).

Ян Ван Лиивен (Jan vanLeeuwen) обобщил теорему Н, показав, что

r(fc2°)+t < Г{кп) < l*{k2)+eo-et+t

для всех фиксированных К > I, если показатели степени во > • • • > достаточно различны [СгеЛе 295 (1977), 202-207].

Некоторые предположения. Хотя, на первый взгляд, разумно предположить, что 1{п) - 1*{п), мы убедились, что оно неверно. Другое правдоподобное предположение, впервые сделанное А. Голардом (А. Goulard) и "доказанное" Э. де Жонки-эресом (Е. de Jonquieres) в LJntermed. des math. 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, и доказательство того, что /(191) > 10, вручную представляется весьма нетривиальным. Так, компьютерное доказательство автором этого факта с использованием метода отката, который будет рассмотрен в разделе 7.2.2, требует детального изучения 948 случаев.) Наименьшими четырьмя значениями п, такими, что 1{2п) = 1{п), являются п = 191, 701, 743, 1111. Э. Г. Тюрбер доказал в РасШс J. Math. 49 (1973), 229-242, что третье из этих чисел является членом бесконечного семейства таких п, а именно - 23-2*4-7 для всех к > 5. Представляется разумным предположение о том, что 1{2п) > 1{п), но даже оно может оказаться ложным. Кевин Р. Хебб (Kevin R. Hebb) показал, что 1{п) - 1{тп) может быть сколь угодно большим при всех фиксированных целых числах т, не являющихся степенями 2 [Notices Amer. Math. Soc. 21 (1974), А-294]. Наименьшим значением, для которого 1{тп) < 1{п), является /((2 + 1)/3) = 15.

Обозначим через с(г) наименьшее значение п, такое, что 1{п) = г. Вычисление 1{п) представляется более трудным для этой последовательности п, начинающейся следующим образом.

Для г < И значение с(г) приблизительно равно с(г - 1) -Ь с(г - 2), и этот факт привел ряд исследователей к мысли о том, что с(г) растет, как функция ф". Однако из результата теоремы D (с п = с(г)) вытекает, что r/lgc(r) -+ 1 при г -> оо. Значения, перечисленные здесь для г > 18, были вычислены Ахимом Фла.мменкам-пом (Achim Flammenkamp), кроме вычисленного Даниэлем Блейхенбахером (Daniel Bleichenbacher) значения с(24). Фламменкамп заметил, что с(г) хорошо аппроксимируется формулой 2 ехр(-r/lgr) для 10 < г < 27, где в близко к in2. Это вполне согласуется с верхней гранью (25). Некоторые исследователи одно вре.мя полагали, что с(г) всегда представляет собой простое число (исходя из метода множителя); однако с(15), с(18) и с(21) делятся на 11. Возможно, любое предположение об аддитивных цепочках неверно!

Табуляция значений 1{п) показывает, что эта функция на удивление гладкая; например, для всех п в диапазоне 1125 < п < 1148 значение функции 1{п) = 13. Компьютерные вычисления показали, что таблица 1{п) может быть построена для значений 2 < п < 1000 с использованием формулы

Z(n) = min(/(n-l) + l,/„)-<5„, (48)

где In = 00, если п - целое число, в противном случае In = 1(р) + Чп/р), если р - наименьшее простое число, делящее п; и наконец, (5„ = 1 для п из табл. 1, в противном случае - 6п = 0-