# Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки

 На страницу Пред.  1, 2, 3, 4, 5, 6 ... 88  След.
 Печатать страницу | Печатать всю тему Пред. тема | След. тема

 Re: Factorials21.01.2013, 07:30
 Заслуженный участник

06/10/08
6422
 Последний раз редактировалось Xaositect 21.01.2013, 14:05, всего редактировалось 2 раз(а). 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.

 Re: Factorials21.01.2013, 08:02

21/02/10
1594
Екатеринбург
 Последний раз редактировалось Pavlovsky 21.01.2013, 08:11, всего редактировалось 1 раз. Бурный старт! Уже 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/

 Re: Factorials21.01.2013, 10:12

21/02/10
1594
Екатеринбург
 jcmeyrignac в сообщении #674133 писал(а):http://mathforum.org/wagon/current_solu ... s1153.htmlНашел ссылку на алгоритм.

 Re: Factorials21.01.2013, 10:32
 Заблокирован

22/03/08

7154
Саратов
 Последний раз редактировалось Nataly-Mak 21.01.2013, 10:35, всего редактировалось 2 раз(а). О!!Цитата: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 шаговЗабавная закономерность. Конечно, все результаты наверняка плохие. Но удовольствие получила огромное Дальше ещё не составляла последовательности.

 Re: Factorials21.01.2013, 10:43

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

 Re: Factorials21.01.2013, 10:47
 Заблокирован

22/03/08

7154
Саратов
 Последний раз редактировалось Nataly-Mak 21.01.2013, 11:13, всего редактировалось 1 раз. (Оффтоп) Gerbicz в сообщении #674406 писал(а):This puzzle is good for small kids to play with numbers and operations.Такое высказывание мы уже видели Для вас все задачи детские. Но что-то решить их вы не можете Например, вот эти головоломки:http://www.primepuzzles.net/puzzles/puzz_663.htmhttp://www.primepuzzles.net/puzzles/puzz_671.htmО первой из них вы писали, что она детская. Я вам ответила: "Так решите её". Что-то не вижу решения. Вторую головоломку автор сайта Carlos Rivera назвал "жёсткой". Это он так назвал, не я.Вы можете решить эту головоломку? Она ведь тоже, по-вашему, детская.

 Re: Factorials21.01.2013, 11:47

21/02/10
1594
Екатеринбург
 Последний раз редактировалось Pavlovsky 21.01.2013, 11:47, всего редактировалось 2 раз(а). Поиск регулярного решения. Первое что пришло в голову.Представим число $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)

 Re: Factorials21.01.2013, 13:56
 Заслуженный участник

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

 Re: Factorials21.01.2013, 14:04
 Заблокирован

22/03/08

7154
Саратов
 Последний раз редактировалось Nataly-Mak 21.01.2013, 14:09, всего редактировалось 2 раз(а). dimkadimon в сообщении #674450 писал(а):Очень жалко что топы не видно. Я писал Ал и он ответил что топов показывать не будет. Он говорит что не хочет чтобы народ удерживал лучшие решения.Да, это действительно плохо.Странная логика у Ала. В конкурсах Нила лучшие результаты показывали, и, по-моему, никто рекорды не удерживал.Мы в прошлых темах о конкурсах от AZ приводили свои результаты (не последовательности, а число шагов!), например, в теме о конкурсе с перекладыванием карт.-- Пн янв 21, 2013 15:09:21 --Xaositect в сообщении #674491 писал(а):Еще полезный известный факт, который по одной из приводимых раньше ссылок используется: $(2n)!$ делится на $(n!)^2$, а $(2n+1)!$ на $n! (n+1)!$Да, я сейчас смотрела, как на той странице получено решение для N=20. Там как раз используется первое тождество.

 Re: Factorials21.01.2013, 15:08
 Заблокирован

22/03/08

7154
Саратов
 Последний раз редактировалось Nataly-Mak 21.01.2013, 15:25, всего редактировалось 1 раз. Ещё составила 3 последовательности - N = 17 - 19.Плохо, но всё же есть:N=17 - 17 шаговN=18 - 17 шаговN=19 - 19 шаговДля N=20 последовательность известна из 17 шагов.Используя это решение, легко получила для N=21 последовательность из 19 шагов.Теперь на очереди N=22 Ну, решение из 21 шага уже очевидно. И далее методом наращивания пишем до N=37

 Re: Factorials21.01.2013, 15:25

21/02/10
1594
Екатеринбург
 17 шагов для N=20 уже далеко не рекорд!Код:144 .82 Pavlovsky Valery 21 Jan 2013 12:13

 Re: Factorials21.01.2013, 15:28

20/01/13
62
 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.

 Re: Factorials21.01.2013, 15:36
 Заблокирован

22/03/08

7154
Саратов
 Последний раз редактировалось Nataly-Mak 21.01.2013, 15:40, всего редактировалось 1 раз. Цитата:17 шагов для N=20 уже далеко не рекорд!Вот она - факторизация:Код:...4 13 19, 4 13 19 11, 4 13 19 11 17,...И в представлении этих чисел основная сложность. Смотрите: идёт последовательное умножение на простые числа, это большая потеря шагов.У меня всё точно так же. И как избежать эти потери, я не вижу.

 Re: Factorials21.01.2013, 17:11

09/06/12
26
 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.

 Re: Factorials21.01.2013, 20:13

25/08/12
171
Germany
 Последний раз редактировалось Herbert Kociemba 21.01.2013, 20:22, всего редактировалось 2 раз(а). 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-14At least one of these has presumably better solutions by one ore more contestants21-14,22-15,23-16,24-16,25-16

 Показать сообщения за: Все сообщения1 день7 дней2 недели1 месяц3 месяца6 месяцев1 год Поле сортировки АвторВремя размещенияЗаголовок по возрастаниюпо убыванию
 Страница 3 из 88 [ Сообщений: 1310 ] На страницу Пред.  1, 2, 3, 4, 5, 6 ... 88  След.

Модераторы: maxal, Toucan, PAV, Karan, Супермодераторы

#### Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей

 Вы не можете начинать темыВы не можете отвечать на сообщенияВы не можете редактировать свои сообщенияВы не можете удалять свои сообщенияВы не можете добавлять вложения

 Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group