Factorials

[Pavlovsky]

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

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

Фольфрам упаковал полином не оптимально. Но главное он сделал, выделил часто повторяющиеся конструкции.
Это уже почти готовое решение (dimkadimon):

1,2,4(3),6,36,38,76(72),2736

Любой переборный алгоритм легко его достроит до нужного решения.

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

[Nataly-Mak]

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

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

Здесь $x=2$.
Есть ли полиномы других видов для N=6?

-- Пн мар 11, 2013 08:57:38 --

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

Это уже почти готовое решение (dimkadimon):

1,2,4(3),6,36,38,76(72),2736

А почему "почти готовое"?
Это совсем готовое решение в 18 шагов (по варианту упаковки, приведённому dmd).

Кстати, второй из приведённых выше полиномов легко превращается в полином для $x=4$:

$x^4+5x^3+8x^2+4x$

И далее, для $x=16$:

$x^2+28x+16$

или так:

$x^2+29x$

Полином для $x=4$ Вольфрам упаковывает так:

$x(x+1)(x+2)^2$

Нельзя сказать, что полная ерунда, нормальная упаковка; однако решение получается только в 7 шагов:

1,2,4,5,6,36,180,720

[Nataly-Mak]

Этот полином для $x=2$ сама нашла (для N=6); забавляюсь
Все коэффициенты равны единице.

$x^9+x^7+x^6+x^4$

Упаковка этого полинома:

$(x^2(x+1))^2(x^2+1)$

и решение опять-таки в 7 шагов:

1,2,3,4,5,12,144,720

[Pavlovsky]

Увлекательное занятие.
$x^{10}-x^8-x^6+x^4$
Упаковка от вольфрама:
$(x-1)^2 x^4 (x+1)^2 (x^2+1)$
Полсе преборазований:
$(x^4-x^2)^2 (x^2+1)$
Решение:
1,2,4,5,16,12,144,720

[Nataly-Mak]

Немного преобразовала полином Pavlovsky для 26! (при x=36).
Забавную упаковку предложил Вольфрам:

$x^5(8 + x (50 + x (-10 + x (-363 + x (12 + x (834 + x (2103 + x (2235 + x (1325 + x (510 + x (117 + x (11 + x))))))))))))$

Похоже, я ошиблась в преобразованиях. Значение этого полинома при $x=36$ не равно 26!
Сейчас проверю.

Нашла ошибку. Вот правильный полином:

$x^5 (8 + x (50 + x (-17 + x (-360 + x (-351 + x (834 + x (2155 + x (2227 + x (1325 + x (510 + x (117 + x (11 + x))))))))))))$

[dimkadimon]

Может кому пригодится:

$ n! = (n-1)((n-1)!+(n-2)!) = n(2(n-1)!-(n-1)(n-2)!) $

[Nataly-Mak]

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

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

За какое минимальное количество операций можно вычислить это выражение?
$32 x^{16}+544 x^{15}+4088 x^{14}+17648 x^{13}+47428 x^{12}+79616 x^{11}+76890 x^{10}+28956 x^9-13095 x^8-12022 x^7+640 x^6+800 x^5$

После упрощения

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

оно же

$x^2 x (2 + x) (x + 2 x (2 + x))^2 (1 + 2 x (2 + x)) (-4 + (x + (2 + x) 2 x (2 + x)))^2$

итого 15, но не факт что минимально

Удалось вычислить этот полином за 13 операций.
Ещё одну операцию никак не получается сэкономить

[dmd]

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

[Nataly-Mak]

То есть даже для решения в 15 шагов годится?

Я стремилась получить решение в 16 шагов, как сообщил Pavlovsky. Пока получила только в 17 шагов. Значит, надо где-то сокращать ещё 2 операции.

[dimkadimon]

$f(x) := 9x^3-23x^2+43x-45$
$f(3) = 120$
$f(5) = 720$
$f(9) = 5040$

[dimkadimon]

Пока я пытался обогнать Andy Sloane и перейти на 4ое место, меня обогнали и опустили до 10ого места :) Борьба наколяется!

[Pavlovsky]

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

My base 8 count is 5963543.

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

2 2
3 8
4 59
5 663
6 10609
7 225219

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

2 2
3 8
4 59
5 663
6 10609
7 225219
8 6057298

-- Вт мар 12, 2013 08:41:24 --

Активность в верхней части рейтинга огромная. Еще вчера китаец был в шаге от меня. А теперь:

7 24.67 Hanhong Xue Fuzhou, China 12 Mar 2013 03:31

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

[Nataly-Mak]

Pavlovsky
Кандидат-то вы первый, но это ещё не значит, что вы первый вступите в этот клуб

Да, китаец жжёт

Вот этой троице пожелаем удачи!

Цитата:

43 22.48 Vadim Trofimov Saint Petersburg, Russia 4 Mar 2013 05:49
44 22.37 Dmitry Ezhov Sterlitamak, Russia 11 Mar 2013 08:21
45 22.36 Viktor Polesov Moskow, Russia 12 Mar 2013 03:56

-- Вт мар 12, 2013 08:17:39 --

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

$f(x) := 9x^3-23x^2+43x-45$
$f(3) = 120$
$f(5) = 720$
$f(9) = 5040$

Очень красиво! Мастер-класс

[dimkadimon]

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

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

А я первый кандидат на выход из 10-ки :(

[Pavlovsky]

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

Кандидат-то вы первый, но это ещё не значит, что вы первый вступите в этот клуб

Если у кого то есть алгоритмы, способные выдавать результаты эекстра класса, то уже настало время их запустить в работу. Мой основной рабочий алгоритм обсичтывает один факториал, где то за двое суток. Работают три копии программы. Сейчас обсчитывают N=29,30,31. По моим оценкам, когда будут обсчитаны все N, это принесет мне дополнительно 0,3-0,5 балла. Попутно будет создана огромная база близких к рекордным решений.

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

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

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

Не отказался я и от механизма формирования гипотез. Работаю над ним по-тихоньку.