Factorials

[Pavlovsky]

Xaositect Спасибо.

Последовательности для N<=149. Как раз этого не хватало. Для текущей задачи этого хватит с огромным запасом.

-- Пн фев 18, 2013 13:24:24 --

Остается построить все последовательности для чисел вида $\prod_{i=1}^{n}{{x_i}^{k_i}}$. Для текущей задачи достаточно построить последовательности длины 10 и меньше. Полагаю их не так много.

Например для 11! последовательность может заканчиваться так: 77*80*80*81=39916800.

${77}^{1}{80}^{2}{81}^{1}$ Так как для пострения наименьшей последовательности умножений основание не важно, то задачу можно записывать так: (1,1,2). Что означает построить последвательность умножений наименьшей длины для выражения вида ${A}^{1}{B}^{1}{C}^{2}$

-- Пн фев 18, 2013 13:39:40 --

До кучи. Нижняя оценка длины последовательности умножений
$L(\prod_{i=1}^{n}{{x_i}^{k_i}}) \ge n-1+max(L({x_i}^{k_i}))$, где L() минимальная длина последовательности.

[Xaositect]

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

До кучи. Нижняя оценка длины последовательности умножений
$L(\prod_{i=1}^{n}{{x_i}^{k_i}}) \ge n-1+max(L({x_i}^{k_i}))$, где L() минимальная длина последовательности.

Это не нижняя, это точная оценка(Теорема Оливоса): длина векторной цепочки для $(n_1,\dots,n_k)$ (в терминах мономов, сложность вычисления $x_1^{n_1}\dots x_k^{n_k}$), равна k - 1 + длина аддитивной последовательности для $n_1,\dots,n_k$ (т.е. сложности одновременного вычисления $x^{n_1},\dots,x^{n_k}$).

Доказывается так: аддитивную цепочку можно представить в виде орграфа, где истоки - это исходные переменные, а внутр. вершины - это умножения. Будем считать, что в вершинах может быть не только бинарное умножение, но и большего количества входов. Такую сложную вершину можно "расклеить", получив несколько бинарных. Длина цепочки в таком представлении равна (количество ребер - количество вершин + 1). Например, граф $\xymatrix{x\ar[r]\ar@/{}^1em/[r]\ar@/{}_1em/[r] & x^3\ar[r]\ar@/{}^1em/[r]\ar@/{}_1em/[r] & x^9}$ представляет цепочку $1,2,3,6,9$.
Теперь, для того, чтобы получить из графа для набора $x^{n_1},\dots,x_{n_k}$ граф для монома $x_1^{n_1}\dots x_k^{n_k}$ надо сделать следующее:
1) развернуть все ребра
2) к каждому бывшему выходу $x^{n_i}$ присоединить вход $x_i$.
Например, возьмем цепочку $1,2,3,6,8,9$, вычисляющую $x^8$ и $x^9$. Соответствующий граф

$$\xymatrix{x\ar[r]\ar@/{}^1em/[rr]\ar@/{}_1em/[r] & x^2\ar[r]\ar@/{}_1em/[rrr] & x^3\ar[r]\ar@/{}^1em/[r]\ar@/{}_1em/[rrr] & x^6\ar[r]\ar@/{}^1em/[rr] & x^8 & x_9}$$

После проделывания указанной операции, получаем

$$\xymatrix{x_1^8 x_2^9 & x_1^3 x_2^3\ar[l]\ar@/{}^1em/[l] & x_1^2 x_2^3\ar[l]\ar@/{}_1em/[ll] & x_1 x_2\ar[l]\ar@/{}_1em/[l] & x_1\ar[l]\ar@/{}^1em/[lll] & x_2\ar@/{}^1em/[lll]\ar@/{}_1em/[ll]\\ & & & & x_1\ar[u] & x_2\ar[u]},$$

что соответствует цепочке $(1,0), (0,1), (1,1), (2,2), (2,3), (3,3), (6,6), (8,9)$ ($x_1, x_2, x_1 x_2, x_1^2 x_2^2, x_1^2 x_2^3, x_1^3 x_2^3, x_1^6 x_2^6, x_1^8 x_2^9$)
В обратную сторону это преобразование также работает.

[Pavlovsky]

Xaositect
Не знаю как выразить свое восхищение!! Ну что вся математика есть, осталось ее закодировать.

По моим прикидкам это позволит мне набрать ориентировчно 23,5 балла.

[Nataly-Mak]

Pavlovsky
ваши новые результаты - это уже математика начала работать?
Ох и математику вы раскопали! Я что-то пока никак не врублюсь

Нашла в БД mertz такое равенство:

104006=322^2+322=2*7*17*19*23

Имеем очень много подобных равенств:

2^2+2=6=2*3
3^2+3=12=2^2*3
и т.д.

Интересуют такие равенства для больших чисел.

-- Вт фев 19, 2013 10:29:31 --

В первой десятке лидеры, туда вообще очень трудно пробиться.
Это вторая десятка:

Цитата:

11 23.83 Kalachev Gleb Moscow, Russia 3 Feb 2013 16:52
12 23.75 Rick Hennig Denver, Colorado, United States 15 Feb 2013 14:11
13 23.71 Siva Dirisala Foster City, California, United States 17 Feb 2013 11:08
14 23.57 Mark Mammel Ellicott City, Maryland, United States 28 Jan 2013 14:22
15 23.54 Wes Sampson La Jolla, California, United States 16 Feb 2013 18:51
16 23.35 Tyson Jacobs Nashville, Tennessee, United States 11 Feb 2013 04:59
17 23.34 Alex Chernov Penza, Russia 18 Feb 2013 16:00
18 23.24 Daniel Hartmeier Basel, Switzerland 14 Feb 2013 17:46
19 23.14 Thomas Hupfer Nuremberg, Germany 16 Feb 2013 10:35
20 23.10 Walter Trump Nuremberg, Germany 15 Feb 2013 15:08

Здесь наших двое.
Вчера обновил результаты Алексей Чернов. Это радует, значит, ещё есть ресурсы.
Ещё не вечер

[Pavlovsky]

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

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

Это пока старые наработки. Не спеша шлифую алгоритмы для получения рекордных результатов. Пока у меня 8 повторений рекордов N=13-18,20,21.
Список участников вводящих только рекордные результаты:

107 17.00 Eckard Specht Magdeburg, Germany 18 Feb 2013 21:53
203 10.00 Petr Lishaynikov Saint Petersburg, Russia 4 Feb 2013 08:00
204 10.00 Benjamin Chaffin Portland, Oregon, United States 14 Feb 2013 07:16
217 9.00 Yurii Sigolaev Saint Petersburg, Russia 19 Feb 2013 00:57
235 8.00 Klaus Müller Koblenz, Germany 30 Jan 2013 08:14
236 8.00 Klaus Nagel München, Germany 19 Feb 2013 02:59

[Nataly-Mak]

Тоже 19! не поддаётся?

[Pavlovsky]

Мне много чего не поддается. На 19! не зацикливаюсь. Исследую проблему неспеша.
Первая строка N. Вторая строка рекорды. Один из рекордов меньше на единицу. Третья строка мои результаты.

13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37
11   11   12   12   12   13   13   14   14   14   15   15   16   15   16   16   17   17   19   18   19   18   20   20   20
11   11   12   12   12   13   15   14   14   15   17   17   19   19   20   19   20   21   21   22   --   24   --   33   29

[Nataly-Mak]

Близкие у нас с вами результаты
Мои c N=20:

20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37
16   17   17   17   18   19   19   20   21   21   20   21   23   24   24   26   26   28

У меня 28! и 29! портят картину. И что-то не поддаются улучшению

[Nataly-Mak]

У россиян мощное подкрепление

Цитата:

36 22.00 Vadim Trofimov Saint Petersburg, Russia 19 Feb 2013 12:46

Надо понимать, что 22 оптимальных решения у него уже имеется. Осталось чуть-чуть.

[ben_burrows]

@Pavlovsky (& others) does your solver work from 1 and go forward, or from N! and go backward? Does it backtrack, or is it greedy?

I'm considering backwards search from N! with backtracking. But, even if addition is limited to very small numbers, I'm finding that there are just too many possible ways of factoring out primes. Sometimes it's best to take out a full square, other times it's best to leave some terms in because there are tricks to get rid of them. Given $p_1^{n_1} \cdot p_2^{n_2} \cdot p_3^{n_3}$..., I don't see a single technique to break that in half that consistently produces short programs.

Thoughts? Advice?

[Nataly-Mak]

Попробовала предложенную Pavlovsky математику для 19!

19! = 5*143*323*(35*144^2)^2

Ничего хорошего не получилось, --- решение в 16 шагов.
Столько же шагов у меня в найденном раньше решении.

Неудачное разложение? Или эта математика для 19! не работает?

[Pavlovsky]

ben_burrows в сообщении #685789 писал(а):

Thoughts? Advice?

Как бы мы не организовали перебор вперед от 1 или назад от N!, количество вариантов будет громадным. Вижу только один выход, использовать эвристические процедуры сокращения количества вариантов. При этом мы естественно рискуем потерять рекордный результат. Есть ли смысл обсуждать различные эвристики?! У эвристик не может быть математического обоснования. Только вычислительный эксперимент! Дала эвристика результат, значит это хорошая эвристика!

-- Ср фев 20, 2013 09:35:23 --

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

Или эта математика для 19! не работает?

Я уже писал, что не работает. В рекордной последовательности для 19! в конце слишком мало умножений. Можно считать почти доказанным в последовательности длиной 13 для 19! в конце максимум 2 умножения.

[Nataly-Mak]

Xaositect в сообщении #685208 писал(а):

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

До кучи. Нижняя оценка длины последовательности умножений
$L(\prod_{i=1}^{n}{{x_i}^{k_i}}) \ge n-1+max(L({x_i}^{k_i}))$, где L() минимальная длина последовательности.

Это не нижняя, это точная оценка(Теорема Оливоса): длина векторной цепочки для $(n_1,\dots,n_k)$ (в терминах мономов, сложность вычисления $x_1^{n_1}\dots x_k^{n_k}$), равна k - 1 + длина аддитивной последовательности для $n_1,\dots,n_k$ (т.е. сложности одновременного вычисления $x^{n_1},\dots,x^{n_k}$).

Xaositect
вы уверены, что приведённая формула даёт точную оценку длины последовательности умножений?

Пример 1:
5^3*7^2*143*144^4*323
L=5-1+2=6
фактически имеем 7 умножений

Пример 2:
35^2*144^4*323*715
L=4-1+2=5
фактически имеем 5 умножений

Я ошибаюсь?

P.S. Пожалуйста, посмотрите нашу дискуссию с Pavlovsky на ПЕН

[Xaositect]

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

5^3*7^2*143*144^4*323
L=5-1+2=6

Откуда 2? Сложность для $3,2,1,4,1$ будет 3 (собственно, цепочка $1,2,3,4$)
А во втором примере все хорошо.

-- Ср фев 20, 2013 08:50:54 --

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

P.S. Пожалуйста, посмотрите нашу дискуссию с Pavlovsky на ПЕН

Проблемы терминологии. Аддитивной цепочкой для $n$ называется straight-line программа со сложениями, в которой последним элементом является $n$. Аддитивной последовательностью для $n_1,\dots,n_k$ называется straight-line программа со сложениями, содержащая все числа $n_1,\dots,n_k$

-- Ср фев 20, 2013 08:52:03 --

Собственно, я об этом писал:

Xaositect в сообщении #685208 писал(а):

длина аддитивной последовательности для $n_1,\dots,n_k$ (т.е. сложности одновременного вычисления $x^{n_1},\dots,x^{n_k}$).

-- Ср фев 20, 2013 08:58:46 --

Внимательно посмотрел на формулировку Pavlovsky. Извиняюсь, что ввел в заблуждение, просто увидел знакомую формулу.

[Nataly-Mak]

Xaositect в сообщении #685999 писал(а):

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

5^3*7^2*143*144^4*323
L=5-1+2=6

Откуда 2? Сложность для $3,2,1,4,1$ будет 3 (собственно, цепочка $1,2,3,4$)
А во втором примере все хорошо.

2 - это у меня длина аддитивной последовательности для 144^4.
Это неправильно я понимаю?
По моему пониманию длина аддитивной последовательности (максимальная) в обоих примерах одинакова и равна 2, по вот этой аддитивной последовательности получения степени 4:
1,2,4

Если рассмотреть формулу с этой точки зрения, то она даёт действительно нижнюю оценку для длины последовательности умножений, как и написал Рavlovsky.

Какой будет формула для точной оценки?

-- Ср фев 20, 2013 09:11:55 --

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

До кучи. Нижняя оценка длины последовательности умножений
$L(\prod_{i=1}^{n}{{x_i}^{k_i}}) \ge n-1+max(L({x_i}^{k_i}))$, где L() минимальная длина последовательности.

"...где L() минимальная длина последовательности"

Какой последовательности?

Например, L(144^4) чему равно?
Я считаю, что это равно 2.