Factorials

[Nataly-Mak]

Pavlovsky
Поздравляю!
Догоняете прежних лидеров Valentin Dobrota и Herdert Kociemba.
Закрепились в клубе 24+
Ещё немного, ещё чуть-чуть

Walter Trump жжёт

Цитата:

8 24.57 Walter Trump Nuremberg, Germany 19 Mar 2013 17:58

[Pavlovsky]

Чтобы не было недоразумений, делаю заявление для всех.

Граждане России, иностранные граждане и лица без гражданства. Читайте эту ветку, в ней достаточно информации, чтобы найти решение для 26! в 15 операций.

[Nataly-Mak]

В какой ветке есть информация, как найти решение для 29! в 17 шагов?

Даже после преобразования упаковки по рекомендации Pavlovsky, выполненного whitefox, ничего путного не получилось. Наоборот, даже решение в 19 шагов не получилось

Не подумайте плохое Рекомендация дана здесь. В личной переписке сейчас с Pavlovsky не состою.

-- Ср мар 20, 2013 12:38:25 --

Вот она --- рекомендация:

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

Отталкиваясь от темы про полиномы, упорно ищу алгебраические преобразования экономящие операции. Увы кроме уже известного A(A+1)B^2=AB(AB+B), ничего интересного не нашел.
Кстати это преобразование можно применить и к:
$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$
Из него легко виделить конструкцию:
$2x(x+2) (2 x (x+2)+1)$

[Pavlovsky]

Вот такое загадочное преобразование.
Пусть у нас в последовательности есть числа A,B,C,D,E. Причем E=B*D.
И дано выражение: (A*B)*(A*B+C)*D^2, которое вычисляется за 5 операций.
Тогда после преобразований:
(A*B*D)*(A*B*D+C*D)=(A*E)*(A*E+C*D) получается 4 операции.

-- Ср мар 20, 2013 15:50:53 --

В моих алгоритмах полный перебор идет до последовательностей длиной 8 операций. Далее начинается балансировка между двумя противоречивыми требованиями:
1) Сократить перебор до возможности искать решения за реальное время;
2) И при этом не потерять рекордные решения.

A*B+C формируется за 10 операций и программа его видит. A*E+C*D формируется за 11 операций и программа уже его не видит. Трагедия нехватки глубины расчета всего на один шаг!

Эх если бы была техническая возможность делать полный перебор хотя бы для последовательностей длиной 9 опраций! Я бы давно имел 25 баллов. А так получается последовательностей длиной 8 около 6 миллионов. Последовательностей длиной 9 несколько миллиардов. Увы это уже за пределами доступных мне технических возможностей.

Кстати

Цитата:

Finished complete search for 12 steps (15!,16!,17!) Ran 55 hours, 19 trillion
nodes using 12 threads on a 3930K.

mertz обсчитал все поледовательности длиной 12. Это лежит за пределами моей фантазии.

[Nataly-Mak]

Pavlovsky
срочно переходите на PARI/GP
Кроме шуток: быстродействие этого языка потрясающее!
Вот svb всегда пытался меня (и не только меня!) убедить в том, что быстродействие от языка нисколько не зависит. Но очевидно же, что это не так. Я за свою долгую программистскую практику не раз в этом убеждалась.
Только что привела пример с экспериментом, выполненным Максом.
Там квадраты были знаете какого порядка? 12-го! Представили полный перебор для квадратов этого порядка (хотя и классических; ну там, конечно, некоторые условия заданы, квадраты-то ищутся определённого вида; но всё равно перебор просто огромадный)?? В-о-о-т! А программа на PARI/GP всё это пощёлкала за 8 часов.

Язык очень прост для освоения. Вот смотрю на текст программы Макса, ну всё очень просто.

-- Ср мар 20, 2013 15:25:30 --

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

Эх если бы была техническая возможность делать полный перебор хотя бы для последовательностей длиной 9 опраций! Я бы давно имел 25 баллов. А так получается последовательностей длиной 8 около 6 миллионов. Последовательностей длиной 9 несколько миллиардов. Увы это уже за пределами доступных мне технических возможностей.

Да не переживайте вы так
Мои технические возможности в разы скромнее (у меня вообще почти все возможности - лист бумаги и карандаш). И ничего, вполне себе довольна своими результатами (лично своими, а не командными; командные, кстати сказать, у нас пока не блещут).
Ну что хорошего: написать код программы, загнать его в машину и тоскливо смотреть как она молотит это сутками??

-- Ср мар 20, 2013 15:27:41 --

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

Кстати

Цитата:

Finished complete search for 12 steps (15!,16!,17!) Ran 55 hours, 19 trillion
nodes using 12 threads on a 3930K.

mertz обсчитал все поледовательности длиной 12. Это лежит за пределами моей фантазии.

А тут я не совсем поняла, о каких 12 шагах идёт речь. В скобках упоминаются 15!,16!,17!.

[mertz]

15! 347 solutions, 16! 215 solutions, 17! 13 solutions. As pointed out by Pavlovsky, these are not unique solutions. Each solution has at least one number that is different. For 17!, there are just 2 unique base 9 sequences.

[Nataly-Mak]

Интересна бета-таблица конкурса, вот первая двадцатка участников:

Цитата:

1 24.85 Martin Piotte Montreal, Quebec, Canada 17 Mar 2013 19:36
2 24.83 Tomas Rokicki Palo Alto, California, United States 22 Feb 2013 03:36
3 24.58 Hermann Jurksch Recklinghausen, Germany 14 Mar 2013 23:03
4 24.30 Valentin Dobrota Constanta, Romania 7 Feb 2013 11:05
5 24.13 Herbert Kociemba Darmstadt, Germany 10 Mar 2013 10:09
6 23.97 John Morris Simi Valley, California, United States 5 Mar 2013 14:14
7 23.97 Walter Trump Nuremberg, Germany 19 Mar 2013 17:58
8 23.90 Andy Sloane Sunnyvale, California, United States 8 Feb 2013 21:39
9 23.85 Lucien Pech Zürich, Switzerland 10 Mar 2013 09:03
10 23.80 Kalachev Gleb Moscow, Russia 3 Feb 2013 16:52
11 23.66 Siva Dirisala Foster City, California, United States 18 Mar 2013 07:35
12 23.59 Alex Chernov Penza, Russia 27 Feb 2013 10:40
13 23.30 Mark Mammel Ellicott City, Maryland, United States 28 Jan 2013 14:22
14 23.30 Rick Hennig Denver, Colorado, United States 15 Feb 2013 14:11
15 23.30 Johan Roos Lund, Sweden 20 Feb 2013 08:23
16 23.28 Helge Keller Karlsruhe, Germany 12 Mar 2013 16:11
17 23.28 Lars Nagel Mainz, Germany 28 Feb 2013 13:33
18 23.26 Dmitry Kamenetsky Adelaide, Australia 14 Mar 2013 22:17
19 23.24 Tyson Jacobs Nashville, Tennessee, United States 11 Feb 2013 04:59
20 23.17 Wes Sampson La Jolla, California, United States 26 Feb 2013 09:04

Pavlovsky
вы в этой таблице на 22-ом месте.
И 25 баллов никто не имеет

-- Ср мар 20, 2013 19:42:45 --

На второй день конкурса завершил своё участие Ярослав Вроблевский (более 18 баллов):

Цитата:

104 18.39 Jarek Wroblewski Wroclaw, Poland 20 Jan 2013 16:47

Круто!
Почему не стал продолжать?

[Nataly-Mak]

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

15! 347 solutions, 16! 215 solutions, 17! 13 solutions. As pointed out by Pavlovsky, these are not unique solutions. Each solution has at least one number that is different. For 17!, there are just 2 unique base 9 sequences.

mertz
Теперь, кажется, понимаю.
Вы проверили ВСЕ последовательности в 12 шагов, чтобы найти все решения для 15!, 16!, 17! ? Это, действительно, здорово!
И у вас сохранена эта база данных из всех последовательностей в 12 шагов?

[Nataly-Mak]

Пошёл последний месяц конкурса.
Положение участников из России в турнирной таблице на сегодня:

Цитата:

16 24.15 Valery Pavlovsky Ekaterinburg, Russia 20 Mar 2013 07:38
20 23.77 Alex Chernov Penza, Russia 27 Feb 2013 10:40
24 23.68 Kalachev Gleb Moscow, Russia 3 Feb 2013 16:52
31 23.34 Vladimir Chirkov Bobruisk, Russia 20 Mar 2013 10:18
46 22.50 Dmitry Ezhov Sterlitamak, Russia 17 Mar 2013 17:18
47 22.48 Vadim Trofimov Saint Petersburg, Russia 4 Mar 2013 05:49
48 22.41 Viktor Polesov Moskow, Russia 17 Mar 2013 07:06
118 17.76 Minin Nikita Moscow, Russia 30 Jan 2013 19:39
130 16.87 Gennady Gusev Rybinsk, Russia 8 Mar 2013 19:01
156 15.45 Vladimir Romanov Kurgan, Russia 29 Jan 2013 18:04
157 15.45 Nikolay Kurtov Novosibirsk, Russia 25 Jan 2013 11:56
227 10.04 Dmitry Shpika Krasnodar, Russia 20 Jan 2013 23:20
228 10.00 Petr Lishaynikov Saint Petersburg, Russia 4 Feb 2013 08:00
229 10.00 Yurii Sigolaev Saint Petersburg, Russia 20 Feb 2013 17:28
237 9.37 Nikolay Medvedev Moscow, Russia 18 Mar 2013 16:16
274 6.87 Petr Philippov Saint-Petersburg, Russia 27 Jan 2013 06:58
285 6.00 Shamil Kurmangaleev Moscow, Russia 30 Jan 2013 20:14
289 5.93 Prokhorov Maxim Voronezh, Russia 23 Feb 2013 15:43
358 1.40 Mikhail Tikhomirov Moscow, Russia 22 Jan 2013 21:02

Pavlovsky лидирует среди россиян.

Кстати, ники конкурсантов, которые известны:

Valery Pavlovsky - Pavlovsky
Alex Chernov - alexBlack
Vladimir Chirkov - Vovka17
Dmitry Ezhov - dmd

Ещё знаю конкурсанта Yurii Sigolaev по теме на форуме ПЕН.
Всё, больше никого не знаю.

Если оценивать выступление россиян на сегодня, оно выглядит не очень здорово.
Казалось бы, задача не ах какая сложная. Скорее всего, тут сказывается слабая техническая база.
Все основные идеи высказаны, все алгоритмы опробованы. Остаётся только кодирование и выполнение программ машиной.

-- Чт мар 21, 2013 11:49:52 --

(Оффтоп)

Для сравнения: участники конкурса "Магические квадраты - ёмкости для воды" (этот конкурс тоже был у Al Zimmermann; первый конкурс, в котором я приняла участие):

Цитата:

18 24.1353 Natalia Makarova Saratov, Russia 11 Jun 2010 19:51
20 23.8074 Peter "inversed" Karpov Podolsk, Russia 4 Apr 2010 15:57
28 22.1789 Sergey Fironov Saint-Petersburg, Russia 29 Mar 2010 09:00
56 13.7703 Valery Pavlovsky Ekaterinburg, Russia 28 May 2010 15:03
80 5.9034 Ivan Kazmenko Saint-Petersburg, Russia 30 May 2010 23:19
115 1.0000 Vladimir Romanov Kurgan, Russia 24 Mar 2010 08:40

(у меня в этом конкурсе была команда).
Правда, и общее количество участников тут намного меньше текущего конкурса - всего 143.
Всё равно, как мне кажется, наблюдается тенденция роста количества участников из России в подобных конкурсах.

[Pavlovsky]

Вот как выглядит рейтинг по странам. Россия, волею организаторов конкурса, попала в Азию. Трое из 19 россиян действительно живут в Азии (в какой части света находится Бобруйск не знаю ). Первая колонка, место лучшего представителя страны. Вторая колонка, название страны. Третья колонка, количество участников.

North America
1   United States   116
3   Canada   13
Europe
2   Germany   62
11   Switzerland   9
14   Romania   6
17   United Kingdom   26
21   Sweden   7
23   France   10
28   Austria   7
Asia
4   Israel   4
8   China   4
16   Russia   19
35   India   14
Australia - Oceania
10   Australia   8
360   New Zealand   1
South America
96   Brazil   2
140   Argentina   2
Africa
103   Morocco   2
188   South Africa   1

[Nataly-Mak]

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

...
Europe
2   Germany   62
11   Switzerland   9
14   Romania               6
17   United Kingdom   26
21   Sweden   7
23   France   10
28   Austria   7

А где Венгрия?
Украины тоже не вижу.
Какая-то "усекновенная" таблица
В Азии Россия на 3-ем месте, в Европе - на 4-ом. Почти одинаково

Не вижу Польши, Бельгии, Финляндии, Японии, Вьетнама...

[Pavlovsky]

В Европе и Азии отрезал страны, лучшие участники которых, занимают ниже 50-го места.

[Nataly-Mak]

Понятно. Я и говорю - "усекновенная" таблица.
Так это вы отрезали? А я думала, что организаторы конкурса.
Ну, это ещё ничего, если вы отрезали

[mertz]

Цитата:

And you still have the database of all sequences in the 12 steps?

Compressing solutions down to 24 bytes each, the file would be about 456TB

[Pavlovsky]

Неспешно готовлю пакет идей для финишного рывка. Покритикуйте, пожалуйста следующую идею.
Идея основана на идеях dmd о поиске хороших делителей.

Примеры оптимальных решений. Показана начальная последовательность и финальные умножения.
N=7; 1,2,3,6,12,72,70; 70*72
N=8; 1,2,4,8,64,63; 63*10*64
N=9; 1,2,3,6,12,72,70; 70*72^2
N=10; 1,2,3,9,81,80; 7*80^2*81
N=12; 1,2,4,6,36,144,150,154; 154*150*144^2
N=12; 1,2,4,6,24,96,2304,2310; 2310*90*2304
Примеры можно продолжать.
Во всех примерах есть делитель N! обладающий свойствами:
1) делитель имеет вид AB^2 или AB;
2) A,B очень большие числа;
3) A получается из B за одну операцию сложения или вычитания.

Возникает задача.
Для заданного N! найти все последовательности длиной 8-11 операций содержащие числа A,B, такие что:
1) A получается из B за одну операцию сложения или вычитания;
2) AB^2 или AB являются делителем N! Можно наложить дополнительное условие A^2 не является делителем N!;
3) A,B больше заданного порога.