Factorials

[Gerbicz]

Pavlovsky:
"Funny situation. If we share information secretly in off line. Then no one would press charges cheating.
When exchanging information openly. Anyone can read and ~ Use this information. That is why many annoying."

The solution is surprisingly easy: DO NOT CHEAT!

[Nataly-Mak]

Ого!
Pavlovsky
вы делаете успехи уже миновали группу 18+ и оказались в группе 19+

Цитата:

40 19.23 Valery Pavlovsky Ekaterinburg, Russia 2 Feb 2013 05:53

Рада за вас. Вперёд, только вперёд!

[Nataly-Mak]

У меня калькулятор в компьютере считает только до 21!

21! = 51090942171709440000

[svb]

Gerbicz

Цитата:

The solution is surprisingly easy:

А что делать, если попадется кретин (на себя не принимайте), который все-равно будет обвинять в обмане? В этом случае простого решения нет.

[Nataly-Mak]

Gerbicz в сообщении #679244 писал(а):

The solution...

Это называется - зациклился

Gerbicz
пожалуйста, включите уже команду "выход из цикла"

-- Вс фев 03, 2013 09:21:48 --

Ого, на конкурсе уже 333 участника
В десятке по-прежнему жарко. Состав её постоянно меняется. Все участники рвутся в десятку
Ну, разве что кроме тех, кто решил просто отметиться на конкурсе.

[Pavlovsky]

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

Все участники рвутся в десятку

Я тоже рвусь в десятку. Но только тайно, чтоб обмануть других участников.

Пока у меня алгоритм такой.
Перебором строю последовательность задом на перед. Начинаю с искомого числа, раскладываю его на сомножители или слагаемые и так далее.
Чтобы кардинально сократить перебор добавил несколько разумных эвристик. Которые позволяют сократить перебор, но при этом есть вероятность пропустить рекордное решение. У эвристик есть параметры, регулируя которые можно устанавливать соотношение быстрота/качество.

Вот текущие мои результаты. Первая трока N. Вторая строка расчетные рекорды. Третья строка мои результаты.Valentin Dobrota 1 Feb улучшил какой то рекорд. Какой не знаю. Но это точно не N=33 и N=35

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

Временно остановил работу моих алгоритмов на реконструкцию. Надо эффективно решить задачу факторизации числа. Смотрю различные алгоритмы. Думаю реализовать один из них или придумать что то свое адаптированное под конкретные ньюансы алгоритма. Собственно факторизация нужна для задачи. Разложить число на два сомножителя всеми возможными способами.

-- Вс фев 03, 2013 11:18:51 --

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

21! = 51090942171709440000

1      1
2      2
3      6
4      24
5      120
6      720
7      5040
8      40320
9      362880
10      3628800
11      39916800
12      479001600
13      6227020800
14      87178291200
15      1307674368000
16      20922789888000
17      355687428096000
18      6402373705728000
19      121645100408832000
20      2432902008176640000
21      51090942171709440000
22      1124000727777607680000
23      25852016738884976640000
24      620448401733239439360000
25      15511210043330985984000000
26      403291461126605635584000000
27      10888869450418352160768000000
28      304888344611713860501504000000
29      8841761993739701954543616000000
30      265252859812191058636308480000000
31      8222838654177922817725562880000000
32      263130836933693530167218012160000000
33      8683317618811886495518194401280000000
34      295232799039604140847618609643520000000
35      10333147966386144929666651337523200000000
36      371993326789901217467999448150835200000000
37      13763753091226345046315979581580902400000000

[Nataly-Mak]

О!
Pavlovsky
спасибо большое за численные значения факториалов.
Теперь могу умножать столбиком и сверяться по вашим значениям. А то вдруг при умножении столбиком ошибусь, а проверить и негде

Вчера так просто, на листочке, прикинула, как получить последовательность для 28!, используя последовательность для 14!. С ходу нашла решение из 22 шагов.
Сейчас проверю своё решение

Цитата:

Надо эффективно решить задачу факторизации числа.

Значит, всё-таки факторизация нужна Всем нужна!

[Pavlovsky]

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

спасибо большое за численные значения факториалов.

Человек слаб. Не удержался похвастаться возможностями платформы 1С Предприятие.

-- Вс фев 03, 2013 11:33:01 --

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

Значит, всё-таки факторизация нужна Всем нужна!

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

Собственно факторизация нужна для задачи. Разложить число на два сомножителя всеми возможными способами.

[Nataly-Mak]

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

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

спасибо большое за численные значения факториалов.

Человек слаб. Не удержался похвастаться возможностями платформы 1С Предприятие.

Дык ведь нужная всем информация

[malk]

Вместо калькулятора можно использовать http://www.wolframalpha.com/.
Там много чего можно делать, в частности факторизация там называется factor().

[Nataly-Mak]

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

Вчера так просто, на листочке, прикинула, как получить последовательность для 28!, используя последовательность для 14!. С ходу нашла решение из 22 шагов.
Сейчас проверю своё решение

Проверила, нашла ошибку, неправильно разложила на множители

Теперь вроде правильно:

28! = 40116600*(14!)^2

Это по свойству: (2n)! делится на (n!)^2

Используя это разложение и решение для 14!, нашла последовательность для 28! из 22 шагов (впрочем, количество шагов такое же, как было и вчера в ошибочном решении).
Во-о-о-т! А у меня было 32 шага

Можно и для других N улучшить решения, используя это свойство, а также и второе свойство, выложенное выше.

[Nataly-Mak]

Думаю, что для N=20 мне вручную вряд ли удастся улучшить интернетовское решение из 17 шагов, поэтому начинаю с N=21.
Удалось найти решение из 18 шагов, на 1 шаг улучшила
Иду дальше...

[Nataly-Mak]

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

Вместо калькулятора можно использовать http://www.wolframalpha.com/.
Там много чего можно делать, в частности факторизация там называется factor().

Да, хорошая программа, спасибо.
Пример факторизации:



А я вручную раскладывала.
Ну, с этой программой вообще дело быстро пойдёт

[dimkadimon]

Предсказание: скоро у кого-то будет 25 баллов. Мне кажется что Tomas Rokicki (23.94) и Herbert Kociemba (23.93) удерживают одно оптимальное решение и у них на самом деле 24.94 и 24.93. Возможно скоро они получат последнее оптимальное решение и набирут 25.

[Nataly-Mak]

Хе!
Вам и про Tom Sirgedas казалось
Оказалось, что всё только казалось...