Factorials

[Nataly-Mak]

В Африке нам первое место будет гарантировано?

[mertz]

Цитата:

8! 40 320 [8] 1,2,4,6,36,32,35,1120,40320 
8! 40 320 [8] 1,2,4,6,36,32,35,1152,40320 
8! 40 320 [8] 1,2,4,6,36,32,35,1260,40320

It is proper to assume that these solutions are also duplicates. When at the end of the sequence is a series of multiplications, the order of multiplication is not important. The above solutions differ only in the order of multiplication of numbers: 32 * 35 * 36 = 40,320.

I will have to think if I can detect this during the search (at a reasonable cost). Not a math person so it is not obvious to me. Anything to decrease nodes generated helps. My biggest problem now is the speed of the containers. I am using the built in versions supplied with Qt. I need to try the Boost and STL libraries to see if they are faster. I have multiple solutions for 18! and 19! now. 20! and 21! would be the last possible with 64-bit integers.

[Nataly-Mak]

Кажется, я выдохлась --- в ручном режиме.
Это всё, что мне удалось найти:

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

Вторая строка - рекорды, они не точные (один из выложенных здесь вариантов); нужна корректировка.
Дальше торможу, ничего уже не улучшается.

[Pavlovsky]

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   18   18   19   19   20
11   11   12   12   12   13   14   14   14   15   16   16   16   17   18   17   19   19   21   21   21   23   21   22   29

Первая строка N. Вторая строка рекорды. Два рекорда (какие не знаю) на единицу меньше. Третья строка мои результаты.

[Nataly-Mak]

Сравнительный анализ --- ЕИ и ИИ

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

[Nataly-Mak]

Можно продолжить
Это решение для 37!, оно получено домножением 36! на 37:

1,2,4,6,..., 36!,37,37!

В решении 25 шагов.
Теперь домножаем на 38 и получаем решение для 38! в 27 шагов:

1,2,4,6,...,36!,37,37!,38,38!

и так далее.

[Nataly-Mak]

Сейчас попробовала в программе mertz искать решение для 38! (это самая первая программа, которая только даёт все числа. порождаемые введённой последовательностью --- такой помощник).
Решение искала на основе разложения

$38! = K \cdot(19!)^2$
$K= 35345263800 = 2^3 \cdot 3 \cdot 5^2 \cdot 7 \cdot 11 \cdot 23 \cdot 29 \cdot 31 \cdot 37$

Особо не думала при наборе сомножителей, что сразу в голову пришло, лежало на поверхности. Здесь хорошо видна схема, по которой я действовала, вручную набирая сомножители. Множитель K представлен в виде следующего произведения:

$K = 322 \cdot 1073 \cdot 102300$

Начальную последовательность для 19! полностью не показываю, она в 13 шагов.

1,2,4,16,...,19!,
(19!)^2,64,80,3080,3000,105300,102300,322,1152,79,1073,345506,35345263800,
523022617466601111760007224100074291200000000

Решение для 38! получилось в 27 шагов.

-- Вс мар 03, 2013 12:51:25 --

И вот улучшение.
Если в предыдущем решении множитель 102300 составлен за 6 шагов, в этом решении - за 4 шага. Зато множитель 1073 в этом решении не удалось составить за 3 шага, а только за 4.
В результате имеем решение в 26 шагов:

1,2,4,16,...,19!,(19!)^2,
100,320,102400,102300,322,208,207,1280,1073,345506,35345263800,
523022617466601111760007224100074291200000000

Вот так и маялась больше месяца
Теперь выдохлась, ничего больше не могу улучшить для конкурсных задач.

-- Вс мар 03, 2013 12:59:26 --

Pavlovsky
вы на границе зоны 23+
Не плохо. В этой зоне наши ребята Алексей и Глеб.
Пройти всю эту зону и прорваться в зону 24+ непросто.

Цитата:

31 22.96 Valery Pavlovsky Ekaterinburg, Russia 2 Mar 2013 06:09

[Pavlovsky]

Уже в 23+

28 23.11 Valery Pavlovsky Ekaterinburg, Russia 3 Mar 2013 10:27

Наконец удалось получить приличный результат для 37! 24 операции. Есть в запасе еще 3 улучшения, но их пока придержу. Они улушают текущий мой результат на единицу, а при этом расчет рекорда становится не достоверным.

-- Вс мар 03, 2013 16:15:23 --

Появилась вот такая идейка. Разложить на множители $N!=A(A \pm 1)K$, где $A=2^{k_1}3^{k_2}$

[Nataly-Mak]

Ого! Хорошо! Поздравляю с продвижением
Надеюсь, что вам удастся прорваться в зону 24+
Ну, а в этой зоне борьба очень острая. Удачи! Болею за вас, за вас и за Алексея.

А у меня для 37! 25 шагов.

[Pavlovsky]

В зону 24+ с текущим подходом, вряд ли удастся прорваться. Как всегда нужны идеи. Если удастся разложить N! на множители:
$N!=A(A \pm 1)B(B \pm 1)C$, где A,B,C имеют вид $2^k3^l$, тогда остается построить последовательность содержащюю A,B,C. Так как A,B,C имеют специальный вид, то перебор должен стать намного меньше.

[Pavlovsky]

Есть 13 для 19!. Мои компьютеры и программы ну очень глупые. Сколько времени не могли найти рекорд. А я немного подумал и ручками собрал решение. Жаль, что в текущем конкурсе не публикуют информацию сколько человек повторило рекорд. Интересно сколько человек осилило 13 для 19!?!

Забавное свойство, посчитайте количество операций слева и справа от равенства:

A^2*B*(B+1)=(A*B)*(A*B+A)

[Nataly-Mak]

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

Есть 13 для 19!. Мои компьютеры и программы ну очень глупые. Сколько времени не могли найти рекорд. А я немного подумал и ручками собрал решение.

Побеждает ЕИ?

Цитата:

Забавное свойство, посчитайте количество операций слева и справа от равенства:

A^2*B*(B+1)=(A*B)*(A*B+A)

Что же тут забавного? Простая алгебра
Я в ручном режиме таких алгебраических преобразований десятки делала.

[Pavlovsky]

http://tech.groups.yahoo.com/group/AlZi ... ssage/5469

macroxue выложил точные текущие рекорды. Проверил их на своих данных, все верно.

macroxue это он?

13 23.91 Hanhong Xue Fuzhou, China 7 Mar 2013 01:52

Тогда именно он оттеснил Россию в чемпионате Азии на третье место. А где же наши лидеры?!

15 23.77 Alex Chernov Penza, Russia 27 Feb 2013 10:40
18 23.68 Kalachev Gleb Moscow, Russia 3 Feb 2013 16:52

Как всегда. Первая строка 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   18   18   18   17   19   18   20
11   11   12   12   12   13   13   14   14   15   16   16   16   17   18   17   18   19   20   19   20   20   21   21   23

-- Чт мар 07, 2013 09:07:04 --

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

Что же тут забавного? Простая алгебра

Видать настала пора заняться простой алгеброй. Например найти все числа вида A*(A+1) которые являются делителем N! До 37! конечно не дойти, но первый миллиард, простым перебором, проверить можно.

[Nataly-Mak]

Итак, впереди России Израиль, Китай... это по Азии. А если брать по Европе и по миру... Всё закономерно! Не удивляюсь ничуть.

Вчера дочь привезла фильм... Посмотрела. Волосы дыбом! Но об этом не здесь.

[mertz]

Hanhong Xue won the AZPC Prime Sums Contest. The contest should be on the old AZPC site, but JC never got it uploaded.