Factorials

[dimkadimon]

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

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

552129177600000 за 13 операций, 552204732119040 за 14 операций, но общие числа только 1, 2, 3.

[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_{12},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_{12},a_{13},X,X,X,X,X,9075135300,18!,(18!)^2,36!$

Продолжаю описание данного алгоритма.
Итак, нам надо найти число 9075135300 за 6 шагов, начиная от указанных начальных последовательностей, представляющих 18! (без последнего члена).
Найти число за 6 шагов (а также и за 5 шагов) я не могу (машина не тянет).
Тогда представляю число 9075135300 в виде произведения двух сомножителей:
9075135300 = A*B (A<B)
и начинаю работать с этими разложениями.

На первом этапе надо проверить такие варианты, в которых множитель A является членом начальной последовательности. В этом случае множитель В должен формироваться за 5 шагов. Тяжёлый для меня случай Я его пропускаю (отправила все 10 вариантов товарищу по команде; но и у него этот поиск выполняется довольно долго).

На втором этапе проверяю такие варианты, когда множитель А находится среди чисел, порождаемых начальной последовательностью. Далее за 4 шага формируется множитель В, и оставшиеся шаги завершают формирование 36!
Я нашла много таких вариантов, сначала только 26, потом обнаружила ещё 19 вариантов. Возможно, это ещё не всё, вручную трудно проверить.
Ну, например, порождаемыми числами являются такие (они будут далее выступать в качестве множителя А):
5,10,11,15,20,21,28,30,33,35,42,50...

Все 45 вариантов проверила, ничего не нашла.

Далее перехожу к следующему этапу: среди всех множителей А (ну, не всех, конечно; все вручную найти нереально) ищу такие, которые могут появиться от начальной последовательности на 14-ом шаге (порождаемые последовательностью числа появляются на 13-ом шаге). Далее за 3 шага пытаюсь сформировать множитель В.
Таких А существует довольно много, например:
100,330,70,700,350,1050,690,6900,300...
Проверила около двух десятков таких вариантов. Ничего не нашла.

Следующий этап: среди множителей А ищу такие, которые пояляются от начальной последовательности на 15-ом шаге. Далее за 2 шага пытаюсь составить множитель В.
Интересно, что на этом этапе проверяю не только множители в порядке А --> В, но и в обратном порядке, то есть можно начинать с множителя А, потом искать множитель В, а можно и наоборот.
Так вот тут как раз когда начинала от множителя В, было найдено решение, в котором множитель В появился на 15-ом шаге.
Это разложение:

$9075135300=2900 \cdot 3129357$
$A=2900$
$B=3129357$

Множитель В появляется на 15-ом шаге, есть два решения.
К сожалению, множитель А не удалось сформировать за 2 шага, только за 3. Таким образом, получено решение в 22 шага, что мне уже не надо, такое решение у меня есть.

[Отмечу, что множитель А=2900 тоже появляется на 15-ом шаге, но множитель В=3129357 не удаётся потом составить ни за 2, ни за 3 шага.]

Работоспособность этого алгоритма доказана. Как я уже писала, по этому алгоритму мне удалось получить решение для 32! в 20 шагов.
Если делать полную проверку, ничего не пропуская (найти все делители, все порождаемые последовательностями числа), может быть, и в данном примере найдётся решение в 21 шаг.

[Nataly-Mak]

Pavlovsky
Опять германец наступает вам на пятки

Цитата:

12 24.63 Valery Pavlovsky Ekaterinburg, Russia 15 Apr 2013 03:37
13 24.61 Michael Hürter Saarbrücken, Germany 17 Apr 2013 15:39

Вот борьба!

[Pavlovsky]

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

Так что, 12-ое место надо держать зубами!

Чего то стало жалко зубы. Ведь оторвут вместе с зубами. Интерес к конкурсу резко стал падать. Мои программы выдали даже больше чем от них ожидал.

[Nataly-Mak]

Да, это верно; я уже тоже работаю по инерции. Интерес пропал, ничего нового в голову не приходит, хожу по кругу, уже голова кружится от этого кругового движения.
Скорее бы конец уже

[Nataly-Mak]

Этот конкурс подобен конкурсу с перекладыванием карт. Задачи такого типа не в моём вкусе: математики мало, превалирует переборная составляющая.
Не хочется писать даже маленькую статью об этом конкурсе.
Устала настолько, что уже и разбор алгоритмов и решений не интересует.

[mertz]

My first search for 12! took 9 hours. Now it takes 42 seconds. The programming has been fun. The problem was not interesting. Next contest for AZPC is September. What will we do till then?

[Nataly-Mak]

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

На первом этапе надо проверить такие варианты, в которых множитель A является членом начальной последовательности. В этом случае множитель В должен формироваться за 5 шагов. Тяжёлый для меня случай Я его пропускаю (отправила все 10 вариантов товарищу по команде; но и у него этот поиск выполняется довольно долго).

Есть! Решение получено!!

Это ж надо - решение нашлось при проверке 7-го варианта из 10. Нет бы в первом варианте нашлось --- закон подлости Пришлось впустую проверить аж 6 вариантов.
Но на 7-ом оно всё-таки нашлось!
С каким нетерпением я ждала результатов проверки...
Думала: неужели за 5 шагов нигде не составится множитель В. Составился!
Теперь у нас для 36! не плюс 4 от оптимального, а плюс 3.
Осталось безобразное плюс 4 от оптимального для 34! (21 шаг при оптимальном 17 шагов).

Вот и скажите теперь: имеет ли значение при поиске решений (в задачах с преобладанием перебора) мощность машины?! Я на своей машине это решение найти не смогла бы при всём желании и старании, ну не хватает у машины мощности, хоть застрелись

-- Чт апр 18, 2013 20:35:35 --

mertz в сообщении #712238 писал(а):

My first search for 12! took 9 hours. Now it takes 42 seconds. The programming has been fun. The problem was not interesting.

Да, программы ваши очень и очень хорошие!

Цитата:

Next contest for AZPC is September. What will we do till then?

Приглашаю вас решать мои проблемы:
http://www.primepuzzles.net/puzzles/puzz_663.htm
http://www.primepuzzles.net/puzzles/puzz_671.htm
http://www.primepuzzles.net/puzzles/puzz_681.htm
http://www.primepuzzles.net/puzzles/puzz_682.htm


-- Чт апр 18, 2013 21:07:54 --

Посмотрела свой рабочий файл, моё самое первое решение для 36! было в 27 шагов.
Теперь мы получили в 21 шаг. Прогресс налицо
Чуть-чуть не хватило сил дойти до оптимального решения.

Завтра попытаюсь сделать "задний ход" от 36! к 35!; для 35! у нас решение в 22 шага.
К сожалению, ход вперёд - от 36! к 37! - никак не получается за один шаг: ни в одном решении (а их получено 322) в последовательности нет готового числа 37, чтобы сразу домножить. Среди порождаемых чисел 37 есть, но тогда надо два шага и получается решение в 23 шага; такое у нас уже есть.

[dimkadimon]

mertz в сообщении #712238 писал(а):

My first search for 12! took 9 hours. Now it takes 42 seconds. The programming has been fun. The problem was not interesting. Next contest for AZPC is September. What will we do till then?

I can find 12! in 15 seconds, but perhaps I have a faster machine. We need to test on larger N. How quickly can you find 19? I can find it in 70 seconds.

Remember there is my contest starting as soon as this one finishes. TopCoder has a marathon match round 2 starting on 1st of May.

[Nataly-Mak]

dimkadimon
требуется уточнение: вы можете найти все 56 решений для 12! за 15 секунд? Или только первое решение? Это важно.
Как я понимаю, mertz выполняет полный поиск всех 56 решений за 42 секунды.

На моей машине по прогрмме mertz для 12! первые 6 решений появляются на 45-ой секунде; все 56 решений появляются через 3 минуты.

(Оффтоп)

1,2,4,16,18,288,304,5184,92416,92400,479001600
1,2,4,16,18,288,304,5472,1663488,1663200,479001600
1,2,4,16,18,288,304,92416,1663488,1663200,479001600
1,2,4,16,18,288,304,92416,92400,1663200,479001600
1,2,4,16,18,288,304,92416,92400,26611200,479001600
1,2,4,16,18,288,5184,5472,29942784,29937600,479001600
1,2,4,6,12,144,150,154,21600,22176,479001600
1,2,4,6,12,144,150,154,21600,3110400,479001600
1,2,4,6,12,144,150,154,21600,3326400,479001600
1,2,4,6,12,144,150,154,22176,3193344,479001600
1,2,4,6,12,144,150,154,22176,3326400,479001600
1,2,4,6,12,144,150,154,23100,3326400,479001600
1,2,4,6,12,144,150,20736,154,23100,479001600
1,2,4,6,12,144,150,20736,154,3110400,479001600
1,2,4,6,12,144,150,20736,154,3193344,479001600
1,2,4,6,12,144,150,576,21600,22176,479001600
1,2,4,6,24,144,150,154,21600,22176,479001600
1,2,4,6,24,144,150,154,21600,3110400,479001600
1,2,4,6,24,144,150,154,21600,3326400,479001600
1,2,4,6,24,144,150,154,22176,3193344,479001600
1,2,4,6,24,144,150,154,22176,3326400,479001600
1,2,4,6,24,144,150,154,23100,3326400,479001600
1,2,4,6,24,144,150,20736,154,23100,479001600
1,2,4,6,24,144,150,20736,154,3110400,479001600
1,2,4,6,24,144,150,20736,154,3193344,479001600
1,2,4,6,24,144,150,576,21600,22176,479001600
1,2,4,6,24,30,576,720,21600,22176,479001600
1,2,4,6,24,30,576,900,21600,22176,479001600
1,2,4,6,24,30,576,900,924,518400,479001600
1,2,4,6,24,30,576,900,924,532224,479001600
1,2,4,6,24,30,576,900,924,831600,479001600
1,2,4,6,24,30,720,900,518400,924,479001600
1,2,4,6,24,30,720,900,924,665280,479001600
1,2,4,6,24,30,900,924,21600,19958400,479001600
1,2,4,6,24,30,900,924,21600,22176,479001600
1,2,4,6,24,30,900,924,21600,518400,479001600
1,2,4,6,24,30,900,924,22176,19958400,479001600
1,2,4,6,24,30,900,924,22176,532224,479001600
1,2,4,6,24,30,900,924,831600,19958400,479001600
1,2,4,6,24,36,576,600,21600,22176,479001600
1,2,4,6,24,576,600,3600,21600,22176,479001600
1,2,4,6,24,96,90,2304,2310,207360,479001600
1,2,4,6,24,96,90,2304,2310,207900,479001600
1,2,4,6,24,96,90,2304,2310,5322240,479001600
1,2,4,6,36,144,150,154,21600,22176,479001600
1,2,4,6,36,144,150,154,21600,3110400,479001600
1,2,4,6,36,144,150,154,21600,3326400,479001600
1,2,4,6,36,144,150,154,22176,3193344,479001600
1,2,4,6,36,144,150,154,22176,3326400,479001600
1,2,4,6,36,144,150,154,23100,3326400,479001600
1,2,4,6,36,144,150,20736,154,23100,479001600
1,2,4,6,36,144,150,20736,154,3110400,479001600
1,2,4,6,36,144,150,20736,154,3193344,479001600
1,2,4,6,36,144,150,576,21600,22176,479001600
1,2,4,8,12,144,152,20736,23104,23100,479001600
1,2,4,8,12,144,152,23104,23100,3326400,479001600

Я прерываю программу при появлении 56 решений, так как знаю, что больше решений нет. Но программа отработала только 42%, следовательно, до конца работы ей требуется ещё более 3 минут.

-- Пт апр 19, 2013 07:03:10 --

Сейчас уместно привести сообщение YuriiS на форуме ПЕН:
http://e-science.ru/forum/index.php?s=& ... t&p=393039

Цитата:

Если у кого есть желание и минута свободного времени, то развейте "страшные" слухи по поводу 19! на dxdy: это как раз самый благоприятный вариант из всех возможных для компьютерной реализации - у меня он проходит за неуловимые доли секунды. При расчете не учитывалась специфика 19!, а использовался общий подход.

YuriiS участник конкурса (см. Yurii Sigolaev).

У меня есть предположение, что здесь речь идёт о поиске только одного решения, а не всех 9 решений (а и всех-то, кажется, не 9 ), но могу ошибаться. Хотя трудно поверить, что полный поиск для 19! может выполниться за "неуловимые доли секунды"
Это всё-таки решения в 13 шагов!

[mertz]

Search of 2.9 quadrillion nodes for 19! in 70 seconds? It would take me a few months.

Currently re-running 12 step search for 15!, 16! and 17! A little less than 2 hours per trillion nodes.

[Nataly-Mak]

mertz
Так для 19! вы не нашли все решения? 9 решений - это только часть всех решений?
Для 18! 139 решений, это все?
Скорее всего, моё предположение верное: и dimkadimon и YuriiS говорят о поиске только одного решения для 19!

Ура! Наш Геннадий обошёл фрау из Австрии:

Цитата:

44 23.31 Gennady Gusev Rybinsk, Russia 18 Apr 2013 18:18
45 23.31 Alexandra Chrysothemis Salzburg, Austria 15 Apr 2013 19:38

[mertz]

My runs for 18! and 19! used non-factor pruning. There could be more solutions.

[Nataly-Mak]

А-а-а, поняла.
Вы использовали ограничение и при этом могли пропустить некоторые решения.

[dimkadimon]

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

требуется уточнение: вы можете найти все 56 решений для 12! за 15 секунд? Или только первое решение? Это важно.

Я нахожу 45 решений для 12 за 15 секунд. Все числа делители 12!
Я нахожу первое решение для 19 за 70 секунд и ещё два за 15 секунд.