Factorials

[Pavlovsky]

Herbert Kociemba в сообщении #702521 писал(а):

I never read a single word about the claim that the results cannot be improved from any of them.

Естественно напрямую они этого не говорили. Увы при переводе нюансы моего сообщения пропадают.

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

[Nataly-Mak]

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

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

Просто эти результаты были более простыми и их нашли эти четверо человек почти синхронно, но и то только "почти". Значит, даже эти результаты найти было не очень просто.
Как верно писал Vovka17, и в прошлых конкурсах многие делали упор на повторение уже полученных рекордов, так как это проще: уже точно знаешь, что такие результаты существуют. Мало кто отваживается на поиск новых рекордов - это путь первопроходцев и он, разумеется, сложнее.

-- Чт мар 28, 2013 13:28:39 --

Возвращаясь к полиномизации оптимальных решений...
Нашла полином по своему оптимальноиу решению для 21!

$f(x)=262144 x^{18}+1114112 x^{17}+1785856 x^{16}+1208320 x^{15}+96256 x^{14}-308224 x^{13}-150016 x^{12}-17920 x^{11}+2560 x^{10}+512 x^9$

$x=6$

dimkadimon
не расстраивайтесь
Это всего лишь полином, который оптимально упаковать, чтобы получить решение в 14 шагов, очень не просто. Попробуйте!

Вольфрам, например, предлагает такие упаковки:

$512 x^9 (x+1)^3 (2 x-1) (2 x+1) (4 x+1)^2 (8 x^2+6 x-1)$
$-64 (-8 x+ \sqrt{17}-3) x^9 (x+1)^3 (2 x-1) (2 x+1) (4 x+1)^2 (8 x+\sqrt{17}+3)$

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

[dimkadimon]

Предлагаю интересную но сложную задачу: найти решение для 100! Это число имеет более 150 цифр!

На даный момент мое лучшее решение это 74 шага:

(Оффтоп)

74: 1, 1+1, 2+2, 2+3, 4*4, 5*5, 6*6, 7*7, 7*8, 9*9, 3+6, 11*11, 12*12, 12*13, 10*14, 11*15, 7-12, 16*17, 3+17, 18*19, 6+17, 20*21, 5-21, 21+23, 24*24, 25*25, 22*26, 19+24, 27*28, 23*29, 23+28, 30*31, 4-23, 32*33, 1+17, 34*35, 19-33, 36*37, 37*38, 5-11, 39*40, 2+5, 6+42, 41*43, 1-43, 2-45, 46*46, 44*47, 45*48, 37+46, 49*50, 5+45, 51*52, 37-45, 5-54, 53*55, 55*56, 4-55, 57*58, 54*59, 11-46, 60*61, 5-55, 62*63, 61-64, 61-63, 1-66, 67*67, 64*68, 68*69, 58+66, 70*71, 5+71, 72*73, 66*74

Например a+b это сложить число номером а и число номером b (первое число имеет номер 1). При минусе я беру абсолютный результат. Эта последовательность начинается 1, 2, 4, 6, 36, 1296 ...

Кстати я заметил что мои обычные методы часто застревают и так и не доходят до 100!

[Vovka17]

whitefox в сообщении #702525 писал(а):

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

Если посмотреть http://oeis.org/A173419, то можно убедиться, что минимальные длины последовательностей для различных N сильно скачут. Так что боюсь что в этом деле гармониии нет.
Когда для 25! минимальная длина последовательности 16 операций, а для 26! - 15 это вполне вероятная ситуация.

Этот ряд для последовательных чисел.
Возможно, что ряд для факториалов подчиняется совсем другим правилам.

Придерживаюсь мнения Pavlovsky: Даже при малых N, значения ряда http://oeis.org/A173419 "скачут" и, чем больше будут N, тем более значительные перепады будут встечаться (я этого не доказывал, но для меня это практически очевидный факт). Ряд для факториалов - это просто выборка из ряда натуральных чисел ("почти случайная"). И, следовательно, ряд для факториалов будет обладать такими же перепадами, которые были в ряду натуральных чисел.

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

Предлагаю интересную но сложную задачу: найти решение для 100! Это число имеет более 150 цифр!..
На даный момент мое лучшее решение это 74 шага.
Кстати я заметил что мои обычные методы часто застревают и так и не доходят до 100!

Мой метод не способен находить такие длинные ряды (у меня лишь простой перебор с непростыми отсечениями ). А что либо переделывать сейчас нет ни сил, ни времени, ни идей.
Сегодня дописал многопоточность. Не так уж и страшно, как я предполагал . Всё! Больше я не кодю, - в оставшееся время буду пожинать плоды. Жаль, что не добрался для расчетов до "нормального" компьютера. Приходится считать только в 4 потока...

[dmd]

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

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

Когда для 25! минимальная длина последовательности 16 операций, а для 26! - 15 это вполне вероятная ситуация.

Почему эта ситуация вполне вероятная?
Мне это не кажется очевидным. Почему бы для 25! не найти последовательность в 15 шагов? Чем 25! хуже 26!

Тем, что количество сочетаний степеней двойки и тройки в 25! меньше на 11 штук, чем в 26!. Поэтому вероятность плотнее упаковаться у 26! выше. Это конечно за конкретный рекорд 25! ничего не говорит, это просто вероятностно-числовые соображения.

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

Возвращаясь к полиномизации оптимальных решений...
Нашла полином по своему оптимальноиу решению для 21!

$f(x)=262144 x^{18}+1114112 x^{17}+1785856 x^{16}+1208320 x^{15}+96256 x^{14}-308224 x^{13}-150016 x^{12}-17920 x^{11}+2560 x^{10}+512 x^9$

$x=6$

dimkadimon
не расстраивайтесь
Это всего лишь полином, который оптимально упаковать, чтобы получить решение в 14 шагов, очень не просто. Попробуйте!

Попробовал.

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

и

$2 (y + 6) (3\cdot 2 (y + 6) + 4) (4 y - 1) ((4 y - 1) + 5 y) (2 (y + 6) (2 (y + 6) - 9) y)^2$
$y=36$

Всё-таки считаю субъективное "очень не просто" не изоморфно, извините за каламбур. Кому-то может оказаться и очень просто.

[Nataly-Mak]

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

Попробовал.

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

Эта упаковка вычисляется за 11 операций? Сейчас попробую

Вы "14 шагов" правильно поняли? Это относится уже ко всему окончательному решению для 21!, а не к полиному. Полином должен вычисляться за 11 шагов (когда x=6).

Ну, моё "субъективное" "очень не просто" не относится к таким крупным специалистам по упаковкам, как вы.

-- Чт мар 28, 2013 20:28:07 --

У меня первая упаковка за 11 операций никак не вычисляется.
Даже и в 14 операций с ходу не уложилась.

Вторая упаковка должна вычисляться за 10 операций (ибо x=36).
Может быть, это моё субъективное мнение: за 10 операций вычислить эту упаковку невозможно.
Конечно, если её преобразовать и сделать более оптимальной...

Так я имела в виду именно такую оптимальную упаковку, которая вычисляется за 11 операций при x=6 и за 10 операций при x=36, а не первые приближения к такой оптимальной упаковке.

Кстати, в моём решении отсутствует 36, поэтому я составила полином для x=6.

[whitefox]

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

Тем, что количество сочетаний степеней двойки и тройки в 25! меньше на 11 штук, чем в 26!. Поэтому вероятность плотнее упаковаться у 26! выше.

Количество сочетаний степеней двойки и тройки в 25! точно такое же как и в 24!.
По Вашей гипотезе они будут иметь одинаковую упаковку?

-- 28 мар 2013, 21:15 --

Количество сочетаний степеней двойки и тройки в 18! на 41 больше чем в 17!.
По Вашей гипотезе 18! можно упаковать плотнее чем 17!

[dmd]

25! больше 24! только лишь в 25 раз. А 26! больше 25! не только этим, но и тем.

-- Чт мар 28, 2013 22:22:20 --

По моей гипотезе при движении дальше 37! подобные провалы в графике будут наблюдаться еще глубже.

-- Чт мар 28, 2013 22:32:47 --

В этом ключе заслуживает внимания 32! - возможно в нём сидит не найденный рекорд.

[whitefox]

dmd
А что ответите насчёт 18! и 17!

-- 28 мар 2013, 21:45 --

В 18! тоже сидит не найденный рекорд?
А как тогда быть с этим:

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

mertz перебрав все последовательности длиной 12 операций доказал минимальность результатов для N<=17. Как следствие, 13 операций минимально для N=18,19.

[Nataly-Mak]

dmd
а мне интересен ответ о приведённых вами оптимальных упаковках.
Они у меня что-то не вычисляются "очень просто" за нужное количество операций.

Или я тупая , или упаковки совсем не оптимальные.

[dmd]

whitefox
Думаю, 18! и 32! находятся в не сопоставимых весовых категориях. 18! анализируется почти вручную, для 32! нужен нетривиальный алгоритм; и не факт, что лидеры его нашли. Но может статься, что на самом деле алгоритм для всех N! почти тривиален. Просто дотянуться до него своим вниманием - нетривиальная задача. И я же ни чего конкретного не утверждал, о вероятностях только говорил.

Nataly-Mak
Ну просто так хотел сказать, что делиться упаковками надо отложить на месяц, чтоб не повторился казус Павловского.

[Nataly-Mak]

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

Ну просто так хотел сказать, что делиться упаковками надо отложить на месяц, чтоб не повторился казус Павловского.

Вообще-то я поделилась не упаковкой, а полиномом.
Вы написали, что упаковать этот полином для кого-то, в частности - для вас, очень просто.
Однако приведённые вами упаковки, на мой взгляд, далеки от оптимальной.

Свою оптимальную упаковку я ведь не выложила, а как раз отложила это до конца конкурса.

Я не расстроюсь, если для кого-то действительно окажется просто оптимально упаковать приведённый мной полином

[Pavlovsky]

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

Для начала хотя бы доказать, что существует последовательность длиной 14 для 22!

Независимо от других участников конкурса, доказал существование последовательности в 14 операций для 22!

Теперь у меня есть все рекорды от 13 до 27. Ползем дальше...

[dimkadimon]

Теперь есть 100! в 54 шага.

Гипотеза: количество шагов для N! приближается к N/2 для больших N.

-- 29.03.2013, 14:08 --

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

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

Для начала хотя бы доказать, что существует последовательность длиной 14 для 22!

Независимо от других участников конкурса, доказал существование последовательности в 14 операций для 22!

Теперь у меня есть все рекорды от 13 до 27. Ползем дальше...

Мне 22 тоже трудно далось. Красивое решение. Теперь я тоже застрял на 28.

[Pavlovsky]

Следующая цель убрать позорные плюс два от текущего рекорда для N=33,34,36. Собственно это и будет обещанные 24,5 балла (чуть меньше 24,47).