Factorials

[wanderers]

Nataly-Mak в сообщении #713958 писал(а):

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

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

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

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

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

Формальная разница есть: это два различных решения. И далеко не всегда существуют решения: одно - с плюсом, а другое - с минусом.
Еще раз повторяю: ваша запись содержит операции (x-1, x*(x-1), a^2), которых нет в оптимальном решении.

-- 22.04.2013, 12:22 --

dimkadimon в сообщении #713915 писал(а):

wanderers в сообщении #713906 писал(а):

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

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

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

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

Давайте считать: 31! у меня посчитал на 14 ядрах за полчаса. Этот расчет можно было значительно ускорить, если работать не со всей базой данных, а только с ее участками, которые дают наибольшее количество решений - это примерно 1/5 базы. Вроде получается, что мой алгоритм гарантированно за приемлемое время может набрать 25 баллов. И я ведь еще не исчерпал методы ускорения решения, не связанные с таблицами. Что касается просмотра таблиц, то я использую хеширование и практически сразу определяю, что, где и почему: я об этом ранее писал. Для случая (y, x, a) методика хеширования довольно нетривиальна: из-за ее реализации да плюс еще командировка у меня не хватило времени.

[dimkadimon]

Pavlovsky в сообщении #713968 писал(а):

Прочитал описание алгоритмов лидеров. Понравилось:

Мне тоже это больше всего понравилось. Я никак не мог придумать как ускорить сложение и вычитание. Умножение можно представить как сумму: (a^k * b^m) * (a^p * b^q) представляем как (k,m)+(p,q)=(k+p,m+q).

[Nataly-Mak]

wanderers
ещё раз повторяю: моё решение содержит 15 шагов.

Вы не ответили на мой предыдущий вопрос, где у меня какие-то 5 операций?
Пкажите мне в моём решении, в котором 15 шагов, лишнюю операцию.

По-моему, давно пора признать, что вы были не правы.
Но вы упорствуете в своей неправоте.
Хорошо, я не поленюсь и всё снова повторю
Повторить? Или вы всё-таки признаете свою неправоту?

Кстати, сначала вы писали, что x=322. Привести цитату?
Потом вы уже стали исходить из x=323.
Так в этом примере решение есть в обоих случаях: и для x=322 и x=323.

Будете продолжать упорствовать в своей неправоте?
Тогда давайте показывайте конкретно: где в моём решении лишняя операция?

-- Пн апр 22, 2013 12:30:13 --

wanderers в сообщении #713971 писал(а):

Еще раз повторяю: ваша запись содержит операции (x-1, x*(x-1), a^2), которых нет в оптимальном решении.

Понимаю... у вас по алгебре в школе была двойка?

[wanderers]

Nataly-Mak в сообщении #713980 писал(а):

Понимаю... у вас по алгебре в школе была двойка?

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

[Pavlovsky]

Мне в моих алгоритмах все таки понадобилось разложение чисел на простые множители. Чтобы быстро вычислить разложение на простые множители выражения a+b (a-b), использовал процедуры:
1) Заранее посчитал разложения на простые множители для всех чисел меньших 300000.
2) Использовал преобразование a+b=d(a'+b'), где d= НОД(a,b). До идеи tomrokicki осталось совсем немного. Правда я так и не решился целиком положиться на эвристику, составлять последовательности только из делителей N! А идея tomrokicki основана на этой эвристике.

-- Пн апр 22, 2013 13:45:41 --

Опс следующие конкурсы:

Hell's Kitchen 13 Jul 2013 16:00
Alphabet City 21 Sep 2013 16:00

А вроде говорили, что следующий конкурс будет не раньше октября?!

[Nataly-Mak]

wanderers в сообщении #713984 писал(а):

Nataly-Mak в сообщении #713980 писал(а):

Понимаю... у вас по алгебре в школе была двойка?

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

А по делу будете отвечать?
Где в моём решении в 15 шагов лишняя операция?

*в сторону* д-а-а-а, тяжёлый случай. Ну, если ... упорствует, не старайся его переупорствовать - сам козлёночком станешь

-- Пн апр 22, 2013 12:57:06 --

wanderers в сообщении #713899 писал(а):

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

Может быть, здесь у вас банальная опечатка и вы хотели написать, что существует решение для x=322 и для x=323?
А в следующих постах вы на мой вопрос о решении для x=223 просто сказали, что не поняли вопроса.

Уж если вы взялись что-то "донести до сознания окружающих", то доносите полностью и по возможности правильно
Ошибаться, конечно, можно, но нужно признавать свои ошибки. В противном случае вряд ли вы чего-нибудь донесёте до сознания окружающих.

-- Пн апр 22, 2013 13:10:09 --

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

wanderers
вы утверждаете, что в этой записи 5 операций?
А в этой записи

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

сколько операций?
Неужели вы не видите, что в моём решении всё завершается как раз 4 операциями?

Здесь как раз и применено преобразование Pavlovsky:

A(A+1)CB^2=AB(AB+B)C

Простейшее алгебраическое преобразование, которое знает любой школьник.

[wanderers]

Nataly-Mak в сообщении #713990 писал(а):

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

wanderers
вы утверждаете, что в этой записи 5 операций?
.

Утверждаю.
1. 322+1
2.322*(322+1)
3.(322*(322+1))*12636
4.4435200^2
5.((322*(322+1))*12636)*(4435200^2)

[Nataly-Mak]

Цитата:

А в этой записи

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

сколько операций?
Неужели вы не видите, что в моём решении всё завершается как раз 4 операциями?

Здесь как раз и применено преобразование Pavlovsky:

A(A+1)CB^2=AB(AB+B)C

Простейшее алгебраическое преобразование, которое знает любой школьник.

А по поводу x=223 что вы утверждаете?
Это действительно надо понимать как x=223? Или это надо понимать как x=323?

-- Пн апр 22, 2013 13:42:12 --

Pavlovsky в сообщении #713985 писал(а):

Опс следующие конкурсы:

Hell's Kitchen 13 Jul 2013 16:00
Alphabet City 21 Sep 2013 16:00

А вроде говорили, что следующий конкурс будет не раньше октября?!

Это где-то не у Al Zimmermann?

[wanderers]

Слева 5 операций, а справа - 4 операции: этот неприложный факт не смжет опровергнуть даже самый заядлый двоечник.
И не надо про школу: именно я первый опубликовал прорывной подход к решению задачи, где как раз и используется тройка чисел (y, x, a):
post713672.html#p713672

[whitefox]

wanderers в сообщении #714015 писал(а):

Слева 5 операций, а справа - 4 операции: этот неприложный факт не смжет опровергнуть даже самый заядлый двоечник.

Извините, что вмешиваюсь, но у заядлого двоечника $2\cdot2=5$, так что он легко найдёт опровержение

[Nataly-Mak]

wanderers в сообщении #714015 писал(а):

... именно я первый опубликовал прорывной подход к решению задачи, где как раз и используется тройка чисел (y, x, a):

Ну... что тут скажешь?
Я не рискую стать козлёночком...
"прорывной подход" это хорошо, особенно если вы первый...

Всё-таки позволю себе заметить (ох, не стать бы козлёночком ), что именно решение с тройкой чисел для 23! и продемонстрировал Pavlovsky.

Цитата:

Применяем преобразование A(A+1)B^2=(AB)(AB+B)
322*(322+1)*12636* 4435200^2
(322*4435200)*(322*4435200+4435200)*12636
1,2,3,9,27,36,324,351,322,12636,4435236,4435200, 1428134400, 1432569600, 2045901926154240000, 25852016738884976640000
Итого 15 операций

Таким образом, он открыл вашу парадигму (y,x,a) независимо от вас. Точь-в-точь такую же парадигму с тройкой чисел, которая даёт решение для 23! в 15 шагов.

А я просто повторила решение по разложению, предложенному Pavlovsky. И нет в моём решении никакой лишней операции. Вот!

[wanderers]

Причем здесь Павловский? Вот что он писал только что: "wanderers Разобраться с вашим подходом мне нужно время. Поэтому не думайте, что ваши посты игнорируются".
Я пришел к своему алгоритму, изучая кропотливо решения для 13!, 14!, 15!, 16! и 17!

P.S.

(Оффтоп)

Зависть - отнють не лучшее из человеческих чувств. К счастью, природа меня обошла стороной с этим "подарком"

[Nataly-Mak]

wanderers в сообщении #714026 писал(а):

Причем здесь Павловский?

Ну, это уже даже не смешно.
Да притом, что он открыл эту вашу парадигму независимо от вас.
Я же привела цитату!

Цитата:

(Оффтоп)

Зависть - отнють не лучшее из человеческих чувств. К счастью, природа меня обошла стороной с этим "подарком"

Это кто тут кому завидует?
Есть тут один товарищ из Венгрии... Но больше тут завистливых отнюдь не бывало (кстати, отнюдь пишется через "д").

[wanderers]

Nataly-Mak в сообщении #714030 писал(а):

Это кто тут кому завидует?

(Оффтоп)

Кроме вас на эту кандидатуру никого не заметил

[Nataly-Mak]

wanderers в сообщении #714032 писал(а):

Nataly-Mak в сообщении #714030 писал(а):

Это кто тут кому завидует?

(Оффтоп)

Кроме вас на эту кандидатуру никого не заметил

(Оффтоп)

И кому же я завидую? Уж не вам ли?

-- Пн апр 22, 2013 14:48:37 --

Ну, а теперь я буду искать решение по второму разложению:

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

Уж сразу запишу так, чтобы было 4 операции

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

Так будет понятно?

Теперь (как и в прошлом примере) ищу на первом этапе по программе mertz все решения для числа 12636 в 8 шагов. Их нашлось 279.
На втором этапе ищу от найденных решений все решения, в которых 9-ым шагом появляется число 323. Таких решений найдено 9 штук.

found 14 solutions for 323 in 9 steps
1,2,3,4,9,36,39,324,12636,323
1,2,3,6,18,21,324,39,12636,323
1,2,3,6,18,36,324,39,12636,323
1,2,3,6,36,39,108,324,12636,323
1,2,3,6,9,36,39,324,12636,323
1,2,3,9,12,108,324,117,12636,323
1,2,3,9,12,27,39,324,12636,323
1,2,3,9,12,36,39,324,12636,323
1,2,3,9,18,21,324,39,12636,323
1,2,3,9,18,36,324,39,12636,323
1,2,3,9,27,36,324,351,12636,323
1,2,3,9,27,36,39,324,12636,323
1,2,3,9,81,162,78,161,12636,323
1,2,3,9,81,162,78,324,12636,323

Наконец, от найденных последовательностей ищу решение, в котором 11-ым шагом появляется число 4435200.
Такое решение найдено только одно:

found 1 solutions for 4435200 in 11 steps
1,2,3,9,27,36,324,351,12636,323,4435236,4435200

И теперь завершаю решение за 4 шага:

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

Это вторая парадигма для x=323.
Надеюсь, теперь нет лишних операций

wanderers
а опечатку x=223 вы хоть признаете? Или и тут будете что-то утверждать?

(Оффтоп)

Кстати, тот, кто пишет "я первый опубликовал прорывной подход к решению задачи", и есть первый завистник.