Factorials

[Nataly-Mak]

Немножко ещё поломала голову
Получила для 18! 15 шагов. Уже близко к лучшему результату, найденному на конкурсе - 13 шагов (если он остаётся ещё лучшим).

[Pavlovsky]

Xaositect в сообщении #675739 писал(а):

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

Вспомнил из школьного курса математики формулу:

(A+B)*(A-B)=A^2-B^2.

[Herbert Kociemba]

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

(A+B)*(A-B)=A^2-B^2.

I do not beleave, that this approach is helpful. Adding/subtracting large numbers is expensive.
With my approach I need 23 steps for 35!, 36! and 37! . Not really good, but not really bad too. In my approach subtraction and addition occurs only with relatively small numbers. Then these are multiplied. I use 10 multiplications as the last operations for 35!, 36! and 37!.
Maybe I should rewrite my programs. If there are many multiplications in the end, it may be unnecessary to use the GMP library. For the multiplication of large numbers you only need to add prime powers.

[Pavlovsky]

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

Herbert Kociemba в сообщении #678133 писал(а):

If there are many multiplications in the end, it may be unnecessary to use the GMP library. For the multiplication of large numbers you only need to add prime powers.

Слава богу у меня такой проблемы нет. В платформу программирования, которую я использую, встроена арифметика длинных чисел. Так что спокойно работаю с 50-ти значными числами.

-- Чт янв 31, 2013 10:53:55 --

Есть первая единичка! N13L11.

[Nataly-Mak]

Эх, вот так я и знала...уже вчера видела, что Wes Sampson вышел на 11-ое место и рвётся в десятку

Цитата:

10 22.81 Wes Sampson La Jolla, California, United States 31 Jan 2013 04:11
11 22.47 Alex Chernov Penza, Russia 26 Jan 2013 05:41

Ну, ничего, ещё не вечер!

[Pavlovsky]

142 10.22 Valery Pavlovsky Ekaterinburg, Russia 31 Jan 2013 07:45

Я тоже рвусь в десятку. Написал переборный алгоритм, достаточно быстрый. Дошел до N=21, везде результаты больше 0,9. То есть когда дойду до N=37 будет больше 22,5.

[svb]

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

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

По поводу порога. У меня случилась парадоксальная ситуация. После введения порога я относительно быстро (час? сейчас не помню) нашел N15L12 и N17L12, но вот решение N16L12 и через сутки так и не появилось. И только после увеличения порога удалось получить N16L12.

Цитата:

Слава богу у меня такой проблемы нет. В платформу программирования, которую я использую, встроена арифметика длинных чисел. Так что спокойно работаю с 50-ти значными числами.

Запрограммировать умножение столбиком не сложно, да и полезно вспомнить первый алгоритм, который нам давали в начальной школе

[Pavlovsky]

svb в сообщении #678242 писал(а):

Запрограммировать умножение столбиком не сложно

Читал описание алгоритмов в конкурсе Orchard Planting. Никто из лидеров не стал связываться с арифметикой длинных чисел. То есть добровольно ограничили в своих решених величину координат.

[svb]

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

[Pavlovsky]

А что делать с операциями сложения, вычитания, сравнения?!

[Nataly-Mak]

Herbert Kociemba в сообщении #678133 писал(а):

If there are many multiplications in the end, it may be unnecessary to use the GMP library. For the multiplication of large numbers you only need to add prime powers.

Кстати, переведите кто-нибудь, пожалуйста, последнюю фразу в сообщении Herbert Kociemba. Гугл переводит её невразумительно.

Как я поняла из сообщения Herbert Kociemba, если ограничить числа, для которых использовать сложение/вычитание, то последние операции уже будут только операцией умножения, что даст возможность не использовать библиотеку GMP (то есть арифметику длинных чисел).

Ну, а в представлении последовательности на конкурс, думаю, разрешается писать члены последовательности в виде произведения чисел, а не как конечный результат произведения - огромное число. Я это не знаю, так как сама последовательности на конкурс не ввожу.

[svb]

Pavlovsky

Цитата:

А что делать с операциями сложения, вычитания, сравнения?!

Сложение и вычитание приходится ограничивать , об этом вы уже писали. Сравнение и умножение при представлении чисел в виде наборов степеней 12 простых чисел проблем не вызывает. Получается вариант "задачи о рюкзаке", но количество вариантов на входе в эту задачу ужасает.

Конечно, ограничение рассматриваемых чисел только специальными выглядит странным, но просмотр имеющихся решений до 12! подтверждает разумность подобного ограничения.

Nataly-Mak
Мой вольный перевод: для умножения больших чисел потребуется только сложение степеней простых чисел.

[Nataly-Mak]

svb
спасибо за перевод. Вроде понятно стало.

[svb]

SLP последовательность:
$1,x_1 ,x_2 ,...,x_k $, $x_i = op_i \left( {x_m ,x_n } \right)$, $m \le i,n \le i$, $op_i = \left( { + , - , \times } \right)$
Для шага $x_i = op_i \left( {x_m ,x_n } \right)$ без ограничения общности можно считать $x_n \le x_m $, для этого при вычитании достаточно рассматривать абсолютную величину результата. Положим: $f\left( i \right) = m$ и $l(i) = n$.

Теорема. Для любой SLP последовательности $1,x_1 ,x_2 ,...,x_k $ существует эквивалентная ей последовательность $1,y_1 ,y_2 ,...,y_k $ , состоящая из тех же чисел, что $f\left( i \right) = i - 1 $, либо $f\left( i \right) = f\left( {i - 1} \right)$.

Если убрать случай $f\left( i \right) = f\left( {i - 1} \right)$, то резко сокращается пространство перебора.

Приведенную теорему необходимо проверить, т.к. я мог совершить ошибку. Первоначально мне показалось, что при переборе можно убрать вариант $f\left( i \right) = f\left( {i - 1} \right)$, но для конкретной последовательности это невозможно в том варианте, как указано в теореме. При переборе же ситуация сложнее и, возможно, этот случай можно исключить. По крайней мере, конкретные решения мне удалось получить без использования последнего варианта.

Дополнительно полезно рассмотреть функцию $l(i)$.

[Nakilon]

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

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

Обрезка сложения – это то, что на второй день контеста дало мне 20-е место. Но не смотря на свою тривиальность, считаю это коллективным решением вслух...

P.S.: вот уже больше недели не решаю. Вынашиваю планы о полуавтоматическом решении.
А с N=13 конкурс начинается не просто так, а потому, что оно как раз превышает int32.