Factorials

[dimkadimon]

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

странно, что вы не нашли оптимальное решение для 30!
Я нашла его по алгоритму №1 в полуручном режиме (только воспользовалась программой mertz при составлении множителя K в разложении).
Включите ЕИ

Я тоже не нашёл N=30, но нашёл все оптимальные для N<28. Алгоритм 1 это который представляет 30! как А*(15!)^2? Если так то я проверил все свои решения для 15! и ничего не нашёл.

[Pavlovsky]

Я тоже проверил все свои решения для 15!. Но рекордного решения для 30! не нашел. Видать Наталия чего то не договаривает. Сейчас формирую расширенный список решений для 15!

[Nataly-Mak]

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

Алгоритм 1 это который представляет 30! как А*(15!)^2? Если так то я проверил все свои решения для 15! и ничего не нашёл.

Да, именно так.
Перепроверьте. Уверяю вас, что решение такого вида существует в 17 шагов.
Все ли вы решения проверили для 15!
Их всего 347 штук.

-- Пн апр 15, 2013 12:40:56 --

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

Я тоже проверил все свои решения для 15!. Но рекордного решения для 30! не нашел. Видать Наталия чего то не договаривает. Сейчас формирую расширенный список решений для 15!

Уже абсолютно всё договорила

[Pavlovsky]

96 19.57 Michael Marchenko Jakarta, Indonesia 15 Apr 2013 04:52

Упорство участника с типичной индонезийской фамилией заслуживает уважения.

http://forex-videoteka.ru/video/obuchen ... ti-13.html
Не даром парня из Джакарты знают все кругом...

[Nataly-Mak]

Меня фрау из Австрии восхищает

Цитата:

42 23.23 Alexandra Chrysothemis Salzburg, Austria 14 Apr 2013 23:56
46 23.15 Gennady Gusev Rybinsk, Russia 31 Mar 2013 16:57

Оставила далеко позади нашего Геннадия и почти каждый день идёт вперёд.
У меня есть предположение, что она неплохой капитан, ну, вроде меня

[Pavlovsky]

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

У меня есть предположение, что она неплохой капитан, ну, вроде меня

Наговариваете на себя. Лучше вас капитана не может быть! Одно дело командовать дисциплинированными австрийцами. Другое дело собрать в кучу россиян.

[Nataly-Mak]

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

Лучше вас капитана не может быть! Одно дело командовать дисциплинированными австрийцами. Другое дело собрать в кучу россиян.

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

Открою первый маленький секрет: в этот раз руковожу международной командой.
Трудно очень... Языковой барьер даёт себя знать.
Ну... как у меня получилось, расскажут участники команды по окончании конкурса.

[dimkadimon]

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

Наговариваете на себя. Лучше вас капитана не может быть! Одно дело командовать дисциплинированными австрийцами. Другое дело собрать в кучу россиян.

LOL!

[Nataly-Mak]

Мой последний супер-пупер алгоритм
Это уже изощрённый вариант алгоритма №1. Машина не осиливает у меня полный вариант. Приходится применять дробление процесса на части.
Берём последовательности "по частям"

Я этот алгоритм мучаю уже дней 5. С его помощью удалось найти улучшение решения для 32! (получено решение в 20 шагов).

Потом долго мучила алгоритм для 34!, 35!, 37!
Ничего не нашла.
И вот сейчас мучаю этот алгоритм для 36!
Последние попытки, я уже выдыхаюсь окончательно. Для 36! у нас решение очень плохое - 22 шага. Пытаюсь получить хотя бы 21 шаг.
Напишу, в чём суть алгоритма.
Берём всё то же разложение по алгоритму №1:
$36! = 9075135300 \cdot (18!)^2$

Я начинаю поиск от последовательностей, представляющих 18! без последнего члена, то есть начальные последовательности имеет вид:

$a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9,a_{10},a_{11},a_{13}$

Далее пишу вид искомой последовательности:

$a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9,a_{10},a_{11},a_{13},X,X,X,X,X,9075135300,18!,(18!)^2,36!$

Всё элементарно, но! моя машина не тянет такой поиск, в котором надо добавлять 6 шагов, как в этом примере. Более того, даже и добавление 5 шагов у меня улетает в беспредел по времени.
Вот поэтому приходится дробить число 9075135300 и искать частные.
В качестве делителей я выбираю не все подряд, а только те, которые либо имеются в самих начальных последовательностях, либо имеются среди чисел, порождаемых этими последовательностями.
Думаю, что дальше расписывать не надо, схема понятна.

Вот сейчас пытаюсь по этой схеме что-то найти для 36!
Проверка даже при добавлении 4-х шагов идёт примерно 1-2 часа, но это ещё терпимо, хотя проверить надо 26 вариантов.
Проверку при добавлении 5 шагов попросила выполнить товарища по команде, у него машина мощнее моей намного. Таких вариантов надо проверить всего 10, но у меня один такой вариант будет проверяться примерно 20 часов. Всё это мне не по силам проверить.
И самое плохое в этом то, что существование решения не гарантируется, его может и не быть.

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

[Nataly-Mak]

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

Я начинаю поиск от последовательностей, представляющих 18! без последнего члена, то есть начальные последовательности имеют вид:

$a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9,a_{10},a_{11},a_{13}$

Здесь, конечно, член последовательности $a_{12}$ просто пропустила.
Не ломайте голову, почему он отсутствует

Целый день выполняю проверку, осталось 5 вариантов, решений не найдено

[dimkadimon]

Вот моя последняя хорошая идея, может кому поможет. Представляем N! как A*B. Теперь находим самые короткие решения для А и B:

S1={а1, а2, ..., А}
S2={b1, b2, ..., B}

Таких решений может быть много, поэтому S1 и S2 множества. Теперь находим пару решений s1 (из S1) и s2 (из S2) так чтобы у них было наибольшее количество общих цифр. Теперь берём эти общие цифры о1, о2, ... и составляем полное решение. А может быть N!/2, a B может быть N!/((N!/2)^2).

[Pavlovsky]

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

А может быть N!/2, a B может быть N!/((N!/2)^2).

Для 28! можно использовать такие разложения:

1) 28!= 2615348736000^2*44574 Число которое берется в квадрате - максимально возможное.
2) 28!=(14!)^2*40116600
3) И даже возможно такое: 28!=(15!)^2*178296

Из приведенных примеров можно сделать вывод, что искать последовательности формирующие число, которое берется в первой степени нет смысла. Таких последовательностей будет слишком много. Достаточно найти последовательности для числа, которое берется в квадрате и пытаться их достроить (можно предварительно отрезать последние числа) до 28!

[dimkadimon]

A еще 28! = 552129177600000*552204732119040 = 552129177600000*(552129177600000+75554519040). Нужно отметить что все эти числа делители 28!.

[Pavlovsky]

И за сколько операций можно сформировать эти числа?
552129177600000,552204732119040,75554519040

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

[Nataly-Mak]

Так, я что-то не понимаю. Сообща будем искать решение для 28!
К чему все эти разложения? Я могу из программы mertz привести полный факторинг 28!
Там столько этих разложений!!
Но что это даёт? Все эти разложения проверить поштучно нереально.
А если есть программа проверки разложений, то и флаг вам в руки

whitefox сделал другие разложения, которых нет в программе mertz (точнее - они есть, но записаны в другой форме). Может и эти разложения выложить? До кучи, так сказать.