Определим теперь две вспомогательные функции для удобства последующего обсуждения:

A(n) = LlgnJ; (6)

i/(n) = количество единиц в двоичном представлении п. (7)

Таким образом, Л(17) = 4, i/(17) = 2. Эти функции могут быть определены следующими рекуррентными соотношениями:

Л(1) = О, Л(2п) = Л(2п + 1) = Л(тг) + 1; (8)

1/(1) = 1, и{2п) = и{п), 1/(2п +1) = 1/(п) +1. (9)

С их помощью можно записать, что бинарные аддитивные цепочки для п требуют ровно Л(п) + 1/(п) - 1 шагов, а (5) принимает вид

1{п) < Л(п) + и{п) - 1. (10)

Специальные классы цепочек. Не теряя общности, можно положить, что аддитивные цепочки возрастающие, т. е.

1 = ао < ai < а2 < < йг = п. (11)

Если два числа из а одинаковы, то одно из них может быть опущено. Можно также переупорядочить последовательность (1) в порядке возрастания и удалить члены, ббльшие, чем п, не нарушая свойство аддитивной цепочки (2). В дальнейшем будем рассматривать только возрастающие цепочки, не оговаривая это соглашение явно.

Теперь удобно определить несколько специальных терминов, относящихся к аддитивным цепочкам. По определению для 1 < г < г

ai = aj+ak (12)

для некоторых jidk, 0<k<j<i. Если это соотношение вьшолняется для более чем одной пары (j, к), полагаем, что j - наибольшее из возможных. Будем говорить, что шаг i цепочки (И) - удвоение, если j = к = i - 1. Тогда а, имеет максимально возможное значение 2aj i, которое может следовать за возрастающей цепочкой 1, ai, ..., flj-i. Если j (но не обязательно к) равно г - 1, будем говорить, что шаг i - звездный шаг {star step). Важность звездных шагов поясняется ниже. И наконец, будем говорить, что шаг i представляет собой малый шаг, если X{ai) = A(ai i). Поскольку a, i < а, < 2д 1, величина A(aj) всегда равна либо A(aj i), либо A(aj i) + 1; отсюда следует, что длина г любой цепочки (11) равна А(п) плюс количество малых шагов.

Эти типы шагов удовлетворяют ряду элементарных соотношений. Шаг 1 всегда представляет собой удвоение. Ясно, что удвоение - звездный шаг, но никогда не малый шаг. За удвоением всегда следует звездный шаг. Кроме того, если шаг i не малый, то шаг г + 1 является либо малым, либо звездным, либо и тем, и другим одновременно. Рассматривая данное утверждение с другой стороны, получим, что если шаг г + 1 не является ни малым, ни звездным, то шаг г должен быть малым.

Звездной цепочкой {star chain) является аддитивная цепочка, включающая только звездные шаги. Это означает, что каждый член а, представляет собой сумму Oi-i и предшествующего ему Ок, простой "компьютер", упоминавшийся ранее, после (2), в звездной цепочке использует только две операции, STA и ADD (без LDA),

поскольку каждый новый член последовательности использует предыдущий результат, находящийся в аккумуляторе. Большинство рассмотренных здесь аддитивных цепочек являются звездными. Минимальная длина звездной цепочки для п записывается как 1*{п); понятно, что

1{п)<1*{п). (13)

Теперь можно вывести несколько нетривиальных фактов об аддитивных цепочках. Сначала покажем, что в цепочке должно быть весьма много удвоений, если г не слишком сильно отличается от Л(п).

Теорема А. Если аддитивная цепочка (И) включает d удвоений и f = г - d неудвоений, то

п < 2-Ff+3. (14)

Доказательство. Используя индукцию nor = d + f, находим, что (14) истинно при г = 1. При г > 1 имеется три случая. Если шаг г -удвоение, то п = Or-i < 2~Ff+3; следовательно, (14) вьшолняется. Если шаги г и г - 1 не являются удвоениями, то ur-i < 2*~F/+2 и аг-2 < 2~F/+i; следовательно, п = йг < Ur-i + аг-2 < 2~(F/4.2 + Ff+i) = 2~Ff+3 по определению последовательности Фибоначчи. И наконец, если шаг г - неудвоение, а шаг г - 1 - удвоение, то аг-2 < 2~Ff+2 ип - йг < ur-i + аг-2 - Заг-2- Теперь 2Е/+з - 3F/4.2 = - Ff > 0; следовательно, п < 2~Ff+з для всех случаев.

Использованный нами метод доказательства показывает, что неравенство (14) является "наилучшим возможным" при указанных предположениях; аддитивная цепочка

1, 2, ..., 2"-, 2<-Рз, 2-F,, 2-Ff+3 (15)

имеет d удвоений и / неудвоений.

Следствие. Если аддитивная цепочка (И) включает / неудвоений и s малых шагов, то

s<f< 3.271s. (16)

Доказательство. Очевидно, что s < f. Имеем

2(") <п< 2-Ff+3 < 2ф = 2(")+Ч<>/2)

поскольку d + f = Х(п) + S и F/4.3 < 2ф при / > 0. Значит, О < sln2 -Ь /\п{ф/2) и (16) следует из того факта, что In 2/\п{2/ф) « 3.2706.

Значения 1{п) для специальных п. Легко показать при помощи индукции, что flj < 2\ и, таким образом, Ign < г в любой аддитивной цепочке (11). Следовательно,

1{п) > [Ign]. (17)

Эта нижняя граница вместе с верхней границей (10), полученной при помощи бинарного метода, дают значения

/(2) = А; (18)

/(2 + 2) = Л + 1, если Л > В. (19)

Другими словами, бинарный метод является оптимальным при и{п) < 2. При помощи некоторых вычислений можно расширить эти формулы для случая, когда и{п) = 3.

Теорема В.

Z(2 + 2« + 2") = Л + 2, если А> В>С.

(20)

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

2 2 + 2,..., 2+с + 2+; Л > В > О, С > 0. 2\ 2 + 2«, 2+1 + 2, ..., 2++1 + 2+; Л > В > О, С > 0. 2Л 2 + 2-1, 2+1 + 2-1, 2+2, ..., 2+; Л > О, С > 2. 2А 2 + 2-1, 2+1 + 2Л 2+2, ..., 2+; Л > О, С > 2. 2 2"* + 2~ 2"*+ + 2"*+"" 2+с-\-\ 2+~2 2a+c+d+i 2+c+d-2. л > О, С > О, £) > 0.

2Л 2 + 2«, 2+1, ..., 2+; Л > В > О, С > 1.

Непосредственные вычисления показывают, что эти шесть типов исчерпывают все возможности. Согласно следствию из теоремы А имеется не более трех неудвоений при наличии одного малого шага; этот максимум встречается только в последовательности третьего типа. Все приведенные выше цепочки - звездные, за исключением типа 6, когда В < Л - 1.

Теперь теорема следует из того факта, что

1{2 + 2 + 2") < Л + 2,

и /(2"* -1-2-1- 2) должно быть больше, чем Л -f- 1, поскольку ни один из шести возможных типов не имеет v{n) > 2.

(Э. деЖонкиэрес (Е. de Jonquieres) в 1894 году без доказательства указал, что 1{п) > А(п) -I- 2, когда и{п) > 2. Впервые теорема В появилась в работе А. А. Gioia, М. V. Subbarao and М. Sugunamma, Duke Math. J. 29 (1962), 481-487.)

Вычислить Z(2 -I- 2 -I- 2 + 2) при A > В > С > D более сложно. По бинарному методу эта величина не превышает Л -I- 3, а в соответствии с доказательством теоремы В она не меньше, чём Л -- 2. Величина Л -- 2 является допустимой, так как известно, что бинарный метод не оптимален при п = 15 или п = 23. Как мы сейчас увидим, при и(п) = 4 можно дать полное определение поведения этой величины.

Теорема С. Если и(п) > 4, то 1(п) > А(п) -I- 3 за исключением следующих случаев, когда А>В>С>Пи Д2 + 2 + 2" + 2) равно Л -- 2.

Случай 1, А-В = С - D. (Пример: п = 15.)

Случай 2. А - В = С - D + 1. (Пример: п = 23.)

Случай 3. Л - В = 3, С - D = 1. (Пример: п = 39.)

Случай 4. Л-В = 5, B-C = C- D = 1. (Пример: п = 135.)