fixfix
2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 51, 52, 53, 54, 55, 56, 57 ... 88  След.
 
 Re: Factorials
Сообщение18.04.2013, 05:40 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #711551 писал(а):
И за сколько операций можно сформировать эти числа?
552129177600000,552204732119040,75554519040

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

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


22/03/08

7154
Саратов
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 шаг.

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


22/03/08

7154
Саратов
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

Вот борьба!

 Профиль  
                  
 
 Re: Factorials
Сообщение18.04.2013, 14:03 
Аватара пользователя


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #708470 писал(а):
Так что, 12-ое место надо держать зубами!


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

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


22/03/08

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

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


22/03/08

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

 Профиль  
                  
 
 Re: Factorials
Сообщение18.04.2013, 16:50 


02/11/12
141
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?

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


22/03/08

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

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

Это ж надо - решение нашлось при проверке 7-го варианта из 10. Нет бы в первом варианте нашлось --- закон подлости :D Пришлось впустую проверить аж 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
:D

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

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

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

 Профиль  
                  
 
 Re: Factorials
Сообщение19.04.2013, 04:28 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
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.

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


22/03/08

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

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

(Оффтоп)


Я прерываю программу при появлении 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 шагов!

 Профиль  
                  
 
 Re: Factorials
Сообщение19.04.2013, 06:10 


02/11/12
141
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.

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


22/03/08

7154
Саратов
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

 Профиль  
                  
 
 Re: Factorials
Сообщение19.04.2013, 06:22 


02/11/12
141
My runs for 18! and 19! used non-factor pruning. There could be more solutions.

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


22/03/08

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

 Профиль  
                  
 
 Re: Factorials
Сообщение19.04.2013, 08:53 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #712587 писал(а):
требуется уточнение: вы можете найти все 56 решений для 12! за 15 секунд? Или только первое решение? Это важно.


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

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

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



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

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


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

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