2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 46, 47, 48, 49, 50, 51, 52 ... 88  След.
 
 Re: Factorials
Сообщение02.04.2013, 09:23 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Pavlovsky в сообщении #704655 писал(а):
Эвристика согласна, что начало 1,2,3 плохое.

Ничего оно не плохое!
Это начало имеет очень хорошее свойство: в некоторых решениях оно взаимозаменяемо с началом
1,2,4.
Например, в оптимальном решении для 26!, которое есть у нашей команды, как раз это свойство имеет место.
А между прочим, для получения других решений от оптимального решения для 26! иногда как раз нужнее число 3, нежели число 4. Многократно с этим сталкивалась.

Так что, я бы не стала особо увлекаться идеей игнорирования нечётных чисел :wink:

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


21/02/10
1594
Екатеринбург
Код:
Contest  Kamenetsky Challenge
Starts 20 Apr 2013 16:00
Ends 25 May 2013 16:00
Prize $25 (Australian Dollars)


Как я понял поиск последовательности для 100!


Увы платформа 1С, на которой я пишу, 150-значные числа не потянет.

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


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #704763 писал(а):
Как я понял поиск последовательности для 100!


Приглашаю всех на мое первое соревнование! Сейчас не буду говорить про задачу, но скоро сами узнаете :)

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


22/03/08

7154
Саратов
Хорошо хоть сейчас нет никаких потерь.
Рекорды закончились, кажется. Пока не видно их на горизонте :-)

dimkadimon
это где будет проводиться ваше соревнование? Подробнее расскажите, пожалуйста.

Ну, вы бы дали хоть чуть-чуть отдохнуть после текущего конкурса :D

 Профиль  
                  
 
 Re: Factorials
Сообщение03.04.2013, 00:20 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #705007 писал(а):
это где будет проводиться ваше соревнование? Подробнее расскажите, пожалуйста.

Ну, вы бы дали хоть чуть-чуть отдохнуть после текущего конкурса :D


Соревнование будет проходить на сайте AZ и будет длиться 5 недель. Приз пока что $25 Австралийских долларов. Я сам вложу изначальное решение чтобы было с чем соревноваться. Надеюсь будет интерес.

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


01/06/12
1016
Adelaide, Australia
Вот в этих ситуациях мы можем убрать +/-1 ничего не теряя:

1, A, B, B+1, AB+A = 1, A, B, AB, AB+A
1, B, B+1, B^2+B = 1, B, B^2, B^2+B
1, B, B+1, 2B+2 = 2, B, 2B, 2B+2

А вот в этих ситуациях ничего не поделаешь:

1, B, B+1, B^2+2B+1
1, B, B+1, 2B+1
1, A, B, B+1, A-(B+1)
1, A, B, B+1, A+B+1

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


21/02/10
1594
Екатеринбург
Где то так. Хотя тема алгебраических преобразований последовательностей еще мало исследована. Может существуют более сложные алгебраические преборазования.

Кстати преобразование A(A+1)B^2=(AB)(AB+B) можно немного обобщить.
A(AC+1)B^2=(AB)(ABC+B). При C=1 получается предыдущее преобразование.

Ну и до кучи. Если AB=C^2, тогда (C+A)(C-B)=C(A-B).

-- Ср апр 03, 2013 13:39:13 --

Эвристику запрета операций с единицей, тестирую уже вторые сутки. Пока результатов нет. Но это ничего не значит. Для N>30 двух суток очень мало. Даже с этой эвристикой, пространство перебора огромное. Полный перебор давно уже заменил случайным поиском.

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


22/03/08

7154
Саратов
Да, вот кластер мне сейчас очень даже пригодился бы :-)
Кто-то тут доказывал, что использование кластера никоим образом не влияет на результаты.
Ой ли?!
Вот у меня есть замечательная программа mertz, которая, как я уже рассказывала, ищет решения для любого числа (не обязательно факториалы). Но! Программа работает приемлемо в пределах 10 шагов, по крайней мере, у меня.
Сейчас, к примеру, пытаюсь найти решения для числа 10816624.
В 10 шагов нашлось 12 решений, это довольно быстро, где-то около часа.
Теперь ищу решения в 11 шагов. И тут уже улетаю в беспредел по времени.
При этом поиск начинаю с готовой БД - последовательности из 7 членов (6 шагов)
(это уже "зашито" в программе). Остаётся добавить всего 5 шагов.
Показываю окно программы. Исходя из того, что уже отработано, делаю вывод: всего потребуется примерно 22 часа.
Программа сделана с многопоточным программированием. Очень хорошая программа!
Но у меня всего 2 ядра :-(
Задаю 4 потока, больше не рискую. Я в это время выполняю ещё одну программу (такую же), но во второй программе уже задаю 2 потока (там поиск поменьше и работает быстрее).

Вот так-то! Где бы взять кластер? :D

Изображение

 Профиль  
                  
 
 Re: Factorials
Сообщение03.04.2013, 15:46 


02/11/12
141
Found all 13 solutions for 17! in 15 minutes using non-factor and even values only pruning. Translation makes a mess of the table.

Код:
!---------------------------------! !----------------------------------! !----------------------------------! !----------------------------------!
! Complete search                 ! ! Non-Factor Pruning               ! ! Even Numbers Only                ! ! Non-Factor and Even Numbers Only !
!                                 ! !                                  ! !                                  ! !                                  !
! N  opt  sols  nodes     time    ! ! N   sols   nodes       time      ! ! N   sols   nodes       time      ! ! N   sols   nodes       time      !
!---------------------------------! !----------------------------------! !----------------------------------! !----------------------------------!
6!  [6]    5    11K                  6!     2    3.9K                     6!     2    2.7K                     6!     2    372
7!  [7]   18   228K                  7!    11     50K                     7!     9     49K                     7!     4    3.9K
8!  [8]   68     6M                  8!    51    330K                     8!    43    1.2M                     8!    27    93K
9!  [8]   18     6M                  9!    18    518K                     9!     8    1.2M                     9!     8   125K
10!  [9]  104   202M    00:00:01     10!    77   10.2M                    10!    41     38M                    10!    24   2.3M
11!  [9]   12   202M    00:00:01     11!    12   17.2M                    11!     1     38M                    11!     1   3.5M
12! [10]   56   7.9B    00:01:25     12!    48    318M     00:00:01       12!    56    1.4B     00:00:12       12!    38    68M
13! [11]  445   358B    01:08:58     13!   116    9.7B     00:01:44       13!   170     59B     00:09:35       13!    31   1.8B      00:00:21
14! [11]   65   358B    01:08:58     14!    62   12.9B     00:02:19       14!    56     59B     00:09:35       14!    53   2.4B      00:00:26
15! [12]  347  18.9T 2d 07:10:35     15!   247    331B     00:58:31       15!   220    298B     08:20:08       15!   170    56B      00:08:25
16! [12]  215  18.9T 2d 07:10:35     16!   215    360B     01:08:45       16!    39    298B     08:20:08       16!    39    70B      00:10:23
17! [12]   13  18.9T 2d 07:10:35     17!    13    558B     01:46:03       17!    13    298B     08:20:08       17!    13   104B      00:15:16
18! [13]                             18!   139   26.8T  3d 13:59:57       18!                                  18!
19! [13]                             19!                                  19!                                  19!

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


21/02/10
1594
Екатеринбург
mertz надо поставить памятник на родине. Очень интересные данные.

Для 13! эвристики "делители факториала" и "четные числа" дают практически различные решения!

Странно, что для 16! эвристика "четные числа" работает хуже чем эвристика "делители факториала".

Экономия по времени перебора просто потрясает! Значит у меня еще есть шансы найти новые решения! Правда после публикации этой таблицы, шансы появились у всех!

 Профиль  
                  
 
 Re: Factorials
Сообщение03.04.2013, 17:03 


02/11/12
141
I am waiting for the end of the contest to hear about the different pruning methods.

Цитата:
ben_burrows to message # 688711 wrote (a):
I impose a pruning rule that eliminates any number which is not a factor of the target (using the slow% operator). This is sufficient up to N = 12! ... but I am becoming concerned that 13! requires more "exotic" calculations.


From Herbert Kociemba

Цитата:
No, it is sufficient for many cases. I can confirm, that with this restriction it is possible to get for N = 13 to N = 37
11 11 12 12 12 13 13 14 14 15 15 15 16 17 17 17 18 19 20 18 20 18 20 20 20


Herbert's comments after the contest will be interesting.

 Профиль  
                  
 
 Re: Factorials
Сообщение04.04.2013, 00:18 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
I restrict all my solutions to use factors of the target and this got me to 24.47.

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


22/03/08

7154
Саратов
После некоторого перерыва активизировался dmd

Цитата:
36 23.46 Viktor Polesov Moskow, Russia 2 Apr 2013 19:13
51 22.66 Dmitry Ezhov Sterlitamak, Russia 3 Apr 2013 17:51

Догонит своего противника, с которым шёл вровень?
Переживаю --- как бы Pavlovsky не проиграл, поставив на dmd :D

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #705530 писал(а):
Переживаю --- как бы Pavlovsky не проиграл, поставив на dmd


Я переживу, лишь бы Россия от внутреннего соперничества выиграла. А пока россияне решают локальные задачи, в мировом зачете Россию обогнала Англия.

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


22/03/08

7154
Саратов
По моей просьбе mertz добавил в программу подробнейший факторинг.

Изображение

Выбрала для 24! такое разложение:

$24! =81800719 \cdot 87091200^2$

Для числа 87091200 нашлось 5 решений в 9 шагов и 1017 решений в 10 шагов.
Для числа 81800719 не нашлось ни одного решения ни в 9, ни в 10 шагов.
Такие вот разные числа. А чем они отличаются? Ну, прежде всего тем, что одно из них чётное, а другое нечётное.

Хоть и много нашла решений для числа 87091200, решение для 24! так и не получилось.
Мне эти числа понравились тем, что они одного порядка. Думала, что-то должно получиться. Мимо! :-(

24! единственное осталось для N<32, для которого решение плюс 2 от оптимального. Никак не поддаётся, даже 16 шагов нет.

-- Пт апр 05, 2013 08:50:59 --

Pavlovsky в сообщении #705952 писал(а):
А пока россияне решают локальные задачи, в мировом зачете Россию обогнала Англия.

Pavlovsky
как же вы такое допустили? :D
Ну, у вас ещё есть время поправить ситуацию.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1310 ]  На страницу Пред.  1 ... 46, 47, 48, 49, 50, 51, 52 ... 88  След.

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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