Factorials

[Pavlovsky]

Это плохое вспомогательное решение. Число 1664100 плохое. оно кратно 43^2. То есть, в вашей терминологии оно пассивное. Нужно только для формирования числа 1662804. Так же плохое 1290, оно кратно 43. Получается в последовательности нет чисел кратных 5,7. А без них 19! не построишь.

[Nataly-Mak]

Да, без чисел, кратных 5,7 туго, но построить решение можно. Ну, не оптимальное, разумеется.
Кстати, мне кажется более удобным это вспомогательное решение:

1,2,4,6,36,1296,1290,1664100,1662804

С числом 4 как-то вроде всегда лучше дело идёт, чем с числом 3 (как заметил dimkadimon).

(Оффтоп)

Pavlovsky
а вы не знаете, что с форумом ПЕН? Он у меня сегодня с утра не открывается.
Может быть, на него подействовал пролетевший сегодня ночью над Землёй астероид?

[Pavlovsky]

(Оффтоп)

Сейчас открывается.

[Nataly-Mak]

Если бы я разрабатывала Правила конкурса, то ввела бы нижнюю границу, разрешённую для ввода решений, например, 3 балла.

Тогда бы турнирная таблица заканчивалась этой строкой:

Цитата:

293 3.00 Andreas Bartsch Nordhausen, Germany 14 Feb 2013 21:33

Сейчас в таблице 375 участников. 82 человека имеют менее 3 баллов, а несколько из них менее 1 балла. Ну что это за участие? Как-то несерьёзно.
Таблицу пролистать и просмотреть трудно стало.

[Nataly-Mak]

Имеем:
6!=3!*5!
10!=6!*7!

Существуют ли ещё подобные соотношения?
[n!=k!*m!]

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

[L-sky]

есть ещё:
24! = 23!*4!

[Nataly-Mak]

Да, верно.
А ещё есть?

[L-sky]

до 40 ничего не наблюдается, а в целом легко отследить учитывая, что факториал в левой части равенства не должен браться от простого числа, иначе правая часть вырождается до умножения на 1, так как необходимо одним из множителей брать факториал от числа не меньшего чем последнее простое число в цепочке умножений факториала слева

[Nataly-Mak]

Спасибо.
Наверное, показалось, что встречалось ещё такое равенство. Вот мучаюсь теперь: было или не было?
Черновиков гора, два раза уже просмотрела, ничего не нашла. Ещё была мысль такая (точно помню): надо записать, потеряется. И всё-таки потерялось.

В задаче-то больше 37! не используется.

А может, это было такое равенство:

n! = (k!)^2*m!

(Оффтоп)

вот старая калоша

[L-sky]

встречал одно такое:
16! = 14!*5!*2 , но с практической стороны толку от него не слишком много, ввиду того, что получить что-либо путное можно только при сравнении со всеми возможными оптимумами обоих чисел, а не одного

-- 17.02.2013, 12:22 --

упс, проморгал один знак, но как таковое внесение квадрата не изменяет общего принципа, так как
$(2n)! = K(n!)^2$ в общем виде рассматривается, как $(cn)! = K(n!)^p$, тогда зафиксировав значение степени равное 2, можно варьировать остальные переменные до получения нужного результата

[Nataly-Mak]

L-sky в сообщении #684922 писал(а):

встречал одно такое:
16! = 14!*5!*2

Интересное равенство, фактически в правой части произведение трёх различных факториалов:

16! = 2!*5!*14!

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

[Pavlovsky]

Есть выражение $\prod_{i=1}^{n}{{x_i}^{k_i}}$

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

Свойства:

1) Если $k_i=1$, тогда как не крути одно умножение необходимо.

2) Выражение ${x_1}^2{x_2}^2$ вычисляется за два умножения $t_1={x_1}{x_2}$, $t_2={t_1}^2$

3) Вычисление $x^k$ эквивалентно построению псоледовательности 1,2,... где разрешено использовать только операцию сложения.

[dimkadimon]

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

3) Вычисление $x^k$ эквивалентно построению псоледовательности 1,2,... где разрешено использовать только операцию сложения.

Эту задачу можно решить, смотрите сюда: http://en.wikipedia.org/wiki/Addition_chain и http://en.wikipedia.org/wiki/Addition-c ... nentiation

Ну наконец я нашёл 13 для 19!. Пришлось почти полностью переписать программу. Зато теперь есть шанс получить новые результаты :)

[Pavlovsky]

dimkadimon Спасибо за ссылки.

Цитата:

Calculating an addition chain of minimal length is not easy; a generalized version of the problem, in which one must find a chain that simultaneously forms each of a sequence of values, is NP-complete.

Вроде задачка выглядит простой. Сразу и не подумаешь, что она NP-полная.

Length of shortest addition chain for n.
http://oeis.org/A003313

[Xaositect]

По аддитивным цепочкам и возведению в степень:
http://wwwhomes.uni-bielefeld.de/achim/ ... chain.html
http://citeseerx.ist.psu.edu/viewdoc/su ... 1.106.5081