Factorials

[Pavlovsky]

svb в сообщении #678303 писал(а):

Положим: $f\left( i \right) = m$ и $l(i) = n$.

Это что за функции?

[svb]

Pavlovsky
Это приведено определение функций

Можно иначе:
$f(i)$ - старший индекс аргументов i-ой операции,
$l(i)$ - младший индекс аргументов i-ой операции

[Xaositect]

svb в сообщении #678303 писал(а):

SLP последовательность:
$1,x_1 ,x_2 ,...,x_k $, $x_i = op_i \left( {x_m ,x_n } \right)$, $m \le i,n \le i$, $op_i = \left( { + , - , \times } \right)$
Для шага $x_i = op_i \left( {x_m ,x_n } \right)$ без ограничения общности можно считать $x_n \le x_m $, для этого при вычитании достаточно рассматривать абсолютную величину результата. Положим: $f\left( i \right) = m$ и $l(i) = n$.

Теорема. Для любой SLP последовательности $1,x_1 ,x_2 ,...,x_k $ существует эквивалентная ей последовательность $1,y_1 ,y_2 ,...,y_k $ , состоящая из тех же чисел, что $f\left( i \right) = i - 1 $, либо $f\left( i \right) = f\left( {i - 1} \right)$.

Если убрать случай $f\left( i \right) = f\left( {i - 1} \right)$, то резко сокращается пространство перебора.

Приведенную теорему необходимо проверить, т.к. я мог совершить ошибку. Первоначально мне показалось, что при переборе можно убрать вариант $f\left( i \right) = f\left( {i - 1} \right)$, но для конкретной последовательности это невозможно в том варианте, как указано в теореме. При переборе же ситуация сложнее и, возможно, этот случай можно исключить. По крайней мере, конкретные решения мне удалось получить без использования последнего варианта.

Дополнительно полезно рассмотреть функцию $l(i)$.

Имеется в виду, что условие $f(i) = i-1 \vee f(i) = f(i - 1)$ выполняется для любого $i$? Что-то я сомневаюсь, что это верно. По крайней мере для аддитивных цепочек это не выполняется.

[svb]

Xaositect
Можно так переставить, что условие будет выполняться.

Кстати, достаточно одного примера, чтобы опровергнуть теорему.

[Pavlovsky]

$x_i = op_i \left( {x_m ,x_n } \right)$

Операция задает отношение частичного упорядочивания. $x_i > x_m$ и $x_i > x_n$. Любой частичный порядок можно дополнить до полного порядка. В том числе числа выстроить в линию можно и таким способом, чтобы $x_{i+1} = op_i \left( {x_i ,x_n } \right)$

Ой вру.

[Xaositect]

svb в сообщении #678315 писал(а):

Кстати, достаточно одного примера, чтобы опровергнуть теорему.

Я, возможно, что-то упустил, но покажите, пожалуйста, перестановку для программы $1, 2, 4, 16, 256, 2^{16}, 2^{16} + 1, 2^{18} + 4, 2^{24}, 2^{24} + 1, 2^{42} + 2^{26} + 2^{18} + 4$ (в ней условие не выполняется для шага $2^{24}$)

[Pavlovsky]

Нормализованная последовательность.
Ну умоляя общности положим m>=n в операции $x_i = op_i \left( {x_m ,x_n } \right)$.

Построение нормализованной последовательности.
Пусть у нас уже построена последовательность $1,x_1 ,x_2 ,...,x_i $. Из чисел еще не добавленных в послдовательность выберем число такое что $x_j = op_j \left( {x_i ,x_n } \right)$. Если такое число есть, то добавим его в последовательность. В противном случае будем искать число $x_j = op_j \left( {x_m ,x_n } \right)$, где $x_m$ число из операции $x_i = op_i \left( {x_m ,x_n } \right)$ и так далее вплоть до числа 1.

Такой подход годится, если мы делаем перебор начиная с 1 и пока не встретим искомое число. Примерно как описано в http://mathforum.org/wagon/current_solu ... s1153.html

Но это не самый лучший подход для текущего конкурса. Очевидно надо строить последовательность задом на перед. Начиная с искомого числа, до тех пор пока под каждое число сможем предъявить операцию $x_i = op_i \left( {x_m ,x_n } \right)$.

[svb]

Xaositect
Спасибо за пример. Теорема опровергнута

-- Чт янв 31, 2013 16:49:26 --

Pavlovsky

Цитата:

Очевидно надо строить последовательность задом на перед.

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

Забавная задачка

[Pavlovsky]

Изучаю статью http://www.cs.ou.edu/~qcheng/paper/factorial.pdf
Застрял на введении

Цитата:

1 Introduction
...
Given an integer m ≥ 2, the smallest positive integer α such
that gcd(α! mod m,m) > 1 is a prime factor of m. For every integer n ≥ α,
gcd(n! mod m,m) is greater than 1

Ничего не пойму. Ведь n! mod m=0 для всех n>=m. Чему тогда равно gcd(0,m)??

[Xaositect]

$\operatorname{gcd}(0,m) = m$. По определению. Любое число делит нуль, наибольшим общим делителем нуля и $m$ является $m$.

[Pavlovsky]

Неожиданно. Буду знать. Спасибо.

-- Чт янв 31, 2013 19:31:46 --

Цитата:

For any prime p, we have p|Ps(x) if s is
divisible by |E(Fp)|, where E is the reduction of E at p and x mod p is the
abscissa of a point on E(Fp) ( x may or may not be an abscissa of a point on
E(Q)).

А что обозначает вертикальная черта в этом выражении p|Ps(x)?

[Nakilon]

svb в сообщении #678344 писал(а):

Похоже, необходимо действовать с двух сторон. Сначала строить базовые последовательности, а уж потом двигаться от результата.

Эта идея давала 20-е место из 200 на 4-ый день соревнования в реализации на самом медленном из языков. Pavlovsky, svb, вы имеете различные аккаунты на сайте соревнования?

[svb]

Вычисления от результата

Рассмотрим арифметику специальных чисел, записанных в виде наборов степеней простых чисел. Например: $102 = 5^1 3^0 2^2 = 20$. В этой арифметике любое число можно выразить через 0(=1):
1=0+0
10=1+0=0+0+0
11=(1+0)(0+0)=(0+0+0)(0+0)=0+0+0+0+0+0
20=(10)(10)=(0+0+0)(0+0+0)=0+...+0 (9 нулей)
В этой арифметике обычное число 37! будет выглядеть как YH8532211111.
Так как дистрибутивный закон в этой арифметике действует, то легко получить представление YH8532211111 через меньшие числа путем раскрытия скобок.
Ясно, что SLP последовательности дают для числа X некоторую последовательность вычислений числа X. Пусть $STEP(X)$ минимальная длина такой последовательности.
Очевидно, что $STEP\left( {XY} \right) \le STEP\left( X \right) + STEP\left( Y \right) + 1$
и $STEP\left( {X+Y} \right) \le STEP\left( X \right) + STEP\left( Y \right) + 1$

Ну, и т.д. Это просто интерпретация исходной задачи.

Nakilon

Цитата:

Pavlovsky, svb, вы имеете различные аккаунты на сайте соревнования?

Я имею отношение к Pavlovsky такое же, как и к вам - общаюсь с ним только через форум. Нарушений правил конкурса со своей стороны я не вижу и, возможно, с некоторого момента вступлю в игру под своим аккаунтом.

[Nakilon]

Все с вами ясно.

А я-то было уже поверил странице на пятой Nataly-Mak о спортивности вашего сообщества.

Русские такие русские.

Удачи.

[svb]

Nakilon

Цитата:

А я-то было уже поверил странице на пятой Nataly-Mak о спортивности вашего сообщества.

Она меня плохо переносит. Когда мы выступали командой, то это было под аккаунтом Nataly-Mak и обменивались между собой письмами, но это было так давно. Лично я не большой любитель участвовать в конкурсах - вдруг мои знакомые узнают об этом и мне станет стыдно . Но задачка мне нравится.