Factorials

[Nataly-Mak]

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

Я не очень разобрался в генерации базы данных но видимо алгоритм достаточно быстрый если он смог найти N=31 за пол часа на 14 ядрах. Или я что то не так понял?

Я не знаю, как искал все решения для 15! mertz и сколько он на это потратил времени.
Это, собственно, и есть один из аспектов генерации БД.
Вот эта маленькая часть БД у меня была, 347 решений для 15! в 12 шагов.

Исходя от этой готовой БД, я нашла оптимальное решение для 30! за 2 минуты (по программе mertz).
Здесь это решение показано.

Это просто пример, как на основе уже готовой БД (не всей, а только маленькой её части!) и по тем самым "прорывным" формулам, которые нам тут преподнёс wanderers, можно достаточно быстро находить оптимальные решения.

Как я понимаю, БД не надо каждый раз генерировать заново. Вот, к примеру, есть все 347 решений для 15!, их можно ведь использовать каждый раз, когда в формуле (в разложении) фигурирует 15!
Я так и делала, и не только с 15!
mertz прислал мне все решения для N=6-20, которые он нашёл. На основе этой БД я искала решения.

Сам процесс построения БД может занимать очень много времени, я с этим полностью согласна. Способ записи и хранения БД тоже очень важен.
Это, по-моему, все отлично понимают, по крайней мере, те, кто прошёл весь этот конкурс.
И не надо тут намекать, что "или не в теме или..." ну, дураки совсем, что не понимают такие простые вещи.

[wanderers]

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

[и по тем самым "прорывным" формулам, которые нам тут преподнёс wanderers

(Оффтоп)

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

-- 23.04.2013, 12:08 --

whitefox в сообщении #714458 писал(а):

Сообщил только, что его алгоритм строит для каждого n по две таблицы, используя формулы n!=a*c^2 и n!=(x*a)(x*a-a)*y

"Сообщил только" - сильно сказано. Этого сообщения достаточно было бы даже за месяц до окончания конкурса, чтобы все, даже с захудалыми базами данных, набрали бы 25 баллов.

[Nataly-Mak]

Что касается первой формулы:
$N! = A \cdot B^2$

Я сначала работала с формулой, в которой $B=(N/2)!$
Потом сама собой, вполне закономерно, пришла идея использовать в качестве числа В другое число, а не только (N/2)!.

Этот метод дал неплохие результаты (некоторые из них здесь показаны).

mertz тоже работал над реализацией этого простого метода.
Он присылал мне все свои результаты, чтобы я смогла по полученной информации эффективнее организовать свой поиск.

Вот фрагмент таблицы, составленной mertz:

....
65 1 276905574400 * 7484400 ^ 2 opt = 9 count = 492
66 1 1107622297600 * 3742200 ^ 2 opt = 9 count = 1457
67 1 4430489190400 * 1871100 ^ 2 opt = 9 count = 1567
68 1 17721956761600 * 935550 ^ 2 opt = 9 count = 1362
69 1 70887827046400 * 467775 ^ 2 opt = 9 count = 6503
70 0 152108775 * 319334400 ^ 2 opt = 10 count = 12
71 1 152108775 * 319334400 ^ 2 opt = 10 count = 27
72 1 608435100 * 159667200 ^ 2 opt = 10 count = 64
73 1 2433740400 * 79833600 ^ 2 opt = 10 count = 141
74 1 9734961600 * 39916800 ^ 2 opt = 9 count = 1578
75 1 38939846400 * 19958400 ^ 2 opt = 9 count = 437
76 1 155759385600 * 9979200 ^ 2 opt = 9 count = 934
77 1 623037542400 * 4989600 ^ 2 opt = 9 count = 1273
78 1 2492150169600 * 2494800 ^ 2 opt = 9 count = 2819
....

Это был поиск оптимального решения для 25! по данному алгоритму.
76-ая строка этой таблицы дала результат - решение в 16 шагов.
Точно такое же решение было найдено нами с whitefox; это выше подробно рассказано, но мы шли другим путём, начиная от поиска решения для 22!

Вот вам пример таблицы "в два столбца" Ничего хитрого абсолютно. Кто в конкурсе участвовал, всё это проходил.

[wanderers]

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

Вот вам пример таблицы "в два столбца" Ничего хитрого абсолютно. Кто в конкурсе участвовал, всё это проходил.

Угу, и все вашими табуреточными методами набрали 25 баллов.

[Nataly-Mak]

Интересно описание, данное mertz к показанному поиску:

Цитата:

partial results of A * B ^ 2 for 25!
restrictions
A < 500000000 or B < 500000000

optimal length <= 10

base sequences = optimal length and optimal length + 1
database: solutions <= 10 steps, 3 to 500000000

ran job 75, 76 and 77.
success on 76, known result.

[Pavlovsky]

wanderers в сообщении #714468 писал(а):

"Сообщил только" - сильно сказано. Этого сообщения достаточно было бы даже за месяц до окончания конкурса, чтобы все, даже с захудалыми базами данных, набрали бы 25 баллов.

Не понял. А что тогда вам помешало набрать 25 баллов?!

[wanderers]

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

wanderers в сообщении #714468 писал(а):

"Сообщил только" - сильно сказано. Этого сообщения достаточно было бы даже за месяц до окончания конкурса, чтобы все, даже с захудалыми базами данных, набрали бы 25 баллов.

Не понял. А что тогда вам помешало набрать 25 баллов?!

Ответ на этот вопрос уже был:
post713899.html#p713899
Я не свободный художник и мог уделять время задаче лишь урывками.

[Pavlovsky]

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

Покажу найденное мной оптимальное решение для 30!
Тут сомневались, что такое решение существует в виде
$30! = A \cdot (15!)^2$

Вот это решение:

1,2,4,6,36,34,216,180,6120,6336,1140480,1146600,25344,25346,155117520,1307674368000,
1710012252724199424000000,265252859812191058636308480000000

$30! = 155117520 \cdot (15!)^2$

Поиск начинается от начальной последовательности, представляющей 15!, без последнего члена. Число 155117520 от этой последовательности составляется всего за 3 шага!
Были, конечно, проверены все последовательности для 15! (их 347 штук); программа mertz выдала для числа 155117520 только два решения.
Это второе решение:

1,2,4,6,36,216,180,176,6336,6120,1140480,1146600,25344,25346,155117520,
1307674368000,1710012252724199424000000,265252859812191058636308480000000

Увы, моя программа за отведенное ей время не может найти решения для 15!, начинающееся с 1,2,4,6,36,34,216,180. Поэтому я так и не нашел оптимальное решения для 30!
Вот начальные последовательнсти для 15!, для которых, моей программой, было найдены решения в 12 операций.

(Оффтоп)

1,2,3,6,36,38,30,1080,1078
1,2,3,6,36,30,1080,1078,1076
1,2,3,6,36,30,1080,1078,1042
1,2,3,6,36,30,1080,1050,1056
1,2,3,9,10,12,21,120,1440
1,2,3,9,10,12,21,144,1440
1,2,3,9,10,12,120,1440,1430
1,2,3,9,10,12,144,1440,1430
1,2,3,9,12,108,324,336,108864
1,2,4,5,20,100,104,108,10800
1,2,4,5,20,100,500,504,50400
1,2,4,6,10,36,144,5184,5148
1,2,4,6,10,36,144,5184,5040
1,2,4,6,36,35,1260,5040,181440
1,2,4,6,36,35,1260,45360,181440
1,2,4,6,36,35,1260,144,181440
1,2,4,6,36,38,30,1080,1078
1,2,4,6,36,40,30,1080,1078
1,2,4,6,36,40,30,1080,1040
1,2,4,6,36,40,30,1080,1166400
1,2,4,6,36,144,5184,5148,5040
1,2,4,6,36,144,5184,5040,25401600
1,2,4,6,36,144,42,6048,6006
1,2,4,6,36,30,1080,1078,1042
1,2,4,6,36,30,1080,1078,1076
1,2,4,6,36,30,1080,1078,1044
1,2,4,6,36,30,1080,1076,1040
1,2,4,6,36,30,1080,1076,1166400
1,2,4,6,36,30,1080,1044,1040
1,2,4,6,36,30,1080,1044,1166400
1,2,4,6,36,30,1080,1050,1056
1,2,4,6,36,42,168,6048,6006
1,2,4,6,36,42,1512,6048,6006
1,2,4,6,36,216,210,840,45360
1,2,4,6,36,1296,1260,5040,181440
1,2,4,8,10,100,108,1080,108000
1,2,4,8,10,100,108,10800,108000
1,2,4,8,10,100,108,1000,108000
1,2,4,16,14,196,392,180,572
1,2,4,16,14,196,392,180,70560
1,2,4,16,14,196,392,180,32400

-- Вт апр 23, 2013 15:50:19 --

post713672.html#p713672

Первая попытка вникнуть в алгоритм.

Цитата:

я генерировал базу размером примерно 600 мегабайт

То что этого достаточно верится с трудом. Например mertz перебрал все последовательности длиной 12 операций. Причем контроль уникальности последовательностей у него тоже есть.
post705224.html#p705224
Для этого ему понадобилось просмотреть 18.9T узлов. Затолкнуть такое количество узлов в 600 mB?! Разве такое возможно?!

А ведь вам например для 37!, чтобы найти решение длиной 20 операций, необходимо рассмотреть все последовательности длиной
18 операций для n!=a*c^2
и 16 операций для n!=(x*a)(x*a-a)*y или n!=(x*a)(x*a+a)*y

[Pavlovsky]

Цитата:

генерируем для каждого n две таблицы - одну из двух столбцов, а вторую - из трех. Далее используем технику хеширования.

Зачем нужны эти таблицы вообще не понятно. Не проще ли в каждом узле перебора пробежаться по текущей последовательности, что бы выяснить есть ли в ней числа удовлетворяющие равенствам n!=a*c^2 и n!=(x*a)(x*a-a)*y или n!=(x*a)(x*a+a)*y

-- Вт апр 23, 2013 16:12:31 --

Создается впечатление, что wanderers накачал алгоритм эвристиками, которые дали неожиданный успех для относительно небольших N. Но обсуждать использованные эвристики автор не хочет.

[mertz]

With help provided by Tom Rikicki, my time to find all solutions for 15! is under 1 day now.

I built a database of 10 steps( 11 values ) of all numbers 500 million and less. Only stored sequences that were the optimal length for each number and optimal length+1. The optimal lengths are in the t500m.tab file which I made available. That file has optimal lengths for numbers 5 - 500 million. It was built during a 12 step search and is 73.5% populated.

The database file is 11.7GB. The index into database is 7.4GB. The 11 step ( 12 value ) database would be close to 1TB using sequences for numbers 500 million and less.

[Pavlovsky]

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

Only stored sequences that were the optimal length for each number and optimal length+1

Отличная эвристика! Что же вы о ней когда шел конкурс не говорили.

[wanderers]

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

Цитата:

генерируем для каждого n две таблицы - одну из двух столбцов, а вторую - из трех. Далее используем технику хеширования.

Зачем нужны эти таблицы вообще не понятно. Не проще ли в каждом узле перебора пробежаться по текущей последовательности, что бы выяснить есть ли в ней числа удовлетворяющие равенствам n!=a*c^2 и n!=(x*a)(x*a-a)*y или n!=(x*a)(x*a+a)*y

-- Вт апр 23, 2013 16:12:31 --

Создается впечатление, что wanderers накачал алгоритм эвристиками, которые дали неожиданный успех для относительно небольших N. Но обсуждать использованные эвристики автор не хочет.

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

[Pavlovsky]

wanderers в сообщении #714571 писал(а):

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

Куда уж нам, любителям, до непризнанных гениев.

[wanderers]

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

wanderers в сообщении #714571 писал(а):

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

Куда уж нам, любителям, до непризнанных гениев.

Да, уж дальше некуда: если не тянете, то и признайтесь в этом, а не поливайте грязью то, в чем не бельмеса не понимаете: мой алгоритм будет опубликован в уважаемом издании, к которому таких, как Вы, и на пушечный выстрел не подпускают.

[Pavlovsky]

(Оффтоп)

-- Так вот, -- говорил им на это Король, -- когда появится Цветная
Капуста, вы на эту зеленую даже смотреть не захотите.
-- Господи, -- вздыхали кролики, услышав такое, -- неужели доживем до
этого?
-- Будьте спокойны, -- кивал Король, -- следим за опытами и
способствуем...

(С) Фазиль Искандер.