Factorials

[Nataly-Mak]

Не все полиномы полезны, однако
Вот мой полином для 29!, кажется, бесполезный. Сколько ни билась, меньше 19 шагов не получается.
А вот у кого-то есть оптимальное решение в 17 шагов и соответствующий ему оптимальный полином, уже упакованный самым наилучшим образом
Но этот полином мы узнаем только после конкурса.

[Pavlovsky]

Прыжок Тигра.

38 23.11 Vladimir Chirkov Bobruisk, Russia 19 Mar 2013 09:41

[Nataly-Mak]

Красиво!

И третье место заняли

Цитата:

3 25.00 Martin Piotte Montreal, Quebec, Canada 17 Mar 2013 19:36

Walter Trump, который вот только был на 15-ом месте, уже в десятке:

Цитата:

10 24.42 Walter Trump Nuremberg, Germany 18 Mar 2013 06:51

Поразительно!

А самые умные американцы живут в штате Калифорния

Цитата:

1 25.00 Tomas Rokicki Palo Alto, California, United States 22 Feb 2013 03:36
6 24.74 John Morris Simi Valley, California, United States 5 Mar 2013 14:14
8 24.52 Siva Dirisala Foster City, California, United States 18 Mar 2013 07:35
13 24.37 Andy Sloane Sunnyvale, California, United States 8 Feb 2013 21:39

[Vovka17]

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

Прыжок Тигра.

38 23.11 Vladimir Chirkov Bobruisk, Russia 19 Mar 2013 09:41

Да, прыжок, но о-о-очень ме-е-е-дленный. Сейчас программа дошла только до середины (и это максимально сильно урезанный в вариантах расчет). Так что мои слова насчет понедельника, похоже, окажутся точными, но только для следующего понедельника .
Наверное, всё-таки займусь с завтрашнего дня разбором многопоточного программирования. Паша, мой напарник, точно бы разобрался быстро, на него и надежда, только вот что-то давненько он переключился исключительно на свою основную работу и мне приходится воевать с кодингом в одиночку...
Текущее отставание от лидеров - 41 пункт - очень много. А то, что на десяток позиций сегодня поднялся - так это просто ввёл, наконец, решение для 37! - пока довольно ужасное - 26 шагов .

[Nataly-Mak]

Vovka17 в сообщении #698319 писал(а):

...ввёл, наконец, решение для 37! - пока довольно ужасное - 26 шагов.

Да, для ИИ это не очень сильное решение
Моё ручное решение 25 шагов.

[dmd]

Внимание - святое первочувство, оно богом дадено, ничего грехитрого в нём нет. Всё нафлуженное про 19! и 26! естественным образом подсказывало структуру будущего решения. Поэтому конечно конкретности лучше не выкладывать. Но абстрактными идеями делиться можно и должно. Наблюдение оптимально упакованных полиномов даёт само собой новые идеи. Например вот. Каждый явно выраженный дивизор в оптимальной упаковке имеет лёгкую структуру. Почти всегда для базовой последовательности типа 1,2,4,6,36 такой дивизор по модулю $kx$, где $x=36, k= \{ 1,2,4,6,36\}$, имеет остаток в форме $uv$, где $u=v=\{ 1,2,4,6\}$. Можно пробежаться по всем делителям N! и отфильтровать такие потенциально оптимальные дивизоры для последующей ручной упаковки. Если для подобной идеи будут результаты, то дальше её надо пытаться формально алгоритмизировать. У меня, к сожалению, есть время только на коротенькие алгоритмы для полу-ручного поиска.

[Pavlovsky]

Хорошая идея, можно попробовать. Только смущает:

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

Можно пробежаться по всем делителям N!

37!=2^34×3^17×5^8×7^5×11^3×13^2×17^2×19×23×29×31×37

Количество делителей = 35×18×9×6×4×3×3×2×2×2×2×2=39191040.

40 миллионов, многовато.

[dmd]

У меня основная среда для алгоритмических вычислений - pari/gp. До 35! включительно могу в винде за 18 секунд сформировать список всех делителей, для 36! и 37! только в линухе, т.к. там настоящая 64-разрядность.

                                                  GP/PARI CALCULATOR Version 2.5.3 (released)
                                           i686 running mingw (ix86/GMP-5.0.1 kernel) 32-bit version
                                                    compiled: Oct  3 2012, gcc-4.6.3 (GCC)
                                               (readline not compiled in, extended help enabled)

                                                    Copyright (C) 2000-2011 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.

parisize = 1000000000, primelimit = 500509
? #
   timer = 1 (on)
? w=divisors(35!);
time = 17,690 ms.
? #w
time = 0 ms.
%2 = 16422912

Если на каждом дивизоре проверять всего лишь несколько вариантов остатков, то, думаю, совокупно по всему списку проверка составит не более нескольких минут даже для 37!. Потому что это pari/gp! Присоединяйтесь! Я математику люблю сильнее, чем лень любит меня, поэтому заставил себя освоить программирование в pari/gp.

[Nataly-Mak]

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

Всё нафлуженное про 19! и 26! естественным образом подсказывало структуру будущего решения.

Да, о решении для 19! писали, в самом деле, много.
А вот что-то о "нафлуженном" о решении для 26! я не припомню
К тому же, я, например, вообще ничего не знала о структуре будущего решения для 26!
[почти все свои решения составляла на основе разложения $2n! =K \cdot(n!)^2$ ].
У меня была в наличии ваша упаковка, которая, как вы написали, вычисляется за 16 операций. Просто попыталась в этой упаковке сократить число операций, мне удалось свести количество операций к 13. Как оказалось, можно эту упаковку ещё доработать и довести её вычисление до 11 операций.

Цитата:

Почти всегда для базовой последовательности типа 1,2,4,6,36 такой дивизор по модулю $kx$, где $x=36, k= \{ 1,2,4,6,36\}$, имеет остаток в форме $uv$, где $u=v=\{ 1,2,4,6\}$.

Несколько смущает "почти всегда". То есть это условие может выполняться, а может и не выполняться?
Кроме того, такой вопрос: это условие необходимое для оптимальности упаковки, или необходимое и достаточное, или только достаточное

-- Ср мар 20, 2013 05:49:13 --

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

У меня основная среда для алгоритмических вычислений - pari/gp. До 35! включительно могу в винде за 18 секунд сформировать список всех делителей, для 36! и 37! только в линухе, т.к. там настоящая 64-разрядность.

А в Винде не настоящая 64-разрядность?

Цитата:

Потому что это pari/gp! Присоединяйтесь! Я математику люблю сильнее, чем лень любит меня, поэтому заставил себя освоить программирование в pari/gp.

А, PARI/GP...
Помню
Большой любитель этого языка maxal.
На форуме даже есть тема, в которой он давал несколько уроков для начинающих. Я тогда хотела попробовать этот язык, но... не получилось
[причин много; лень в список причин не входит: вряд ли я отношусь к ленивым людям ].
Очень интересен эксперимент, выполненный maxal.
Это была проверка одной моей гипотезы по магическим квадратам. С точки зрения программирования проверка гипотезы - тупой перебор, причём очень долгий. Я на своём Бейсике даже и не пыталась это выполнить. Высказала гипотезу, что магических квадратов такого вида не существует. Гипотеза была высказана в теме "Магические квадраты".
maxal заинтересовался и решил выполнить проверку гипотезы. И программу для этого он написал на PARI/GP. Он мне тогда прислал и текст программы. Программа работала несколько часов.
Гипотеза подтвердилась

Pavlovsky
кстати, рекомендую вам.
Я тогда читала первые уроки maxal по PARI/GP. Там нет ничего сложного, всё очень понятно.
А быстродействие --- да, впечатляет.

-- Ср мар 20, 2013 06:11:25 --

Вот нашла и тему maxal
"Интерактивный курс: введение в программирование на PARI/GP"
Тема и была создана в то время, когда maxal выполнял описанный эксперимент. Он очень рекомендовал мне этот язык, прислал все нужные ссылки, что нужно скачать, чтобы начать программировать на этом языке.
Эх! Очень жалею, что не смогла тогда это сделать

[Nataly-Mak]

dmd
предлагаю вам, как специалисту по оптимальным упаковкам, определить, какая из следующих трёх упаковок одного и того же полинома самая оптимальная:
1.
$(2x (x+2) (x-28)+x) x (x+2)(1+2 x (x+2)) ((x+2 x (x+2)) (x (x+2) (1+2 x (x+2))-6x))^2$

2.
$x(x+2)(2x(x+2)+1)(8 \cdot 2x(x+2)+x)((x(x+2)(2x(x+2)+1)-6x)(2x(x+2)+x))^2$

3.
$x^5 (x+2) (2 x+5)^2 (2 x (x+2)+1) (2 (x-28) (x+2) x+x) ((x+2) (2 x (x+2)+1)-6)^2$

$x=36$ для всех трёх упаковок.

На мой взгляд, самая плохая упаковка последняя (предложена Вольфрамом).
Ну и, конечно, самый интересный вопрос: можно ли ещё оптимизировать самую оптимальную упаковку
[Ответ на этот вопрос будет подсказкой, поэтому не прошу ответить. Это потом, после конкурса.]

-- Ср мар 20, 2013 07:42:11 --

О, какая удача! В архиве сохранилось письмо от Макса по поводу описанного эксперимента:

Цитата:

Программу я переписал под PARI/GP (текст ниже). В принципе то, что я уже
рассказал в "введении в программирование на PARI/GP", должно
быть достаточно для ее понимания и проверки соответствия оригиналу. Так
что, проверьте правильность на всякий случай.

Кроме того, я ее прогнал на своем компьютере: все вычисления заняли 8
часов, но ни одного квадрата найдено не было. :(

Это уже история, история нашего сотрудничества в теме "Магические квадраты". Эх... какие были времена!
В письме и текст программы сохранился. Я тогда его проверила на соответствие оригиналу, как просил Макс. А текст Макс переписывал, наверное, с моей программы на Бейсике (ибо --- "переписал").
Если кто захочет освоить этот язык, могу прислать программу Макса, как отличный образец программирования на этом языке.

[Nataly-Mak]

(Оффтоп)

Ещё в письме есть ссылка на официальную страничку Макса. Сейчас заглянула на неё.
Хочу представить всем:
http://www.cse.sc.edu/~maxal/
На страничке ссылки на его работы, это должно быть интересно.
Помнится, svb в какой-то теме приводил эту ссылку.
Повторила, думаю, не помешает.

[dimkadimon]

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

(Оффтоп)

Ещё в письме есть ссылка на официальную страничку Макса. Сейчас заглянула на неё.
Хочу представить всем:
http://www.cse.sc.edu/~maxal/
На страничке ссылки на его работы, это должно быть интересно.
Помнится, svb в какой-то теме приводил эту ссылку.
Повторила, думаю, не помешает.

Так он профессор - круто! У него много интересных статей. Он занимал призы в математических и компьютерных олимпиадах. Спасибо за ссылку.

[dmd]

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

dmd
предлагаю вам, как специалисту по оптимальным упаковкам, определить, какая из следующих трёх упаковок одного и того же полинома самая оптимальная:
1.
$(2x (x+2) (x-28)+x) x (x+2)(1+2 x (x+2)) ((x+2 x (x+2)) (x (x+2) (1+2 x (x+2))-6x))^2$

2.
$x(x+2)(2x(x+2)+1)(8 \cdot 2x(x+2)+x)((x(x+2)(2x(x+2)+1)-6x)(2x(x+2)+x))^2$

Так 1. и 2. одинаковы, ибо $(x-28)=8$. Любой специалист-неспециалист посчитает количество шагов, оно получается 15.

Эвристика "Почти всегда" явно наблюдается в этой упаковке. Делитель $(2x(x+2)+1)$ по модулю $2x$ имеет остаток $1$. Делитель $(2x(x+2)+x)$ по модулю $2x$ имеет остаток равный $x$. Делитель $(8 \cdot 2x(x+2)+x)$ по модулю $2x$ - остаток $x$. Но для делителя $(x(x+2)(2x(x+2)+1)-6x)$ эта схема уже не выполняется. Соответственно разбор подобных делителей можно оставить на заключительную часть алгоритма, где сделать увеличение базы с $\{1,2,...,x\}$ до, например, $\{1,2,...,x,(2x(x+2)+1)\}$. Т.е. для оптимальной упаковки оптимальные дивизоры должны иметь по базовым модулям только базовые остатки.

[Nataly-Mak]

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

Так 1. и 2. одинаковы, ибо $(x-28)=8$. Любой специалист-неспециалист посчитает количество шагов, оно получается 15.

Совершенно верно, что сразу же и заметил whitefox (упаковка, в которой $(x-28)$ заменено на 8, принадлежит ему).
Количество операций, верно, 15; то есть решение получается в 19 шагов и никак не меньше

Цитата:

Эвристика "Почти всегда" явно наблюдается в этой упаковке.

Спасибо за пояснения.

[Pavlovsky]

Все таки я дожал 26!. Есть 15 операций!

Еще у меня нет рекордов для N=22,23. Но это временное недоразумение. Пока у меня все вычислительные ресурсы брошены на поиск решений для больших N>32. А пока N=22,23 это мой гарантированный резерв пополнения очкового баланса.