Factorials

[Nataly-Mak]

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

16 23.80 Valery Pavlovsky Ekaterinburg, Russia 9 Mar 2013 10:27
17 23.77 Alex Chernov Penza, Russia 27 Feb 2013 10:40

Pavlovsky
первое место по России и СНГ
третье место по Азии
восьмое - по Европе
16-ое - по миру

Совсем не плохо

Надеюсь, что Алексей и Глеб ещё не сказали последнее слово в этом конкурсе.

Уже 13 конкурсантов в зоне 24+
А вот 25 баллов пока имеет только один лидер.
Hermann Jurksch очень близко; думаю, что он это получит в скором времени; кажется, ему не хватает всего одного рекорда.

-- Вс мар 10, 2013 06:59:28 --

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

Перебор начинаю с начальных последовательностей длины 8 (они у меня все есть около 7 миллионов).
7. Еще использую эвристику. Фиксация начала последовательности. Например 1,2,4,16 или 1,2,4,16,256.

Начинать можно с любой начальной последовательности.

Когда я нашла вручную решение для 19! в 15 шагов, попросила mertz выполнить эксперимент: найти решения в 15 шагов от некоторой начальной последовательности, взятой из моего решения. Моя последовательность была не нормализованная.
mertz выбрал такую нормализованную начальную последовательность (9 операций) из моего решения:

1,2,4,16,18,72,70,52,936,938

Его программа нашла 15 решений (в 15 шагов) на базе этой начальной последовательности.
Это своего рода полный перебор окончаний (такой алгоритм я использовала в задаче по игре тетрис).
Понятно, что чем длиннее будет начальная последовательность, тем быстрее выполнится полный перебор окончаний, но!.. тем меньше шансов найти решения за приличное число шагов.

mertz
есть два вопроса:
1. как долго работала ваша программа в этом эксперименте?
2. решений в 14 шагов от данной начальной последовательности не существует?

[Pavlovsky]

За какое минимальное количество операций можно вычислить это выражение?
$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$

[dimkadimon]

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

6! = 720 = [6] 1,2,3,9,27,729,720
6! = 720 = [6] 1,2,3,9,81,729,720
7! = 5040 = [7] 1,2,3,9,81,72,70,5040
7! = 5040 = [7] 1,2,4,16,20,256,252,5040
7! = 5040 = [7] 1,2,4,6,36,1296,1260,5040
7! = 5040 = [7] 1,2,4,6,36,144,5184,5040
8! = 40320 = [8] 1,2,3,6,36,34,1156,1120,40320
8! = 40320 = [8] 1,2,4,8,10,64,4096,4032,40320
10! = 3628800 = [9] 1,2,4,8,64,60,240,57600,3686400,3628800

Big thanks! Whenever you use a non-factor you need to go down in the sequence (and use subtraction). Perhaps you can use this fact to speed up your search.

-- 10.03.2013, 14:18 --

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$

Чуствую что тут кроется что то важное... может эта формула дает все решения? Надо узнать какой из коеффицентов сложнее найти.

[dmd]

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, но не факт что минимально

[Pavlovsky]

dmd
Классная работа! Не думал, что все будет так просто. Может поделишься как делал преобразования?
Задача появилась так. Если в выражение подставить x=36, то получим 26! Само выражение получилось из решения длиной 16 операций. Сравниваю ваше решение со своим, отличия конечно есть, но есть и много совпадений.

-- Вс мар 10, 2013 11:58:48 --

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

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

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

Понял ваш метод! Это выражение вы получили Вольфрамом!

-- Вс мар 10, 2013 12:19:40 --

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

может эта формула дает все решения?

Увы я не Матиясевич. Вывести формулу вычисления всех простых чисел мне не по силам.

[dmd]

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

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

[Pavlovsky]

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

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

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

[Nataly-Mak]

У меня получилось 16 операций на вычисление приведённого "упакованного" полинома:

1,2,4,6,36,38,72,1296,...,403291461126605635584000000

Операции начала считать от 38 - $(x+2)$.
В готовом решении 20 шагов.

Имею решение для 26! в 18 шагов; плохое, но лучше, чем полученное сейчас.

Я действовала не оптимальным образом? Странно, что полученный "упакованный" полином не дал 16 шагов в решении, как это получено у Pavlovsky.

[Pavlovsky]

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

Я действовала не оптимальным образом?

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

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

Если dmd не ошибся, то решение должно начинаться так: 1,2,4,6,36 и должно получиться решение в 17 операций (Опс. Или 19 операций?! Ведь числа 2,4 нам тоже надо вычислить.).

Ну и не надо забывать про теорему Оливоса. Умножать надо в правильном порядке.

[Nataly-Mak]

Стоп! А откуда у вас числа 6 и 36?
Разве их не надо тоже получить, начиная с числа 1?

Я же выложила решение. Могу полностью выложить, решение всё равно очень плохое - 20 шагов.
Последовательность я вводила в программе mertz. Готовое решение в программе взяла.

Цитата:

...решение должно начинаться так: 1,2,4,6,36

Ну, я так и начинала решение. Только на вычисление полинома у меня ушло 16 шагов (операций) (начиная с вычисления 38). Как у вас получается решение в 16 шагов??

За 15 операций вычислить полином мне не удалось. Но пусть даже я потеряла 1 шаг и полином вычисляется за 15 шагов. Но в итоге-то всё равно в решении никак не 16 шагов!

[Pavlovsky]

Ну у меня полином упакован не так как у dmd. Хотя совпадений много.

[Nataly-Mak]

Ну, теперь понятно.
То есть, ваш порядок вычислений даёт-таки решение в 16 шагов.

Сейчас попробую по-другому вычислить "упакованный" полином. Где я потеряла одну операцию (точнее, не потеряла, а наоборот лишнюю операцию использовала)? А может быть, и не одну? Может быть, полином вычисляется не за 15 операций, а меньше?

-- Вс мар 10, 2013 12:20:38 --

Сейчас ввела в Вольфраме наобум:

$x^7+2x^5+10x^4+16x^3+20x^2+24x=21!$

Выдалось значение для корня этого уравнения, но оно не является целым числом.

[Pavlovsky]

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

$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$

Совсем не хотел подсказывать. Но получилось море подсказок. Ну да бог с ним. Зарождается новая математическая теория, а это важнее любого самого уважаемого конкурса.
Очевидно в последовательности должны быть числа $(2 + x)$ и $2 x (2 + x)$
То есть возможны два варианта начала последовательности.

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

-- Вс мар 10, 2013 13:57:19 --

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

Выдалось значение для корня этого уравнения, но оно не является целым числом

Так сделайте как я. Возьмите свое решение. И постепенно заменяйте в нем числа на числа и операцию из которого оно получено. Делайте это пока у вас не останется одно число (плюс маленькие числа типа 1,2,...). Замените его на x. Потом полученное выражение загоните в вольфрам. Фольфрам вам сам выдаст полином и альтернативные упаковки полинома.

[Nataly-Mak]

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

-- Вс мар 10, 2013 13:02:26 --

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

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

Выдалось значение для корня этого уравнения, но оно не является целым числом

Так сделайте как я. Возьмите свое решение. И постепенно заменяйте в нем числа на числа и операцию из которого оно получено. Делайте это пока у вас не останется одно число (плюс маленькие числа типа 1,2,...). Замените его на x. Потом полученное выражение загоните в вольфрам. Фольфрам вам сам выдаст полином и альтернативные упаковки полинома.

А зачем это надо - преобразовывать мои не оптимальные решения? Разве это может дать какое-то улучшение?

[Pavlovsky]

Тот же полином, но x=6.
$32 x^{32}+544 x^{30}+4088 x^{28}-32 x^{27}+17840 x^{26}-416 x^{25}+49924 x^{24}-2280 x^{23}+93304 x^{22}-6816 x^{21}+117570 x^{20}-11984 x^{19}+98514 x^{18}-12408 x^{17}+52885 x^{16}-7122 x^{15}+17007 x^{14}-1960 x^{13}+2910 x^{12}-200 x^{11}+200 x^{10}$