2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 55, 56, 57, 58, 59, 60, 61 ... 88  След.
 
 Re: Factorials
Сообщение22.04.2013, 08:55 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Итак, положение России на конкурсе:

Цитата:
5 Israel 4
10 China 4
12 Russia 19
29 India 16
88 Vietnam 8
95 Indonesia 1
101 Japan 5
162 Philippines 1
213 Singapore 1
284 Taiwan 1
333 Iran 1
337 Hong Kong 1
343 Thailand 1
385 Sri Lanka 1

Почётное 3-е место :D
Зато по количеству участников на первом месте.
Не взяли качеством, взяли количеством :wink:

 Профиль  
                  
 
 Re: Factorials
Сообщение22.04.2013, 08:59 
Заблокирован


21/04/13

78
Nataly-Mak в сообщении #713892 писал(а):
wanderers в сообщении #713888 писал(а):
И 23! вписывается также в парадигму (y, x, a).

Вот это

$23! = 322\cdot (322+1) \cdot 12636 \cdot 4435200^2$

и есть та самая парадигма?

Цитата:
n!=(x*a)(x*a+a)*y

Существуют решения с x=322 и с x=223: просто хочу донести до сознания окружающих, что никаких велосипедов изобретать не нужно - достаточно двух сгенерированных таблиц. Хотя сам алгоритм не так прост: на c это несколько тысяч операторов (к сожалению, отладить полностью алгоритм для случая (y, x, a) к 10 апреля не сумел, по этой причине даже не удалось к этому времени посчитать 27!, т.к. 11 апреля отбыл в командировку и появился только утром 20 апреля. Надеялся, что успею выловить баги, но это случилось только поздним вечером 20 апреля). И потом, в вашей записи решения лишняя операция.

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


01/06/12
1016
Adelaide, Australia
wanderers в сообщении #713899 писал(а):
Существуют решения с x=322 и с x=223: просто хочу донести до сознания окружающих, что никаких велосипедов изобретать не нужно - достаточно двух сгенерированных таблиц.


Но достаточно ли? Можно ли этим методом найти все оптимальные решения до N=37?

 Профиль  
                  
 
 Re: Factorials
Сообщение22.04.2013, 09:28 
Заблокирован


21/04/13

78
dimkadimon в сообщении #713905 писал(а):
wanderers в сообщении #713899 писал(а):
Существуют решения с x=322 и с x=223: просто хочу донести до сознания окружающих, что никаких велосипедов изобретать не нужно - достаточно двух сгенерированных таблиц.


Но достаточно ли? Можно ли этим методом найти все оптимальные решения до N=37?


Такая задача перед конкурсантами не ставилась: я действовал в рамках поставленной задачи. Мне вот более интересно, с чего это победители конкурса людям мозги "компостируют"?

P.S.
Я уже ранее писал, что достаточно взглянуть на решения для 13!, 14!, 15!, 16! и 17!, чтобы понять, что все оптимальные решения достаточно разнообразны и не вписываются в мой метод.

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


22/03/08

7154
Саратов
wanderers в сообщении #713899 писал(а):
Существуют решения с x=322 и с x=223...

Может быть, с x=224?

$23! = 224 \cdot (224+1) \cdot 1330560^2 \cdot 289731$

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


01/06/12
1016
Adelaide, Australia
wanderers в сообщении #713906 писал(а):
Такая задача перед конкурсантами не ставилась: я действовал в рамках поставленной задачи. Мне вот более интересно, с чего это победители конкурса людям мозги "компостируют"?

P.S.
Я уже ранее писал, что достаточно взглянуть на решения для 13!, 14!, 15!, 16! и 17!, чтобы понять, что все оптимальные решения достаточно разнообразны и не вписываются в мой метод.


Перефразирую свой вопрос. Может ли ваш метод набрать 25 в конкурсе? Мой опыт показал что найти оптимальные решения для N<=27 не достаточно, так как найти оптимальные решения для N>27 гораздо сложнее.

Например для больших N вашей таблицы может не хватить. Конечно таблицу можно увеличить, но она будет расти очень быстро и время просмотра этой таблицы тоже будет расти.

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


22/03/08

7154
Саратов
wanderers в сообщении #713899 писал(а):
И потом, в вашей записи решения лишняя операция.

Где именно лишняя операция? В решении для 23! :?:

Код:
1,2,3,9,27,36,324,351,12636,322,4435236,4435200,1428134400,1432569600,
2045901926154240000,25852016738884976640000

Но здесь решение в 15 шагов. Разве для 23! есть решение в 14 шагов?

 Профиль  
                  
 
 Re: Factorials
Сообщение22.04.2013, 09:49 
Заблокирован


21/04/13

78
Nataly-Mak в сообщении #713911 писал(а):
wanderers в сообщении #713899 писал(а):
Существуют решения с x=322 и с x=223...

Может быть, с x=224?

$23! = 224 \cdot (224+1) \cdot 1330560^2 \cdot 289731$

Уточняю: расчет 23! и 24! проводился на более примитивном уровне, т.к. к этому времени отладка для (y, x, a) была еще не завершена: как только появлялось решение или группа решений, я снимал задачу. Но для расчета 27! этот метод для меня уже не годился, т.к. более часа я не готов был ждать решения.

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


22/03/08

7154
Саратов
Ничего не поняла в вашем уточнении.

Пожалуйста, приведите парадигму для x=223 в виде числового разложения.
Я такое разложение не нашла, а нашла то, что показано выше (x=224).

Да, и где вы видите в моём решении для 23! лишнюю операцию?

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


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #713905 писал(а):
Но достаточно ли? Можно ли этим методом найти все оптимальные решения до N=37?


Естественно нет. Но оцените решение для 37! на единицу хуже оптимального.

1,2,3,9,18,36,648,666,443556
37!=666*651*443555*34^2*650^2*443520^3*648^2*2^2
После преобразования получается решение в 21 операцию.

Используется начальная последовательность всего в 8 операций (9 чисел). Процедура разложения на множители работает не просто быстро, а очень быстро. То есть получить решение для 37! в 21 операцию можно используя очень скромные вычислительные ресурсы!
Конечно, если бы мы взяли начальную последовательность
1,2,3,9,18,36,648,666,443556,651,443520,443520*651
Тогда мы бы нашли решение в 21 операцию и без преобразований. Но удлинить последовательность на три числа это означает рассмотреть более 100 тысяч вариантов. То есть без применения преобразования, поиск бы шел в сотни тысяч раз дольше!

 Профиль  
                  
 
 Re: Factorials
Сообщение22.04.2013, 10:05 
Заблокирован


21/04/13

78
Nataly-Mak в сообщении #713917 писал(а):
wanderers в сообщении #713899 писал(а):
И потом, в вашей записи решения лишняя операция.

Где именно лишняя операция? В решении для 23! :?:

x=322
y=12636
a=4435200
У вас
1.x+1
2.x*(x+1)
3.(x*(x+1))*y
4.a*a
5.[(x*(x+1))*y]*(a*a)
У меня
1.x*a
2.x*a+a
3.(x*a)*(x*a+a)
4.[(x*a)*(x*a+a)]*y

Ваш второй вопрос не понял.

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


22/03/08

7154
Саратов
Nataly-Mak в сообщении #713917 писал(а):
wanderers в сообщении #713899 писал(а):
И потом, в вашей записи решения лишняя операция.

Где именно лишняя операция? В решении для 23! :?:

Код:
1,2,3,9,27,36,324,351,12636,322,4435236,4435200,1428134400,1432569600,
2045901926154240000,25852016738884976640000

Но здесь решение в 15 шагов. Разве для 23! есть решение в 14 шагов?

Ещё раз, пожалуйста, посмотрите на моё решение.
В нём же 15 шагов. В 14 шагов вроде нет решения для 23!

Цитата:
У вас
1.x+1

Где вы видите в моём решении (x+1)?

Второй вопрос.
Вы пишете, что есть решение для x=223.
Я прошу привести это решение, ну или хотя бы разложение для x=223.

 Профиль  
                  
 
 Re: Factorials
Сообщение22.04.2013, 10:38 
Заблокирован


21/04/13

78
Nataly-Mak в сообщении #713939 писал(а):
Где именно лишняя операция? В решении для 23! :?:

Второй вопрос.
Вы пишете, что есть решение для x=223.
Я прошу привести это решение

Вы писали:
$23! = 322\cdot (322+1) \cdot 12636 \cdot 4435200^2$
В такой записи 5 операций.

Код:
1,2,3,9,27,36,324,323,351,12636,4435236,4435200,1428134400,1432569600,2045901926154240000,25852016738884976640000

x=323
y=12636
a=4435200
1.x*a
2.x*a-a
3.(x*a)*(x*a-a)
4.[(x*a)*(x*a-a)]*y

 Профиль  
                  
 
 Re: Factorials
Сообщение22.04.2013, 10:45 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
wanderers в сообщении #713957 писал(а):
Вы писали:
$23! = 322\cdot (322+1) \cdot 12636 \cdot 4435200^2$
В такой записи 5 операций.

Где 5 операций? :-)
Я нахожу число 4435200 за 11 шагов:

Код:
1,2,3,9,27,36,324,351,12636,322,4435236,4435200

Это понятно?
В вашем решении ведь то же самое! Число 4435200 стоит в последовательности 11-ым шагом:

Код:
1,2,3,9,27,36,324,323,351,12636,4435236,4435200

Разве не так?

Далее завершаю вычисление 23! за 4 операции!

Код:
1,2,3,9,27,36,324,351,12636,322,4435236,4435200,1428134400,1432569600,
2045901926154240000,25852016738884976640000


Где вы видите какие-то 5 операций?
Вы привязались к своему решению и не хотите понять решение, которое чуть-чуть отлично от вашего.

Это разложение

$23! = 322\cdot (322+1) \cdot 12636 \cdot 4435200^2$

можно записать и так:

$23! = 323\cdot (323-1) \cdot 12636 \cdot 4435200^2$

Никакой разницы нет абсолютно.

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


21/02/10
1594
Екатеринбург
Прочитал описание алгоритмов лидеров. Понравилось:
tomrokicki
Цитата:
Fifth, I pregenerated all possible equations a+b=c where a and b are
relatively prime and a, b, and c are all factors of 37!. There turns
out to be only a small number of these, and they fit in a small hash
table, so I was able to use this to restrict the additions and
subtractions I performed to those resulting in factors, efficiently.
(Side puzzle for those who haven't done it already: how fast can you
generate all of these equations, and how many are there?)


Это к вопросу как складывать, вычитать числа представленные ввиде разложения на простые множители.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1310 ]  На страницу Пред.  1 ... 55, 56, 57, 58, 59, 60, 61 ... 88  След.

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



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

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


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

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