Factorials

[Nataly-Mak]

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

Очевидно в последовательности должны быть числа $(2 + x)$ и $2 x (2 + x)$
То есть возможны два варианта начала последовательности.

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

Ну да, так у меня решение и начинается:

1,2,4,6,36,38,72,2736,2772,...,403291461126605635584000000

[Pavlovsky]

Упаковка предложенная вольфрамом.
$2 (x^2+2) (2 (x^2+2) x^2+x^2)^2 ((x^2+2) (2 (x^2+2) x^2+1)-x)^2 x^{10}+4 (x^2+2) (2 (x^2+2) x^2+x^2)^2 ((x^2+2) (2 (x^2+2) x^2+1)-x)^2 x^8+(2 (x^2+2) x^2+x^2)^2 ((x^2+2) (2 (x^2+2) x^2+1)-x)^2 x^8+2 (2 (x^2+2) x^2+x^2)^2 ((x^2+2) (2 (x^2+2) x^2+1)-x)^2 x^6$
Забавно, вольфрам предлагает делать последней операцией сложение.

[Nataly-Mak]

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

Тот же полином, но x=6.

Выкладываете готовое решение --- второе уже.
Gerbicz нет, к счастью

[Pavlovsky]

Аккуратно заполнил упаковку, предложенную вольфрамом. Чуток подправил. Получил решение 16 операций. Тема интересная, но надо сделать паузу.

[Pavlovsky]

Получается так. Раскладываем N! на простые сомножители. Каждое простое число раскладываем на сумму (разность) степеней двойки. Так как разрешена операция вычитания, то простое число можно разложить различными способами. Например 3=2+1, 3=4-1. Далее оптимизируем полученное выражение. Например (4-1)*(4+1)=(16-1).
Получилась фигня.

[dimkadimon]

Ребята осторожно. Тут почти целые решения...

[Pavlovsky]

3=2+1
5=4+1
7=2*4-1
11=16-4-1
13=16-2-1
17=16+1
19=16+2+1
23=16+2*4-1
29=2*16-2-1
31=2*16-1
37=2*16+4+1

-- Вс мар 10, 2013 16:27:59 --

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

Ребята осторожно. Тут почти целые решения...

Извини, так получилось. Честное слово не хотел.

[dimkadimon]

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

3=2+1
5=4+1
7=2*4-1
11=16-4-1
13=16-2-1
17=16+1
19=16+2+1
23=16+2*4-1
29=2*16-2-1
31=2*16-1
37=2*16+4+1

И что дальше? Можно 11=2*4+2+1. A лучше использовать другие простые числа. Например 11=2*5+1.

[L-sky]

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

И что дальше? Можно 11=2*4+2+1. A лучше использовать другие простые числа. Например 11=2*5+1.

Не лучше хотя бы в том плане, что любое число из последовательности можно представить в некое малое количество действий с цифрой 2, $1 = 2^0$, а так как получение промежуточных значений 2 невыгодно, допустим даже $2^8$,то весь фокус сводится к тому чтобы подобрать некоторое наиболее часто используемое выражение через операции с 2, которое при использовании других простых чисел становятся не очевидным, насколько это слово вообще применимо, а в ряде случаев и невозможным

[Xaositect]

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

[Pavlovsky]

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

[dmd]

Тот полином было легко упаковать (хоть и не оптимально) потому что он исходно был развёрнут из конкретного решения, т.е. коэффициенты были соответствующие. Поэтому Вольфраматика так удачно его и свернула, что его можно было хоть как-то но достаточно легко вручную доупаковать. Там кстати не 15, а 16 шагов, ошибся, т.е. всего 16+4=20.
А вот как упаковать такой стартовый полином, полученный переводом числа 26! в 36-ричную систему счисления?:

$8 x^5 + 14 x^6 + 20 x^7 + 35 x^8 + 34 x^9 + 31 x^{10} + 17 x^{11} + 19 x^{12} + 20 x^{13} + 8 x^{14} +24 x^{15} + 14 x^{16} + x^{17}$

Поскольку знаем (или уверенно предполагаем), что числа 38 и 2736 также будут активно участвовать в последовательности, то быть может стоит в одном полиноме сделать интерсекшин двух систем счисления 38- и 2736-ричных? Действительно ходим по кругу, с этого места безуспешно начинал конкурс. Но обсуждение как минимум даст хотя бы отрицательный результат.

[dimkadimon]

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

Теперь понял, спасибо. Только как вы это получили в Вольфраме?

[Pavlovsky]

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

А вот как упаковать такой стартовый полином, полученный переводом числа 26! в 36-ричную систему счисления?:

При переводе числа в Х-ричную систему исчисления, предполагается что коэффициенты при степенях основания не отрицательны и меньше основания. В нашем случае такого ограничения нет. Коэффициенты могут быть больше основания и даже отрицательными.
Пока получается так. Надо перебрать все представления числа N! по выбранному основанию. Для каждого полученного полинома найти оптимальное решение. Из полученных решений выбрать лучшее.

-- Пн мар 11, 2013 08:34:06 --

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

Только как вы это получили в Вольфраме?

Вольфрам выдал полную ерунду. Тогда решил преобразовать исходное выражение руками. Но меньше чем 7 операций у меня не получилось. Тогда взял решение за 6 операций и подогнал преборазования под выбранный ответ.
Даже для 6! оптимально упаковать полином трудная задача!

[Nataly-Mak]

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

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

У меня тоже сначала получилось 16 шагов. Потом сделала в 14 (тот же самый ваш вариант).
Всё решение содержит в этом случае 18 шагов.

-- Пн мар 11, 2013 07:53:11 --

(Оффтоп)

Вообще-то уже сообщала об этом:

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

Удалось вычислить "упакованный" полином, приведённый dmd, за 14 операций
(зри в теорему Оливоса )
Всё решение содержит 18 шагов.
Но опять же не 16, как у Pavlovsky.
Следовательно, "упаковка" dmd не оптимальная, есть лучше. Надо сэкономить ещё 2 операции, чтобы получить решение в 16 шагов.