Factorials

[Nataly-Mak]

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

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

Эвристика тривиальная: домножить результат для 26! на 27.

А если попробовать наоборот? Скажем есть решение 19 шагов для 34! А для 33! лучшее решение 20 шагов. Можно ли из решения для 34! убрать число 34, чтобы получить решение для 33!

"Задний ход" применяла неоднократно. Иногда получается.
Посмотрите, где можно в решении для 34! убрать умножение на 34 (на 2 и на 17).
С числом 34 вряд ли получится (убрать), так как в его разложении присутствует простое число 17, на которое довольно сомнительны умножения в процессе вычислений.
Но чем чёрт не шутит

Кстати, мой печальный опыт...
у нас в команде решение для 26! есть в 15 шагов, а решение для 25! аж в 18 шагов.
Сколько ни билась сделать "задний ход" (убрать умножение на 26), ни фига не получилось, хоть застрелись
Число 26 тоже очень плохое, ибо $26=2 \cdot 13$.

"Ход вперёд" работает гораздо эффективнее. Причём я применяю его не только при переходе от N к (N+1), но и от N к (N+m), где m>1.
Например, элементарно получаю улучшение для решения 32! от решения в 30! домножением на $31 \cdot 32=992$.

[dimkadimon]

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

А если попробовать наоборот? Скажем есть решение 19 шагов для 34! А для 33! лучшее решение 20 шагов. Можно ли из решения для 34! убрать число 34, чтобы получить решение для 33!

Ход назад возможен, но я его не так делаю. Я беру первые 6-12 цифр из (N+1)! и достраиваю до N! Иногда работает.

[Nataly-Mak]

То ли дело - число 36

От решения для 36! замечательно делается "задний ход" к решению для 35! (убираем умножение на 36).
Проверено на личном опыте

[Pavlovsky]

Ну чтож попробуем "Задний ход". Все равно прорывных идей нет, и похоже не будет. Хотя прогноз, что я выйду на отметку 24,5 балла остается в силе. Думаю запустить что ли случайный выбор начальных последовательностей и пусть мои алгоритмы весь последний месяц конкурса работают. Найдут, хорошо. Не найдут, значит судьба.

-- Вс мар 24, 2013 17:32:27 --

45 22.62 Viktor Polesov Moskow, Russia 24 Mar 2013 12:01
46 22.60 Dmitry Ezhov Sterlitamak, Russia 23 Mar 2013 19:07

Вот это заруба! Вцепились друг в друга мертвой хваткой! Делаем ставки? По понятным причинам, ставлю на dmd.

[Nataly-Mak]

Pavlovsky
вы, как всегда, очень наблюдательны.
Жду, когда вы "вычислите" мою команду

[Nataly-Mak]

Кажется, выжала из алгоритма №1 всё
Почти уверена, что этот алгоритм не даёт оптимальных результатов ни для каких N>12, то есть для всех конкурсных задач.
Вот, например, какие результаты удалось выжать мне:

19 20 21 22 23 24 25
15 15 15 16 17 17 18

Дальше тупик.
Напомню, алгоритм №1 - это использование разложений:

$2n! = K(n!)^2$
$(2n+1)! = K(n!)^2$

[Nataly-Mak]

Оказалось, не всё выжала
Совсем забыла, что можно пользоваться, например, такими разложениями:

$(2n+1)! = K((n-1)!)^2$
$(2n+1)! = K((n-2)!)^2$
и т.д.

[Nataly-Mak]

И ещё прыжок - понедельничный

Цитата:

19 23.92 Vladimir Chirkov Bobruisk, Russia 25 Mar 2013 12:01

И на пороге клуба 24+
А там и десятка не так уж далеко. Удачи, Владимир!

[Pavlovsky]

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

Думаю запустить что ли случайный выбор начальных последовательностей

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

[Nataly-Mak]

У меня вырисовывается такая картина: алгоритмом №1 можно найти решения (почти для всех N) всего на 1 шаг больше оптимальных.
До N=28 мне это удалось.
Сейчас буду мучить N=29, пока имею решение в 19 шагов.

[Vovka17]

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

А там и десятка не так уж далеко. Удачи, Владимир!

Спасибо!
Все мои ранние прогнозы о скорости работы программы оказались очень далеки от ужасающей реальности - более десяти суток беспрерывных расчетов для достижения текущих значений:

   n ... 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
tops ... 15 15 16 15 16 16 17 17 18 18 18 17 19 18 20
  my ... 16 15 16 17 16 17 18 19 20 19 19 19 21 21 23

При этом отрезалось и сокращалось всё что только можно и где можно. Как следствие, многие топовые значения (особенно для старших n) оказались за бортом.
Впрочем, пока был задействован лишь один поток и, поэтому, теоретически всё можно ускорить в разы. Зато всю неделю только результаты вводил (отдохнул - во! ) - вот так я люблю участвовать, когда, лишь сливки снимать !
По плану - сейчас несколько дней финального кодинга и, в последний бой!

[dimkadimon]

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

То ли дело - число 36

От решения для 36! замечательно делается "задний ход" к решению для 35! (убираем умножение на 36).
Проверено на личном опыте

Забавно, а у меня наоборот. У меня есть решение для N=36 (с числом 36) которое на один шаг лучше N=35, но я никак не могу из него сделать хорошее N=35. Просто удалить число 36 невозможно потому что оно используется в самом начале для построения других чисел.

[Nataly-Mak]

Надо удалять не само число 36, а "умножение на число 36" (если такое умножение используется в процессе вычислений). Это большая разница

[dimkadimon]

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

Надо удалять не само число 36, а "умножение на число 36" (если такое умножение используется в процессе вычислений). Это большая разница

Но наверно это возможно только если к результату ничего не прибавляется. У меня ситуация такая: ... B, A, 36, 36A, 36A+B ... 36!

[Nataly-Mak]

Разумеется!
Имеется в виду, что результат 36! не умножаем на 36, получая таким образом результат 35!
В вашем случае это было бы возможно, если В кратно 36.