Некоторые свойства аддитивных цепочек

Некоторые свойства аддитивных цепочек

Костюрина Екатерина (ученица 10 класса ГОУ Лицея № 000)
Научный руководитель:

Дадим необходимые определения:

Аддитивной цепочкой для числа р называется последовательность натуральных чисел 1, 2, а2, а3, …, аn= p где каждый следующий член получается путем сложения каких-либо двух предыдущих:

аi = аj + аk, k ≤ j < i, i = 1, 2, …, n,

при этом число n называется длиной аддитивной цепочки.

l(p) – будем обозначать минимальное из чисел n число, т. е. минимальную длину аддитивной цепочки для числа p:

1, 2, а2, а3, …, аl(p)= p, где l(p) = min{n: 1, 2, а2, а3, …, аn= p}

Для удобства, под l(p) будем понимать также некоторую минимальную аддитивную цепочку для р.

Цепочкой Брауэра называется аддитивная цепочка, в которой каждый следующий член образуется с использованием предыдущего:

аi = аi-1 + аk, k < i, i = 1, 2, …, n.

Цепочкой Хансена называется аддитивная цепочка, для которой существует подмножество Н = {1, 2, b1…, bm}, состоящее из элементов, таких, что каждый член цепочки образуется из наибольшего элемента из Н, который меньше этого члена.

аi = bp + аk, bp = max{bÎH, b < аi}, i = 1, 2, …, n.

Минимальные аддитивные цепочки Брауэра и Хансена для р будем обозначать lB(p) и lH(p) соответственно.

Проблема определения l(p) связана с задачей эффективного вычисления хр по данным х и р, где р – натуральное число. Согласно Кнуту [3, стр. 503, 507] эта проблема, по-видимому, впервые была поставлена в 1894 году Х. Деллаком и частично решена Э. де Жонкиэресом методом множителей, которым можно получить следующую оценку для произведения:

l(mn) <l(n)+l(m)+1.

С тех пор получено много результатов, которые можно найти в [1]-[4], где указаны также нерешенные проблемы, например, оценка l(2n)>l(n)-1, также проблематична.

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

λ(n)=[log2 n] – длина двоичной записи числа n, уменьшенная на единицу ([x] – целая часть числа х);

ν(n) – число единиц (сумма цифр) двоичной записи числа n.

Эти функции связаны следующими рекуррентными соотношениями [3, стр. 509]:

λ(1)=0, λ(2n) = λ(2n+1) = λ(n) + 1, ν(1)=1, ν(2n) = ν(n), ν(2n+1) = ν(n) + 1,

и с их помощью легко получить следующую оценку l(n) [1, стр. 161]:

l(n) ≤ λ(n) + ν(n) – 1. (1)

Для функций ν(n) можно доказать следующую лемму:

Лемма 1. Для любых натуральных m и n справедливо неравенство:

ν(n+m) ≤ ν(n) + ν(m) – ν(nÙm),

где ν(nÙm) – число единиц двоичной записи m и n, стоящих на одних местах.

Доказательство. Запишем двоичные записи чисел m и n для сложения их «в столбик»:

m = 110111000…01110011

n = 1011100…01101010

Далее перенесем все те единицы из нижнего ряда в верхний ряд, над которыми стоит 0:

111111100…01111011

11000…01100010

Очевидно, что это действие не повлияет на результат сложения, но тогда, в силу принципа включения и исключения, верхний ряд будет содержать ν(n) + ν(m) – ν(nÙm) единиц, а в нижнем останется ν(nÙm) единиц.

Далее, верхний ряд окажется разбитым на блоки, состоящие из подряд идущих единиц, разделенных нулями. При сложении, ν(nÙm) единиц в блоках верхнего ряда, стоящих над единицами нижнего ряда приведет к сдвигу влево соответствующего блока и не увеличит число ν(nÙm):

111111100…01111011

11000…01100010

1000010100…11011101

Лемма 1 доказана.

Наиболее знаменитая проблема, связанная с аддитивными цепочками и все еще нерешенная, – гипотеза Шольца-Брауэра [3, стр. 521], гласящая, что

l(2n – 1) ≤ n – 1 + l(n) (2)

В 1939 году А. Брауэр доказал, что

lВ(2n – 1) ≤ n – 1 + lВ(n), (3)

а затем Хансеном было показано, что l(n) может быть меньше, чем lВ(n) и определил цепочку lН(n), определенную выше (цепочку Хансена).

Докажем теорему одну из теорем Хансена, а именно

Теорема 1. Для любого натурального n справедливо неравенство.

lН(2n – 1) ≤ n – 1 + lН(n).

Доказательство. Будем пользоваться двоичной записью числа, например, 7 = 1112. Тогда в двоичной системе счисления число

, а число .

Эти (n-1) ноль или (n-1) место (и только их!) будем использовать в нашем дальнейшем алгоритме.

Пусть 1, 2, а2, а3, …, аp= n, где р = lН(n), цепочка Хансена и Н = {1, 2, b1…, bq} – соответствующее по определению ей множество.

Каждому члену аi, i = 1, 2, …, lН(n), этой последовательности поставим в соответствие набор из аk единиц (эти наборы соответствуют двоичным представлениям чисел ). Так как каждый член цепочки есть сумма двух некоторых предыдущих, то, в нашей соответствующей последовательности, каждый член есть конкатенация двух некоторых предыдущих наборов. Например, цепочке 1, 2, 4, 5 ставится в соответствие последовательность: 1,11,1111,11111. Заметим, что конечное число единиц равно n, а число членов этой последовательности – (lН(n)+1).

Для построения цепочки lН(2n – 1) будем дописывать нули (удваивать) к наборам из bi единиц (bi+1 – bi) раз и вставляя между ними наборы из а единиц, где a – элемент цепочки lН(n), лежащий между bi и bi+1, i=1, 2, …, q, а bq+1 = n. Это можно сделать, в силу определения цепочки Хансена.

Всего нулей будет дописано 1+ (b2 – 2) + (b3 – b2) + … + (bn – bq) = n – 1, наборов из единиц, очевидно, – lН(n).

Легко проверить, что построенная цепочка является цепочкой Хансена, у которой множество Н состоит из всех чисел , i = 0, 1, …, lН(n) и всех удвоений чисел , i = 0, 1, …, q.

В качестве примера, рассмотрим цепочку для m=(213 – 1). Пусть цепочка для числа 13 имеет вид:

1, 2, 4, 5, 8, 13

Очевидно, это является цепочкой Хансена с Н={1, 2, 4, 8}. Соответствующие ей наборы единиц:1, 11, 1111, 11111, 11111111, 1111111111111. Построенная алгоритмом цепочка для (213 – 1) будет иметь вид:

1, 2, 3, 6, 12, 15, 30, 31, 60, 120, 240, 255, 510, 1020, 2040, 4080, 8160, 8191.

Здесь

Н={1, 2, 3, 6, 12, 15, 30, 60, 120, 240, 255, 510, 1020, 2040, 4080, 8160, 8191}.

Теорема доказана.

Пользуясь методом доказательства этой теоремы можно получить следующие следствия.

Рассмотрим аддитивные цепочки для таких чисел n, двоичная запись которых состоит из нескольких одинаковых блоков, разделенных нулями. Например, 10100101000 = 132010, здесь два блока вида 101 и 5 разделяющих их нулей.

Следствие 1. Пусть двоичная запись числа n состоит из р одинаковых блоков, представляющих число k и разделенных m нулями (m ≥ 0). Тогда

lН(n) ≤ l(k) + λ(n) – λ(k) + lН(p).

Доказательство. Сначала строим аддитивную цепочку для k и записываем ее в двоичной системе счисления, затем находим цепочку Хансена для числа р. После чего удваиваем (дописываем нули) (λ(n) – λ(k)) раз, вставляя между полученными членами из lН(p), как при доказательстве теоремы 1.

Следующее следствие доказывается аналогично.

Следствие 2. Пусть двоичная запись нечетного числа n состоит из р одинаковых блоков, представляющих число k и разделенных каждый с каждым (р-1) блоками из некоторого числа m нулей так, что

2p(λ(k)+1+m) –1 = n(2m +1).

. Тогда

lН(2p(λ(k)+1+m) –1) ≤ l(k) + λ(n) – λ(k) + lН(p) + m +1.

Следует заметить, что при m=0 и k=1, λ(1) = l(1) = 0. Поэтому теорема 1 есть частный случай следствия 1, но не вытекает из следствия 2, например, для цепочки l(28 – 1), т. к. в этом случае l(7) = 4 > l(8) = 3 и оценка следствия 2 будет на 1 больше, чем в теореме 1.

В заключении рассмотрим пример следствия 2: lН(212 – 1).

Возьмем n = 1365. Его двоичная запись 10101010101, состоит из трех блоков «101», разделенных одним нулем (k=5, p=3, m=1). Минимальная аддитивная цепочка для числа 5: 1, 2, 3, 5, l(5)=3. λ(5) = 2, 23(2+1+∙1) –1 = 212 – 1 = 1365(21 + 1) = 4095, а lН(p) = lН(3) = 2 и λ(1365) = 10. По оценке следствия 2 получаем:

lН(212 –1) ≤ l(5) + λ(1365) – λ(5) + lН(3) + 1 = 3 + 10 – 2 + 2 + 1 +1 = 15

А, т. к. цепочка Хансена для 12 имеет вид: 1, 2, 4, 8, 12, то lН(12) = 4 и оценка в теореме 1 будет такой же:

lН(212 – 1) ≤ 12 – 1 + lН(12) = 12 – 1 + 4 = 15.

Автор благодарит за научное руководство, и за полезные обсуждения работы.

Выводы:

•  Сформулировано и доказано новое свойство для ν(n)

•  Найдено новое доказательство теоремы Хансена

•  Сформулированы и доказаны два следствия из теоремы Хансена

Литература

[1] , , Алгоритмическин основы эллиптической криптографии, Изд-во РГСУ, М., 2004.

[2] Гашков элементарная алгебра, Изд-во МЦНМО, М., 2006.

[3] Искусство программирования, т.2,

[4] Richard K. Guy, Unsolved problems in Number Theory (раздел C6), QA241.G87 1994