Factorials

[Nataly-Mak]

Ага, понятно.
Подождём, что у Эда.
Он вчера прислал мне решения до N=11 включительно, для N=12 обещал позже прислать.

У Эда такие количества решений:

N=6 - 5
N=7 - 18
N=8 - 65
N=9 - 18
N=10 - 91
N=11 - 12

[mertz]

Цитата:

There is not guarantee. My program does not check everything. Such as Internet based solution (1, 2, 4, 6, 24, 30, 720, 900, 924, 518 400, 479 001 600), she does not find.

I thought the tree pruning I was using resulted in a complete search. Now you have me worried.

[Nataly-Mak]

Мощная группа лидеров (24+):

Цитата:

1 24.94 Hermann Jurksch Recklinghausen, Germany 8 Feb 2013 22:30
2 24.78 Martin Piotte Montreal, Quebec, Canada 14 Feb 2013 02:14
3 24.52 Andy Sloane Sunnyvale, California, United States 8 Feb 2013 21:39
4 24.43 Tomas Rokicki Palo Alto, California, United States 14 Feb 2013 15:59
5 24.37 Valentin Dobrota Constanta, Romania 7 Feb 2013 11:05
6 24.32 Dmitry Kamenetsky Adelaide, Australia 14 Feb 2013 06:33
7 24.28 Herbert Kociemba Darmstadt, Germany 10 Feb 2013 07:31

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

Алексей Чернов тоже примолк. Кончились идеи?

[mertz]

found 56 solutions for 12!

[Nataly-Mak]

mertz
здорово!
Я получила эти решения.
Вы позволите выложить вашу БД на другом форуме?
Здесь вы тоже можете показать ваши решения для N=12.

[Pavlovsky]

Задача. Построить последовательность, которая заканчивается числом кратным заданному K.

Для построения последовательности будем использовать арифметику по модулю K.

Если к последовательности предъявить минимальное требование оптимальности. В последовательности не должно быть одинаковых чисел по модулю K. Тогда задача решается за не более K шагов!

-- Пт фев 15, 2013 09:47:22 --

Пусть мы решаем задачу нахождения последовательности для N=19! Простые числа 19*17*13*11=46189 входят в 19! в первой степени. Тогда можно предположить, что последовательность заканчивается числами: ...,19!/K,19! Где K кратно 46189. При этом допущении, вероятность потерять оптимальное решение минимальна!

[Nataly-Mak]

А у меня лучше всех прочих улучшению поддаётся решение для N=25.
Я уже рассказывала об одной удачной находке. Сейчас в этом же решении, которое состояло из 20 шагов, сэкономила ещё шаг. Стоило посмотреть повнимательнее и вот... нашла.

В решении был такой набор:

...323,336,5120,4784,21,300,6300,...

Активные сомножители: 323,4784,6300, остальные числа пассивные (использованы для получения активных сомножителей).
Теперь делаю такой набор:

...323,300,4800,4784,21,6300,...

Активные сомножители те же, а вот пассивных чисел стало всего 3 вместо 4. И один шаг сэкономлен.

Красиво?
Ну, пока только 19 шагов, а в оптимальном решении 16 шагов. Всё равно довольна новым результатом.
Имею за это решение: 16/19=0.84
Если все решения найти на этом уровне, 21 балл в кармане.

[Pavlovsky]

Цитата:

1,2,3,9,81,80,77,6160,492800,39916800
1,2,3,9,81,80,77,6160,498960,39916800
1,2,3,9,81,80,77,6160,6480,39916800
1,2,3,9,81,80,77,6480,498960,39916800
1,2,3,9,81,80,77,6480,518400,39916800
1,2,3,9,81,80,77,6400,492800,39916800
1,2,3,9,81,80,77,6400,518400,39916800
1,2,3,9,81,80,77,6237,498960,39916800
1,2,3,9,81,80,77,6237,6400,39916800
1,2,3,9,81,80,77,6237,498960,39916800

Все эти последовательности можно считать изоморфными. Все они различные варианты выполнения трех операций умножения: 77*80*80*81=39916800. Естественно их легко получить друг из друга.

-- Пт фев 15, 2013 14:22:42 --

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

Если все решения найти на этом уровне, 21 балл в кармане.

9   23.83   Kalachev Gleb   Moscow, Russia 3 Feb 2013 16:52
19   22.86   Alex Chernov   Penza, Russia 5 Feb 2013 13:29
48   20.37   Viktor Polesov   Moskow, Russia 15 Feb 2013 11:18
54   19.92   Valery Pavlovsky   Ekaterinburg, Russia 15 Feb 2013 09:06
88   17.84   Minin Nikita   Moscow, Russia 30 Jan 2013 19:39
107   16.43   Gennady Gusev   Rybinsk, Russia 14 Feb 2013 19:27
124   15.53   Nikolay Kurtov   Novosibirsk, Russia 25 Jan 2013 11:56
125   15.52   Vladimir Romanov   Kurgan, Russia 29 Jan 2013 18:04
193   10.09   Dmitry Shpika   Krasnodar, Russia 20 Jan 2013 23:20
195   10.00   Petr Lishaynikov   Saint Petersburg, Russia 4 Feb 2013 08:00
236   7.03   Vadim Trofimov   Saint Petersburg, Russia 14 Feb 2013 13:59
239   7.00   Yurii Sigolaev   Saint Petersburg, Russia 11 Feb 2013 11:26
240   6.92   Vladimir Chirkov   Bobruisk, Russia 7 Feb 2013 04:59
241   6.87   Petr Philippov   Saint-Petersburg, Russia 27 Jan 2013 06:58
252   6.00   Shamil Kurmangaleev   Moscow, Russia 30 Jan 2013 20:14
257   5.71   Dmitry Ezhov   Sterlitamak, Russia 15 Feb 2013 17:17
280   3.68   Prokhorov Maxim   Voronezh, Russia 11 Feb 2013 18:20
320   1.40   Mikhail Tikhomirov   Moscow, Russia 22 Jan 2013 21:02

Наталия вас явно не хватает в этом списке. Россиян в конкурсе 18. Что меньше чем участников из США (111) и Германии(56). Это поянтно. Но меньше чем англичан(24). А это удивляет. Не порядок!

[dimkadimon]

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

Пусть мы решаем задачу нахождения последовательности для N=19! Простые числа 19*17*13*11=46189 входят в 19! в первой степени. Тогда можно предположить, что последовательность заканчивается числами: ...,19!/K,19! Где K кратно 46189. При этом допущении, вероятность потерять оптимальное решение минимальна!

Интересная идея. А почему последовательность не может закончитъся так: A*11*13, B*17*19, 19!, где 19!=A*B*11*13*17*19 ? В этом случае K=A*11*13 и оно не кратно 46189.

[Pavlovsky]

Все зависит от того как мы получили числа A*11*13, B*17*19. Если мы их получили умножением:
A*11*13=A'*(K1*11*13), B*17*19=B'*(K2*17*19), тогда последовательность может быть такой

T1=(K1*11*13)*(K2*17*19)
T2=A'*B'
T3=T1*T2. Где T1 кратно 11*13*17*19. При этом длина последовательности не изменится.

Все эти рассуждения основаны на гипотезе озвученной Herbert Kociemba .

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

With my approach I need 23 steps for 35!, 36! and 37! . Not really good, but not really bad too. In my approach subtraction and addition occurs only with relatively small numbers. Then these are multiplied. I use 10 multiplications as the last operations for 35!, 36! and 37!.

В моей трактовке:
Гипотеза. Существуют оптимальные последовательности, которые заканчиваются достаточно длинной последовательностью умножений.

Здравый смысл в этой гипотезе есть. Ведь чем больше умножений, тем короче должна быть последовательность. Хотя мои данные не подтверждают эту гипотезу. У меня все рекордные последовательности имеют вид: 1-2 операции сложения/вычитания; 2-3 операции умножения. То есть длиных последовательностей умножений я не видел. 10 подряд умножений это, что то из раздела фантастика.

[Nataly-Mak]

Pavlovsky

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

Наталия вас явно не хватает в этом списке. Россиян в конкурсе 18. Что меньше чем участников из США (111) и Германии(56). Это поянтно. Но меньше чем англичан(24). А это удивляет. Не порядок!

Потерпите, ответ будет по окончании конкурса

[malk]

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

Пусть мы решаем задачу нахождения последовательности для N=19! Простые числа 19*17*13*11=46189 входят в 19! в первой степени. Тогда можно предположить, что последовательность заканчивается числами: ...,19!/K,19! Где K кратно 46189. При этом допущении, вероятность потерять оптимальное решение минимальна!

В решение за 13 ходов, которое мне известно, предпоследнее число не умножается на множитель, кратный 46189.
У меня была такая идея: а - предпоследнее число, b - одно из чисел в последовательности, ab=N!;
с = a/b, с<b - также одно из чисел в последовательности. Начинаем перебирать возможные варианты а(их не очень много), из а получаем b и c; перебором строим кратчайшую последовательность для с, из нее перебором строим последовательность для b. Получается не оптимальная, но достаточно короткая последовательность для N!.

Цитата:

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

В решении для 20! за 14 ходов в конце 4 умножения. Для 21! и 22! за 14 ходов - 2 умножения.

[Pavlovsky]

malk в сообщении #684271 писал(а):

В решении для 20! за 14 ходов в конце 4 умножения. Для 21! и 22! за 14 ходов - 2 умножения.

У меня аналогично. Хотя все может быть. Например короткие последовательности умножений это может быть следствием особенностей алгоритма. Скажем у меня алгоритм заточен на поиск последовательностей с длинными сериями умножений в конце. Для 21! за 15 ходов 6 умножений в конце. Для 22! за 15 ходов 5 умножений.

-- Пт фев 15, 2013 18:21:56 --

malk в сообщении #684271 писал(а):

В решение за 13 ходов, которое мне известно, предпоследнее число не умножается на множитель, кратный 46189.

А если поменять местами операции умножения?! Ведь число кратное 46189 обязано появиться в последовательности! В конце концов 19! кратно 46189 .

[mertz]

Цитата:

Let us solve the problem of finding a sequence of N = 19! Prime numbers 19 * 17 * 13 * 11 = 46,189 are 19! in the first degree. Then we can assume that the sequence ends with the numbers ... 19! / K, 19! Where K is a multiple of 46,189. Under this assumption, the probability of losing the best solution is minimal!

It would be 7 or 8 numbers just to get 11,13,17,19.

[Pavlovsky]

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

It would be 7 or 8 numbers just to get 11,13,17,19.

Это если их получать по отдельности. Запустил программу построения числа кратного 46189. Последовательностей из 9-ти чисел (8 операций) с искомым числом нет.