Factorials

[Nataly-Mak]

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

Эвристика согласна, что начало 1,2,3 плохое.

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

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

[Pavlovsky]

Contest  Kamenetsky Challenge 
Starts 20 Apr 2013 16:00
Ends 25 May 2013 16:00 
Prize $25 (Australian Dollars)

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


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

[dimkadimon]

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

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

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

[Nataly-Mak]

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

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

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

[dimkadimon]

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

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

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

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

[dimkadimon]

Вот в этих ситуациях мы можем убрать +/-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

[Pavlovsky]

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

Кстати преобразование 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 двух суток очень мало. Даже с этой эвристикой, пространство перебора огромное. Полный перебор давно уже заменил случайным поиском.

[Nataly-Mak]

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

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

[mertz]

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!

[Pavlovsky]

mertz надо поставить памятник на родине. Очень интересные данные.

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

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

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

[mertz]

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.

[dimkadimon]

I restrict all my solutions to use factors of the target and this got me to 24.47.

[Nataly-Mak]

После некоторого перерыва активизировался 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

[Pavlovsky]

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

Переживаю --- как бы Pavlovsky не проиграл, поставив на dmd

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

[Nataly-Mak]

По моей просьбе 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
как же вы такое допустили?
Ну, у вас ещё есть время поправить ситуацию.