Factorials

[Nataly-Mak]

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

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

Он гарантированно упакуется в 11 ходов, т.е. это именно рекордный полином.

Если это правда. Значит теория упаковки полиномов работает!

Это правда
Да, оптимальная упаковка полинома решает всё.
Ваша идея с полиномами, как всегда, супер

[Pavlovsky]

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

Ваша идея с полиномами, как всегда, супер

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

[Nataly-Mak]

Зверюшка действительно очень забавная.
Я вчера с этой зверюшкой целый день забавлялась

[Vovka17]

Добрый день всем!

Pavlovsky
Ну вы даёте . Специально не вчитывался в ваши полиномы, чтобы не нарушить свои мысли. Хотя что-то похожее у меня (да и наверное не только у меня) проскакивало. Но было отброшено из-за скудных математических способностей...

(Оффтоп)

Может вы, например, и в шашках так сможете. Есть расположение всех шашек на доске, сделать формулу выдающую наилучший ход!

А у меня вот всё не клеится что-то. Всё программирование свелось к банальному перебору с обрезаниями (хотя я и долго упирался от такого пути). Плюс последние две недели расчеты обрывались где-то на середине из-за фатальных багов в программе. Плюс вчера по ошибке грохнули мои полурасчеты за последнюю неделю ...

Правда, есть ещё парочку сильных улучшений, которые никак не доберусь запрограммить.

И, кстати, n=19! в 13 шагов я нашел относительно легко. Странно, что все говорят, о сложности этого решения. Наверное у меня всё-таки не такой банальный путь, как я думаю . В моих расчетах все сложности начинаются от n=25!. А выше N=30!, вообще, ещё нет ничего...

[Pavlovsky]

Vovka17 в сообщении #694402 писал(а):

Может вы, например, и в шашках так сможете. Есть расположение всех шашек на доске, сделать формулу выдающую наилучший ход!

Шашки (8х8) теоретически решенная проблема! Существуют программы способные сформировать оптимальное полное дерево перебора.

[Vovka17]

(Оффтоп)

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

Шашки (8х8) теоретически решенная проблема! Существуют программы способные сформировать оптимальное полное дерево перебора.

Английский чекерс да, но это далеко не русские шашки, плюс программа Chinook даёт не всегда самые сильные ходы (ведущие к более вероятному выигрышу). Просто она не проигрывает (то есть все непроигрышные ходы для нее более-менее равнозначны).
А про русские шашки не знаком с такими алгоритмами и программами.

[dimkadimon]

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

Теорию вокруг задачи можно так выстроить.

Есть число $n!$. Будут две подзадачи. Первая - сопоставить числу лучший подходящий полином, возможно больше чем от одной переменной. Вторая - максимально "упаковать" полином. Для второй наверняка есть готовые алгоритмы, не может быть чтоб эта задача раньше никогда не возникала.

Я стал думать над второй подзадачей. Мне кажется что максимальная упаковка полинома имеет такую же сложность как наша оригинальная задача для N!. Чтобы упаковать полином f(x) надо найти программу от x до f(x) используя операции -, + и *. Например упакуем f(x)=x^3+3x^2+2x. Получим (x+1)((x+1)^2-1). Это можно представить как программу x, x+1, (x+1)^2, (x+1)^2-1, f(x). Заметьте что можно добавлять числа, как мы превратили x в x+1.

-- 12.03.2013, 18:35 --

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

А можно ли для N! составить такой полином, чтобы он содержал все решения задачи?!

Думаю можно, но он не будет давать хороших решений. Выше я написал полином который дает 120, 720 и 5040. Мы знаем что для n точек существует полином с максимальной степенью (n-1) который проходит через все эти точки. Коеффиценты этого полинома будут рациональными. Осталось только найти такой полином чтобы его решения х для всех N! были целыми числами.

[Nataly-Mak]

А вот этого страшного зверя кто-нибудь может упаковать?

$32 x^{15}+864 x^{14}+12728 x^{13}+144928 x^{12}+1496708 x^{11}[phone] x^{10}[phone] x^9+1505467456 x^8+15054661465 x^7+150546602628x^6+ 1505466026920 x^5+15054660270000 x^4+150546602700000 x^3+ 1505466027000000 x^2+15054660270000000 x+208449142200000000$

В таком виде полином в Вольфрам не вмещается в поле для ввода.
Надо уменьшать коэффициенты.

[Nataly-Mak]

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

Вот зверь менее страшный:

$262144x^{13}+65536x^{12}-5238784x^{11}[phone]x^{10}-28211968x^9+28763648x^8-19942912x^7+9746432x^6-3341056x^5+764416x^4-103424x^3+6144x^2$

Упаковки, предложенные Вольфрамом:
$256 (1-4 x)^2 (x-1)^4 x^2 (x+6) (x (8 x-7)+2) (x (8 x-3)+2)$
$256 (-1 + x)^2 x^2 (6 + x) (1 - 5 x + 4 x^2)^2 (2 - 7 x + 8 x^2) (2 - 3 x + 8 x^2)$

Точнее, это предложили Вольфрам и Математика. Что-то эти упаковки мне не очень нравятся.

Да, искусство оптимально упаковать полином весьма сложное

[Nataly-Mak]

Попутно нашла для 10! красивый полином:

$4x^5+11x^4+10x^3+3x^2$
он же упакованный:
$(x(x+1))^2(4x+3)$
$x=15$

Полином даёт оптимальное решение:

1,2,4,16,15,64,63,240,57600,3628800

Уф, наигралась с полиномами по самое "не хочу"

p.s.
лучше по основанию 16, да?

$4x^5-9x^4+6x^3-x^2$
$(x(x-1))^2(4x-1)$

[Nataly-Mak]

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

Тривиальное замечание по поводу полиномов: Можно подставить в полином единицу и искать алгоритмы вычисления нужного полинома среди алгоритмов вычисления получившегося числа $f(1)$. Может быть полезно, если $f(1)$ невелико.

Извините за непонятливость.
Ну, допустим, нашли мы алгоритм вычисления $f(1)$.
Дальше что?

Пример:
$f(x)=x^2+29x$

Полином даёт значение 720 при $x=16$.

$f(1)=30$

Число 30 составляется легко:

1,2,4,16,32,30

Как это применить к вычислению 6! по приведённому полиному?

[Nataly-Mak]

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

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

И что дальше?

6!=2^4*3^2*5=2^4*(2+1)^2*(2^2+1)=(2^2* (2^2+2))*(2^2*(2^2+2)+(2^2+2))
1,2,4,6,24,30,720

Первый очень красивый полином для 6! Красота его в том, что он даёт оптимальное решение.
$x^8+5x^6+8x^4+4x^2$
$x=2$

Сделаем замену $t=x^2$. Полином превратится в такой:

$t^4+5t^3+8t^2+4t$
$t=4$
Соответствующая упаковка:
$(t(t+2))(t(t+2)+(t+2))$

Кстати, Вольфрам не справляется с оптимальной упаковкой этого полинома; я, по крайней мере, не добилась от него такой упаковки.

Интересно, на мой взгляд, найти для каждого N! свой полином, дающий оптимальное решение.
Такая полиномизация факториалов
Для N=10 я такой полином нашла (показан чуть выше).
Ну, наверное, задача решается просто, если идти от известных готовых решений для каждого N!.
Для 10! у меня было не так; я искала полином для другого N, попутно получила полином для 10!.

-- Ср мар 13, 2013 10:28:49 --

Кстати, такой полином, как у Pavlovsky, я тоже получила в Вольфраме. Однако оптимально упаковать его не смогла.

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

Забавно:
вводила в Вольфрам различные упакованные варианты для N=6.
Вольфрам выдал полиномы двух видов:

$x^8+2x^7+2x^6+2x^5+x^4$
$x^8+5x^6+8x^4+4x^2$

Здесь $x=2$.

Для N=26 Pavlovsky тоже нам представил полином, дающий оптимальное решение в 15 шагов (это пока рекорд, найденный на конкурсе).

N=7
$20x^2-5x$
$x=16$
упаковку лучше всего (нагляднее для составления решения) записать так:
$(4x-1)(4x+x)$

Решение:

1,2,4,16,64,63,80,5040

[Nataly-Mak]

N=8

$8x^3+28x^2+24x$
$x=16$
упаковка:
$2x(2x+3)(2x+4)$
или так для большей наглядности:
$2x(2x+4)(2x+4-1)$

Решение:

1,2,4,16,32,36,35,1120,40320

N=9

$4x^4+22x^3+40x^2+24x$
$x=16$
Упаковка:
$(4(x+2))^2(4(x+2)-2)$

Решение:

1,2,4,16,18,72,70,5184,362880

Эквивалентные варианты:
$5x^4+8x^3+9x^2+8x$
$64x^3+352x^2+640x+384$
$x=16$

Для N=10 полином представлен выше.

N=11

$x^6+15x^5+92x^4+300x^3+560x^2+576x+256$
$x=16$
Упаковка:
$(x(x+4)+4)(x+4)((x(x+4)+4)(x+4)-(x(x+4)))$

Решение:

1,2,4,16,20,320,324,6480,6160,39916800

[Nataly-Mak]

Последний полином для N=12.

$x^7+10x^6+37x^5+59x^4+32x^3-4x^2$
$x=16$
Упаковка:
$x(x+2)^2((x(x+2)+x)^2-x)$

Решение:

1,2,4,16,18,288,304,5184,92416,92400,479001600

Интересный факт: почти все факториалы (кроме 6!) представлены по основанию 16.

[Xaositect]

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

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

Тривиальное замечание по поводу полиномов: Можно подставить в полином единицу и искать алгоритмы вычисления нужного полинома среди алгоритмов вычисления получившегося числа $f(1)$. Может быть полезно, если $f(1)$ невелико.

Извините за непонятливость.
Ну, допустим, нашли мы алгоритм вычисления $f(1)$.
Дальше что?

Пример:
$f(x)=x^2+29x$

Полином даёт значение 720 при $x=16$.

$f(1)=30$

Число 30 составляется легко:

1,2,4,16,32,30

Как это применить к вычислению 6! по приведённому полиному?

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