Factorials

[Nataly-Mak]

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

Имеется в виду перебирать все алгоритмы для числа 30, причем, к сожалению, не только оптимальные.

Мой вопрос был: как применить алгоритмы вычисления числа 30 к вычислению 6! по заданному полиному?

Для N=13 тоже нашла полином по известному решению и тоже по основанию 16.

[Pavlovsky]

В борьбу вступил еще один россиянин!

253 8.83 Nikolay Medvedev Moscow, Russia 13 Mar 2013 09:43

Теперь нас 19 (если не учитывать агентов, работающих под прикрытием).

[Nataly-Mak]

Хотела показать полином для N=13, очень оригинальное решение.
Но... Вольфрам для этого полинома даёт хорошую упаковку, сразу составляется по ней оптимальное решение.
Не буду показывать

[Nataly-Mak]

Вот полином для N=27:

$x^{18}+2x^{17}+3x^{16}-93x^{15}-294x^{14}-510x^{13}-547x^{12}-239x^{11}+68x^{10}+116x^9+24x^8+11x^7-12x^6$
$x=36$

Ничего лучше такой тривиальной упаковки Вольфрам не предлагает:
$x^6(x(x(x(x(x(x(x(x(x(x(x(x+2)[phone])+68)+116)+24)+11)-12)$

В чём же секрет "хорошего" полинома
Хорошего --- в том смысле, что полином хорошо упаковывается.
Можно ли хоть как-то упаковать приведённый полином другим способом, отличным от предложенного Вольфрамом?

[dimkadimon]

Конец!

2    25.00    Hermann Jurksch    Recklinghausen, Germany    14 Mar 2013 23:03

[Nataly-Mak]

К тройке россиян подтягивается Vovka17.

Цитата:

44 22.48 Vadim Trofimov Saint Petersburg, Russia 4 Mar 2013 05:49
45 22.42 Dmitry Ezhov Sterlitamak, Russia 13 Mar 2013 19:34
46 22.36 Viktor Polesov Moskow, Russia 12 Mar 2013 03:56
. . . . . . . . . . . .
53 21.69 Vladimir Chirkov Bobruisk, Russia 13 Mar 2013 12:10

Что-то никто не посоветовал, как упаковать приведённый мной полином
Может быть, попробовать сделать замену
$x=6t$

Для N=27 имею решение в 18 шагов, что плохо (на 2 шага больше оптимального). Хотела что-нибудь получить с помощью полиномизации, но увы...
Получила несколько полиномов и ни один из них не могу упаковать. Вольфрам тоже не может

[Pavlovsky]

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

Конец!

Первые два места заняты?! Без вариантов?!
Ведь есть и такое мнение:

Цитата:

It seems to me that most problems above 30
haven't reached the best solutions.

[Nataly-Mak]

Учимся искусству упаковывать полиномы
http://e-science.ru/forum/index.php?showtopic=41268

[dimkadimon]

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

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

Конец!

Первые два места заняты?! Без вариантов?!
Ведь есть и такое мнение:

Цитата:

It seems to me that most problems above 30
haven't reached the best solutions.

Я начинаю сомневаться что осталось много рекордов, может один-два не больше. Мне кажется что самый вероятный рекорд это 37! в 19 шагов.

[Pavlovsky]

Полиномы, как и целые числа можно делить друг на друга с остатком.
$x^6 (x^{12}+2 x^{11}+3 x^{10}-93 x^9-294 x^8-510 x^7-547 x^6-239 x^5+68 x^4+116 x^3+24 x^2+11 x-12)= x^6(x^6(x^6+P(x))-(119P(x)+ (-410 x^4+10951 x^3+34962 x^2+60679 x+65105)))$
где
$P(x)= 2 x^5+3 x^4-93 x^3-294 x^2-510 x-547$

-- Пт мар 15, 2013 11:24:54 --

И еще замечание. Когда мы основание, относительно которого разложили факториал, заменили на X. Мы сделали это формально. Ну чтобы удобнее было приименять формальные алгебраические преобразования. Поэтому мы всегда можем приментить следующее формальное преобразование:
$x^k=Ax^{k-1}$, где A основание по которому был разложен факториал.

-- Пт мар 15, 2013 11:54:04 --

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

Я начинаю сомневаться что осталось много рекордов

Третье место пока еще свободно. Если честно, меня третье место вполне устроит.

-- Пт мар 15, 2013 11:56:42 --

70 20.62 Angelika Rindler Klagenfurt, Austria 15 Mar 2013 00:54

[Nataly-Mak]

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

Полиномы, как и целые числа можно делить друг на друга с остатком.

Ага, и умножать тоже можно
что я и сделала для 27! (см. полиномы, представленные на ПЕН).

Цитата:

И еще замечание. Когда мы основание, относительно которого разложили факториал, заменили на X. Мы сделали это формально. Ну чтобы удобнее было приименять формальные алгебраические преобразования. Поэтому мы всегда можем приментить следующее формальное преобразование:
$x^k=Ax^{k-1}$, где A основание по которому был разложен факториал.

Можно использовать это преобразование для уменьшения коэффициентов полинома, если они очень большие.

Цитата:

Третье место пока еще свободно. Если честно, меня третье место вполне устроит.

Поторопитесь Кандидатов на третье место много (выше вас в турнирной таблице).

[Pavlovsky]

1   25.00   Tomas Rokicki   Palo Alto, California, United States 22 Feb 2013 03:36
2   25.00   Hermann Jurksch   Recklinghausen, Germany 14 Mar 2013 23:03
3   24.89   Gil Dogon   Jerusalem, Israel 12 Mar 2013 17:55
4   24.89   Martin Piotte   Montreal, Quebec, Canada 11 Mar 2013 10:46
5   24.79   Lars Nagel   Mainz, Germany 28 Feb 2013 13:33
6   24.74   John Morris   Simi Valley, California, United States 5 Mar 2013 14:14
7   24.67   Hanhong Xue   Fuzhou, China 12 Mar 2013 03:31
8   24.47   Dmitry Kamenetsky   Adelaide, Australia 14 Mar 2013 22:17
9   24.41   Lucien Pech   Zürich, Switzerland 10 Mar 2013 09:03
10   24.41   Albert Graells Rovira   Zürich, Switzerland 14 Mar 2013 22:35
11   24.37   Andy Sloane   Sunnyvale, California, United States 8 Feb 2013 21:39
12   24.23   Siva Dirisala   Foster City, California, United States 14 Mar 2013 05:56
13   24.22   Valentin Dobrota   Constanta, Romania 7 Feb 2013 11:05
14   24.19   Herbert Kociemba   Darmstadt, Germany 10 Mar 2013 10:09
15   24.13   Walter Trump   Nuremberg, Germany 15 Mar 2013 10:13
16   23.95   Valery Pavlovsky   Ekaterinburg, Russia 15 Mar 2013 10:25

Ага как же их обгонишь. Walter Trump обошел меня как стоячего. Я шаг, он три. Мало того что обошел меня с членством в клубе 24+, так еще создал задел, чтоб у него 15-е место не отняли. Активность лидеров потрясает. В топ-15 только 4 человека не вводили новые решения в марте. Еще видна четкая граница между 7-м и 8-м местами. Разница в 0,2 балла в верху рейтинга это очень много. Это надо улучшить на единицу 4 решения. В ситуации, когда почти все решения являются повтором рекорда.

[Nataly-Mak]

Вот-вот, о чём я и говорила
Сейчас вы опять первый кандидат на вход в клуб 24+
Но не факт, что первым в него войдёте.
Хотя осталось всего чуть-чуть, 0.06 балла достаточно.

[Vovka17]

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

Конец!

Глядя на "хвост" рекордов

...17, 18, 18, 18, 17, 19?, 18, 20?

не покидает ощущение, что не всё возможное ещё "выжато". Думаю, что один-два рекорда (например, для n=35, 37) вполне реальны. То, что никто этого ещё не находил - не показатель. В прошлом конкурсе тоже долго держались рекорды и многие (я в том числе) думали, что улучшить их уже невозможно...
Впрочем, при нынешней конкуренции (уже 405 участников), прорваться бы в десятку сильнейших - предел желаний для меня.
Сегодня запустил на работе свою переборную программу (надеюсь, наконец, что исправил многочисленные мелко-фатальные баги и всё отработает как запланированно). По плану, к понедельнику, будут чувствительные улучшения текущего положения.

[Pavlovsky]

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

Сейчас вы опять первый кандидат на вход в клуб 24+

Уже нет.

16 24.00 Valery Pavlovsky Ekaterinburg, Russia 15 Mar 2013 15:32