Factorials

[Pavlovsky]

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

У меня для 26! решение в 18 шагов.

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

Пример получился не очень удачный.

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

-- Чт мар 07, 2013 12:14:30 --

Или пример по проще:
165375*(165375+1) является делителем 22!

[Nataly-Mak]

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

Раньше вы радовались любому улучшению своих резвльтатов. А сейчас недовольны, что за 5 минут не удалось найти рекордное решение.

Здесь мне не удалось не только рекордное решение найти, но даже решение в 17 шагов (что улучшило бы моё решение всего на 1 шаг). Увы!

Цитата:

Заупустите программу mertz на большую глубину, может где то и проскочат нужные числа.

Уже запустила
К сожалению, программа эта хорошо (быстро) работает в пределах 10 шагов. При 11 шагах она работает уже очень долго.

-- Чт мар 07, 2013 12:14:30 --

Цитата:

Или пример по проще:
165375*(165375+1) является делителем 22!

Проще для чего?
Чтобы найти рекордное решение для N=22?
Ну, я вполне довольна своим решением в 16 шагов (на 2 шага больше рекордного).
И найдено это решение вручную и просто, проще некуда

[mertz]

If you click the "non-factor pruning" check box, you can run 11 steps quickly. It may miss some solutions. 12 steps runs a few hours on a 6 core/12 thread machine. My 13 step run for 18! is going to take over 3 days. Found 139 solutions so far.

[Nataly-Mak]

Я пока не пользовалась этой функцией. Последовательности в 11 шагов уже не так интересны в качестве начальной последовательности.

[dimkadimon]

Уже 400 участников!

Интересно какие евристики люди используют? Вот несколько вариантов:

1. Игнорировать негативные числа. Можно доказать что они не нужны.
2. Игнорировать операцию минус. Часто можно найти хорошее решение без этой операции.
3. Использовать только числа которые делители N!. Эта евристика экономит мне много вычислений, но конечно она убивает некоторые варианты решений. Насколько она вредна я не знаю.
4. Можно предположить что каждое новое число больше предыдущего, то есть последовательность не убывает. Если оно меньше то большая вероятность что мы его уже видили раньше. Но это не всегда работает. Самый простой пример: 1, 2, 4, 16, 15. Это самое короткое решение для 15 и тут мы обязаны спуститься вниз.
5. Можно предположить что нам никогда не придеться строить число больше N!. Опять это не всегда работает, например: 1, 2, 4, 8, 64, 128, 120.
6. Можно предположить что последние K операций умножения. Это часто хорошо работает, но не всегда.

[Nataly-Mak]

Ну вот и встретились

Цитата:

19 23.68 Kalachev Gleb Moscow, Russia 3 Feb 2013 16:52
20 23.64 Valery Pavlovsky Ekaterinburg, Russia 8 Mar 2013 10:14

Глеб выключился 3 февраля, уже больше месяца ничего не вводит.

Pavlovsky
в двадцатку вы уже прорвались. Вперёд, только вперёд! Удачи!

[Pavlovsky]

Увы, идея использования простой алгебры пока не дает результатов. Это странно. Два своих решения сумел улучшить на единицу. Неужели этими двумя решениями исчерпывается возможность использования свойства A*(A+1)*B^2=(A*B)*((A*B)+B)?!
Предыдущие идеи, пока еще дают результаты, но предел уже виден. Для рывка вперед нужны новые идеи.

19 23.70 Valery Pavlovsky Ekaterinburg, Russia 8 Mar 2013 14:56
20 23.68 Kalachev Gleb Moscow, Russia 3 Feb 2013 16:52

[dmd]

С самого начала использую только алгебраическую эвристику переборной решабельности целочисленного уравнения $f(a,b,c)=n!$. Наугад конструирую форму левой части с минимальным количеством шагов. Перебором получаю серию решений. Визуально выбираю из них два-три наиболее удачных на первый взгляд - наитие не запрограммируешь. Вручную строю последовательность для меньшего из $a,b,c$, т.к. число получаются достаточно небольшое и последовательность для него на 5-10 шагов всегда можно самостоятельно составить. Затем программно достраиваю последовательность для двух оставшихся чисел. В итоге длина полученной последовательности плюс длина формы $f(a,b,c)$ и будет результат этой полу-ручной работы. Рекорд таким образом ни в одном случае у меня не получился.

48    21.65    Dmitry Ezhov    Sterlitamak, Russia    8 Mar 2013 14:34

Сейчас это видимо предел для меня с этой эвристикой. Рекорды повторил с 13 по 20 кроме 19 - все вручную.



dimkadimon

С пунктами 2, 4, 5 не согласен. Объём перелопаченных мною чисел этого конкурса говорит об обратном.

Самое интересное, если среди $n>19$ окажется два-три подобных $n=19$ по трудности. Если так, то вероятно рекорды для них ещё не найдены.

[mertz]

Non-factor pruning still finds an answer for all N.

Ignore Subtraction is hit or miss.

Need a hybrid method that allows subtraction for the first i steps, allows addition for the first j steps. Only allow the previous k values to be used + and -. Only allow previous m values to be used for multiplication.

Google translate makes a mess of the table. View untranslated.

!--------------------------------! !---------------------------------! !-------------------------------!
! Complete search                ! ! Non-Factor Pruning              ! ! Ignore Subtraction            !
!                                ! !                                 ! !                               !  
! N   sols   nodes   time        ! ! N   sols   nodes       time     ! ! N   sols   nodes   time       !
!--------------------------------! !---------------------------------! !-------------------------------!
 6!      5    11K                    6!     2    3.9K                    6!     2      8K
 7!     18   228K                    7!    11     50K                    7!     0    133K
 8!     68     6M                    8!    51     31K                    8!     6    2.7M
 9!     18     6M                    9!    18    502K                    9!     0    2.7M
10!    104   200M   00:00:02        10!    77      9M                   10!    17      6M
11!     12   200M   00:00:02        11!    12     16M                   11!     0      6M
12!     56   7.8B   00:01:15        12!    48    309M     00:00:01      12!    45      2B  00:00:19
13!    445   357B   01:10:39        13!   116      9B     00:01:48      13!    28     68B  00:11:45
14!     65   357B   01:10:39        14!    62     12B     00:02:21      14!     0     68B  00:11:45
15!                                 15!   247    323B     00:58:31
16!                                 16!   215    354B     01:04:19
17!                                 17!    13    549B     01:39:49
18!                                 18!   139   26.8T  3d 13:59:57
19!     9  partial run              19!
20!                                      20!   212 partial run 

[dimkadimon]

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

Non-factor pruning still finds an answer for all N.

Ed, can you provide some examples of optimal solutions that use non-factors of N!.

[mertz]

6! = 720 = [6] 1,2,3,9,27,729,720
6! = 720 = [6] 1,2,3,9,81,729,720
7! = 5040 = [7] 1,2,3,9,81,72,70,5040
7! = 5040 = [7] 1,2,4,16,20,256,252,5040
7! = 5040 = [7] 1,2,4,6,36,1296,1260,5040
7! = 5040 = [7] 1,2,4,6,36,144,5184,5040
8! = 40320 = [8] 1,2,3,6,36,34,1156,1120,40320
8! = 40320 = [8] 1,2,4,8,10,64,4096,4032,40320
10! = 3628800 = [9] 1,2,4,8,64,60,240,57600,3686400,3628800

[Nataly-Mak]

dmd в сообщении #692747 писал(а):

Сейчас это видимо предел для меня с этой эвристикой. Рекорды повторил с 13 по 20 кроме 19 - все вручную.

Для сравнения:
не повторила ни одного рекорда. Все решения найдены вручную. Итог: 20,42 баллов (результат на 17 февраля).
Алгоритмы, которыми я пользовалась при ручном поиске решений, описаны выше.
В тех случаях, когда надо было найти представление некоторого числа (в пределах 10 шагов), пользовалась программой mertz. Эта программа выдаёт в некоторых случаях очень много решений; наиболее выгодное выбирала визуально.

[Nataly-Mak]

Интересно:
друг (занимается задачей для души без всяких программа, только вручную) прислал недавно оптимальное решение для N=16. Здорово! Я смогла найти только решение в 13 шагов.
Его решение основано на разложении:

$16! = A \cdot B^2$

Нашёл последовательность, содержащую А и В, и в завершение две операции умножения.
Красиво!

Моё решение в 13 шагов основано на разложении:

$16! = K \cdot (7!)^2$

[Pavlovsky]

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

1. Игнорировать негативные числа. Можно доказать что они не нужны.
2. Игнорировать операцию минус. Часто можно найти хорошее решение без этой операции.
3. Использовать только числа которые делители N!. Эта евристика экономит мне много вычислений, но конечно она убивает некоторые варианты решений. Насколько она вредна я не знаю.
4. Можно предположить что каждое новое число больше предыдущего, то есть последовательность не убывает. Если оно меньше то большая вероятность что мы его уже видили раньше. Но это не всегда работает. Самый простой пример: 1, 2, 4, 16, 15. Это самое короткое решение для 15 и тут мы обязаны спуститься вниз.
5. Можно предположить что нам никогда не придеться строить число больше N!. Опять это не всегда работает, например: 1, 2, 4, 8, 64, 128, 120.
6. Можно предположить что последние K операций умножения. Это часто хорошо работает, но не всегда.

1. Это не эвристика! Это математически доказанное свойство.
2. Это очень плохая эвристика. Операция минус позволяет получать очень хорошие числа. Если вести перебор от числа N! пока не получим, что все числа в последовательности определены. В этом случае возникает опасность "зацикливания". Когда A определяется как B-C, а B определяется как A+C. Для борьбы с зацикливанием можно запретить операцию вычитания. Но это очень плохое решение.
3. Эту эвристику активно использовал. Вроде работает нормально. Правда в последних своих подходах от нее отказался за ненадобностью.
4. Странный пункт. Эквивалентен запрету на вычитание.
5. Использую следующий вариант. Перебор начинаю с начальных последовательностей длины 8 (они у меня все есть около 7 миллионов). Задаю диапозон. Если максимальное число в начальной последовательности не входит в этот диапозон, то эту последовательность не рассматриваю. Трудно назвать это эвристикой. Мы просто разбиваем полный перебор на иттерации. Постепенно увеличивая диапозон, мы в конце концов сделаем полный перебор.
6. Это тоже вряд ли можно назвать эвристикой. Получив последовательность длины K, далее просто делаем упрощенный перебор, запретив операции сложения/вычитания. После того как получили все результаты, можно переходить к последовательностям длины K+1. При таком подходе мы ничего не теряем.
7. Еще использую эвристику. Фиксация начала последовательности. Например 1,2,4,16 или 1,2,4,16,256. Эта эвристика работает не плохо. Особенно на больших N. Впрочем это тоже эвристика управляющая порядком перебора. Перебрав все начала последовательностей, мы получим полный перебор.

[Nataly-Mak]

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

7. Еще использую эвристику. Фиксация начала последовательности. Например 1,2,4,16 или 1,2,4,16,256. Эта эвристика работает не плохо. Особенно на больших N. Впрочем это тоже эвристика управляющая порядком перебора. Перебрав все начала последовательностей, мы получим полный перебор.

Ну, а это какая же эвристика?
С чего-то надо начинать! Все с чего-то начинают.
Я, к примеру, начинаю с последовательности для N! при поиске решений для 2N! и (2N+1)!.
А иногда начинаю и с последовательности для (N-1)! (как в приведённом выше примере для N=16).
Ничего, нормально работает

Эд тоже использует базовые последовательности, они у него, кажется, из 5 членов состоят. Он писал об этом тут.