Factorials

[Xaositect]

Scryer в сообщении #674418 писал(а):

However, I said "good solution" and "(for a particular mathematical definition of "good")" to suggest a general solution for arbitrary N! with an appropriate growth rate. What I wondered was whether this proves the same P != NP conjecture in the Millennium Prize problem, or whether it's a more restricted version of it. (I don't know the answer to this one, and would welcome insight from you or others.)

It's not restricted, it's just somewhat different. Classical computational models and P vs. NP conjecture are formulated in terms of operations with symbols from finite alphabet and considers algorithms working on the entire set of possible words, while Valiant's algebraic version of P vs. NP conjecture takes operations with rational numbers as elementary and allows use of different circuits for different input size. There are no known unconditional implications between classical and Valiant conjectures.

-- Пн янв 21, 2013 08:54:56 --

dimkadimon в сообщении #674391 писал(а):

3. How often do we need to use the negation? We know that we need it for some n.

We can restructure addition-subtraction fragments so that there will be no adjacent subtractions. Maybe it's possible to prove that the number of subtractions is no more than the number of additions and multiplications.

[Pavlovsky]

Бурный старт! Уже 144 участника. Обсуждение началось тоже бурное, как на этом форуме, так и в диcкусcионной группе на Yahoo!

Задача решается алгоритмами динамического программирования. Но размерность задачи такова, что уже даже для N=13, динамический алгоритм будет работать слишком долго.

Значит надо искать регулярные решения. Для себя накладываю табу на написание кода в течение месяца. Буду вгрызаться в теорию. Если чего нарою буду выкладывать в этой теме и дублировать в дискуссионной группе на Yahoo.

-- Пн янв 21, 2013 10:11:26 --

Herbert Kociemba давал ссылку на динамический алгоритм решения задачи конкурса. Куда делась ссылка?

Дублирую ссылку на интересную статью. Ссылку опубликовал Herbert Kociemba в диcкусcионной группе на Yahoo.
http://rjlipton.wordpress.com/2009/02/2 ... actorials/

[Pavlovsky]

jcmeyrignac в сообщении #674133 писал(а):

http://mathforum.org/wagon/current_solu ... s1153.html

Нашел ссылку на алгоритм.

[Nataly-Mak]

О!!

Цитата:

1 23.28 Kalachev Gleb Moscow, Russia 20 Jan 2013 23:16

Класс!

Я пока решаю головоломку без программы, как это делаю часто с конкурсными задачами. Мне нравится решать задачи сначала без программы.
А, между прочим, были времена, когда компьютеров не было. И я уже жила в те времена И задачи решала-таки.
Ну, а поскольку я в конкурсе не участвую, то и вообще могу не писать никакие программы. Вот порешаю немножко для удовольствия и на этом поставлю точку.

Вчера опять просчиталась при подсчёте шагов для 14!
Сообщила, что у меня 12 шагов. Увы, пока только 13.
Часто делаю такую ошибку: забываю писать шаг (он и теряется при подсчёте шагов):

...720, 720^2,...

У меня такая картина получается:

13! - 12 шагов
14! - 13 шагов
15! - 14 шагов
16! - 15 шагов

Забавная закономерность. Конечно, все результаты наверняка плохие. Но удовольствие получила огромное
Дальше ещё не составляла последовательности.

[dimkadimon]

Наконец Herbert Kociemba потерял один top. Значит все таки у других есть шанс. Очень жалко что топы не видно. Я писал Ал и он ответил что топов показывать не будет. Он говорит что не хочет чтобы народ удерживал лучшие решения.

[Nataly-Mak]

(Оффтоп)

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

This puzzle is good for small kids to play with numbers and operations.

Такое высказывание мы уже видели
Для вас все задачи детские. Но что-то решить их вы не можете

Например, вот эти головоломки:
http://www.primepuzzles.net/puzzles/puzz_663.htm
http://www.primepuzzles.net/puzzles/puzz_671.htm
О первой из них вы писали, что она детская. Я вам ответила: "Так решите её".
Что-то не вижу решения.

Вторую головоломку автор сайта Carlos Rivera назвал "жёсткой". Это он так назвал, не я.
Вы можете решить эту головоломку? Она ведь тоже, по-вашему, детская.

[Pavlovsky]

Поиск регулярного решения. Первое что пришло в голову.
Представим число B=\pm 2^0 \pm 2^1 \pm 2^2 \pm 2^3...

Далее составляем последовательность, чтобы в ней были все числа из представления B.
Например.
B=120=5!=2^7-2^3

(1,2,4,8,32,128,120)

[Xaositect]

Еще полезный известный факт, который по одной из приводимых раньше ссылок используется: $(2n)!$ делится на $(n!)^2$, а $(2n+1)!$ на $n! (n+1)!$

[Nataly-Mak]

dimkadimon в сообщении #674450 писал(а):

Очень жалко что топы не видно. Я писал Ал и он ответил что топов показывать не будет. Он говорит что не хочет чтобы народ удерживал лучшие решения.

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

Мы в прошлых темах о конкурсах от AZ приводили свои результаты (не последовательности, а число шагов!), например, в теме о конкурсе с перекладыванием карт.

-- Пн янв 21, 2013 15:09:21 --

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

Еще полезный известный факт, который по одной из приводимых раньше ссылок используется: $(2n)!$ делится на $(n!)^2$, а $(2n+1)!$ на $n! (n+1)!$

Да, я сейчас смотрела, как на той странице получено решение для N=20. Там как раз используется первое тождество.

[Nataly-Mak]

Ещё составила 3 последовательности - N = 17 - 19.
Плохо, но всё же есть:

N=17 - 17 шагов
N=18 - 17 шагов
N=19 - 19 шагов

Для N=20 последовательность известна из 17 шагов.
Используя это решение, легко получила для N=21 последовательность из 19 шагов.
Теперь на очереди N=22 Ну, решение из 21 шага уже очевидно. И далее методом наращивания пишем до N=37

[Pavlovsky]

17 шагов для N=20 уже далеко не рекорд!

144 .82 Pavlovsky Valery 21 Jan 2013 12:13

[jcmeyrignac]

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

Поиск регулярного решения. Первое что пришло в голову.
Представим число B=\pm 2^0 \pm 2^1 \pm 2^2 \pm 2^3...

Далее составляем последовательность, чтобы в ней были все числа из представления B.
Например.
B=120=5!=2^7-2^3

(1,2,4,8,32,128,120)

I wanted to propose binary decomposition.
But you can use powers other than 2.

[Nataly-Mak]

Цитата:

17 шагов для N=20 уже далеко не рекорд!

Вот она - факторизация:

...4 13 19, 4 13 19 11, 4 13 19 11 17,...

И в представлении этих чисел основная сложность. Смотрите: идёт последовательное умножение на простые числа, это большая потеря шагов.
У меня всё точно так же. И как избежать эти потери, я не вижу.

[Scryer]

dimkadimon в сообщении #674450 писал(а):

Наконец Herbert Kociemba потерял один top. Значит все таки у других есть шанс.

Did he? I saw that he had 12.00 but I did not see 13.00. I just assumed he was working toward the next solid record.

I also assumed he had stopped with 8.00 at first because that was the end of 64-bit calculations, and he had not yet gone to an arbitrary precision package or language.

I see from Google that some of the leaders are Haskell experts. Interesting.

[Herbert Kociemba]

Scryer в сообщении #674575 писал(а):

Наконец Herbert Kociemba потерял один top. Значит все таки у других есть шанс.

Definitely you all have a chance, I would be glad to be in the Top Ten in the end. I have no professional programming background, I program very slowly. In the last weeks, I looked which programming environment might be suitable for the competition. Though I use Windows most of the time I here use my Ubuntu Linux, Eclipse with CDT installed and the GMP (Gnu Multiprecision Library). With GMP you can handle arbitrary large integers, and it took me some time to make the library to compile and link. The reason I stopped at 20! was that I have no really good idea to handle larger factorials in the moment. I suspect Tomas Rokicki broke one of my records for 21! or 22!.
Posting scores is in accordance with Al Zimmermanns rules, and I have no problem to give them away:
I believe that for my solutions for 13! to 20! I have 8 points:
13-11,14-11,15-12,16-12,17-12,18-13,19-13,20-14
At least one of these has presumably better solutions by one ore more contestants
21-14,22-15,23-16,24-16,25-16