2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 8, 9, 10, 11, 12, 13, 14 ... 88  След.
 
 Re: Factorials
Сообщение31.01.2013, 15:29 
Аватара пользователя


21/02/10
1594
Екатеринбург
svb в сообщении #678303 писал(а):
Положим: $f\left( i \right) = m$ и $l(i) = n$.


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

 Профиль  
                  
 
 Re: Factorials
Сообщение31.01.2013, 15:33 
Аватара пользователя


20/01/10
766
Нижний Новгород
Pavlovsky
Это приведено определение функций :-)

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

 Профиль  
                  
 
 Re: Factorials
Сообщение31.01.2013, 15:38 
Заслуженный участник
Аватара пользователя


06/10/08
6422
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$? Что-то я сомневаюсь, что это верно. По крайней мере для аддитивных цепочек это не выполняется.

 Профиль  
                  
 
 Re: Factorials
Сообщение31.01.2013, 15:40 
Аватара пользователя


20/01/10
766
Нижний Новгород
Xaositect
Можно так переставить, что условие будет выполняться.

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

 Профиль  
                  
 
 Re: Factorials
Сообщение31.01.2013, 15:54 
Аватара пользователя


21/02/10
1594
Екатеринбург
$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)$

Ой вру.

 Профиль  
                  
 
 Re: Factorials
Сообщение31.01.2013, 16:15 
Заслуженный участник
Аватара пользователя


06/10/08
6422
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}$)

 Профиль  
                  
 
 Re: Factorials
Сообщение31.01.2013, 16:22 
Аватара пользователя


21/02/10
1594
Екатеринбург
Нормализованная последовательность.
Ну умоляя общности положим 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)$.

 Профиль  
                  
 
 Re: Factorials
Сообщение31.01.2013, 16:36 
Аватара пользователя


20/01/10
766
Нижний Новгород
Xaositect
Спасибо за пример. Теорема опровергнута :-(

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

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

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

 Профиль  
                  
 
 Re: Factorials
Сообщение31.01.2013, 17:03 
Аватара пользователя


21/02/10
1594
Екатеринбург
Изучаю статью 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)??

 Профиль  
                  
 
 Re: Factorials
Сообщение31.01.2013, 17:06 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Factorials
Сообщение31.01.2013, 17:09 
Аватара пользователя


21/02/10
1594
Екатеринбург
:D Неожиданно. Буду знать. Спасибо.

-- Чт янв 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)?

 Профиль  
                  
 
 Re: Factorials
Сообщение31.01.2013, 18:30 
Аватара пользователя


23/01/13
11
Мелитополь
svb в сообщении #678344 писал(а):
Похоже, необходимо действовать с двух сторон. Сначала строить базовые последовательности, а уж потом двигаться от результата.


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

 Профиль  
                  
 
 Re: Factorials
Сообщение31.01.2013, 18:39 
Аватара пользователя


20/01/10
766
Нижний Новгород
Вычисления от результата

Рассмотрим арифметику специальных чисел, записанных в виде наборов степеней простых чисел. Например: $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 такое же, как и к вам - общаюсь с ним только через форум. Нарушений правил конкурса со своей стороны я не вижу и, возможно, с некоторого момента вступлю в игру под своим аккаунтом.

 Профиль  
                  
 
 Re: Factorials
Сообщение31.01.2013, 18:50 
Аватара пользователя


23/01/13
11
Мелитополь
Все с вами ясно.

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

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

Удачи.

 Профиль  
                  
 
 Re: Factorials
Сообщение31.01.2013, 19:01 
Аватара пользователя


20/01/10
766
Нижний Новгород
Nakilon
Цитата:
А я-то было уже поверил странице на пятой Nataly-Mak о спортивности вашего сообщества.
:D Она меня плохо переносит. Когда мы выступали командой, то это было под аккаунтом Nataly-Mak и обменивались между собой письмами, но это было так давно. Лично я не большой любитель участвовать в конкурсах - вдруг мои знакомые узнают об этом и мне станет стыдно :D . Но задачка мне нравится.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1310 ]  На страницу Пред.  1 ... 8, 9, 10, 11, 12, 13, 14 ... 88  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Dmitriy40


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group