2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8 ... 88  След.
 
 Re: Factorials
Сообщение23.01.2013, 10:27 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #674516 писал(а):
Ещё составила 3 последовательности - N = 17 - 19.
Плохо, но всё же есть:

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

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


Почему бы вам не поучаствовать?

 Профиль  
                  
 
 Re: Factorials
Сообщение23.01.2013, 10:54 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ссылка на тему о конкурсе на форуме ПЕН:
http://e-science.ru/forum/index.php?sho ... 028&st=220
Там продолжаю тему об одном из прежних конкурсов (это была игра тетрик). Тема так и называется - "Играют все!"

dimkadimon
участвовать - это не значит, что надо обязательно вводить свои результаты на конкурс.
Участвовать - это решать задачу.
Так участвовал, например, svb в конкурсе с раскрасками. Он активно решал задачу, и это главное. Всё остальное - суета сует :D
Что касается официального участия, я свою позицию высказала.
Есть хорошая русская поговорка на тему, но не могу её озвучить :-) (содержит ненормативную лексику).

 Профиль  
                  
 
 Re: Factorials
Сообщение23.01.2013, 14:22 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #675313 писал(а):
участвовать - это не значит, что надо обязательно вводить свои результаты на конкурс.
Участвовать - это решать задачу.
Так участвовал, например, svb в конкурсе с раскрасками. Он активно решал задачу, и это главное. Всё остальное - суета сует :D


Но а как же нашествие Русских? Разве вам не хочеться поддержать родину? :)

 Профиль  
                  
 
 Re: Factorials
Сообщение23.01.2013, 14:26 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ну, во-первых, моя поддержка будет весьма и весьма хилая :D
А во-вторых, русские и без меня очень хорошо справляются.

Глеб жжёт! Уже 24.35!
Ближайший его соперник отстаёт более чем на 1 балл.

Эх, вот жалко, что он не здесь (на форуме).

 Профиль  
                  
 
 Re: Factorials
Сообщение23.01.2013, 14:36 
Аватара пользователя


23/01/13
11
Мелитополь
Всем привет.
Я большой велосипедист, участвую под именем Victor Maslov, Moscow, хотя вообще я из Мелитополя уехал только год назад.
Решаю около суток на самом медленном языке – Ruby.

Пока рез-таты такие:

6 6
7 7
8 8
9 8
10 9
11 9
12 10

13 11
14 11
15 13 (Ruby, бумага)
16 14 (Ruby, бумага)
17 16 (Ruby, бумага)
18 17 (Ruby, бумага)
19 19 (Ruby, бумага)



36 29 (Mathematica + paper)

Если кому интересно, для попадания на 12 место 20 января было достаточно программы, выполняющейся за 0.001 секунды (и по сути можно было сделать тоже самое на бумаге за час). Сейчас же брожу по деревьям. А этой ночью из первой 20-ки меня вытолкало нашествие человек из десяти, внезапно появившихся, иностранцев – подозреваю какую-то утечку или спойлер. Пензенца вроде бы тоже не было в топе.

А вообще хотелось бы на всякий случай напомнить, что согласно официальным правилам, collaborations разрешены, но отправлять в таком случае рез-таты можно только с одного аккаунта. Иначе, извините, просто не спортивно ..)

 Профиль  
                  
 
 Re: Factorials
Сообщение23.01.2013, 14:57 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Nakilon в сообщении #675392 писал(а):
...(и по сути можно было сделать тоже самое на бумаге за час).

Это верно :-)

Цитата:
Пензенца вроде бы тоже не было в топе.

И что? Пензенец - это Алексей Чернов (alexBlack здесь на форуме). Очень талантливый программист, часто занимает высокие места на конкурсах.

Цитата:
А вообще хотелось бы на всякий случай напомнить, что согласно официальным правилам, collaborations разрешены, но отправлять в таком случае рез-таты можно только с одного аккаунта. Иначе, извините, просто не спортивно ..)

На всякий случай... мы в курсе, не в первый раз участвуем в конкурсах. И командой участвовали и индивидуально.
Вы можете не волноваться, среди конкурсантов из России обманщиков не имеется :D

-- Ср янв 23, 2013 16:04:08 --

Nakilon в сообщении #675392 писал(а):
18 17 (Ruby, бумага)
19 19 (Ruby, бумага)

У меня такие же, без всяких программ.
Имею все 25 решений, получены на листе бумаги, сообщала об этом выше.

 Профиль  
                  
 
 Re: Factorials
Сообщение23.01.2013, 15:17 
Аватара пользователя


23/01/13
11
Мелитополь
Nataly-Mak в сообщении #675399 писал(а):
У меня такие же, без всяких программ.
Имею все 25 решений, получены на листе бумаги, сообщала об этом выше.


Здорово ..)
А я для себя решил, что руками ничего не получится с тех пор, как от "только умножения" перешел к комбинации 3 действий.

-- 23.01.2013, 16:01 --

dimkadimon в сообщении #675384 писал(а):
Nataly-Mak в сообщении #675313 писал(а):
участвовать - это не значит, что надо обязательно вводить свои результаты на конкурс.
Участвовать - это решать задачу.
Так участвовал, например, svb в конкурсе с раскрасками. Он активно решал задачу, и это главное. Всё остальное - суета сует :D


Но а как же нашествие Русских? Разве вам не хочеться поддержать родину? :)


Русских, кстати, в конкурсе даже чуть больше, чем кажется на первый взгляд:
93 10.06 Sergey Dymchenko Bellevue, Washington, United States 19 Jan 2013 19:33
133 5.87 Oleg Mazurov Palo Alto, Califonia, United States 23 Jan 2013 06:27
201 .85 Dmitry Kamenetsky Adelaide, Australia 19 Jan 2013 23:36
232 .50 Oleg Tsodikov Ann Arbor, Michigan, United States 21 Jan 2013 15:59

 Профиль  
                  
 
 Re: Factorials
Сообщение23.01.2013, 16:31 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ага, а если посчитать ещё и тех, кто официально не участвует, то будет ещё больше :D
Ну, например, приплюсуйте меня и svb. Хотя svb, может быть, ещё и будет участвовать, я не знаю.

 Профиль  
                  
 
 Re: Factorials
Сообщение24.01.2013, 02:51 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #675313 писал(а):
Ссылка на тему о конкурсе на форуме ПЕН:
http://e-science.ru/forum/index.php?sho ... 028&st=220


А я думал запрещено показывать решения?

Nakilon в сообщении #675414 писал(а):
Русских, кстати, в конкурсе даже чуть больше, чем кажется на первый взгляд:
93 10.06 Sergey Dymchenko Bellevue, Washington, United States 19 Jan 2013 19:33
133 5.87 Oleg Mazurov Palo Alto, Califonia, United States 23 Jan 2013 06:27
201 .85 Dmitry Kamenetsky Adelaide, Australia 19 Jan 2013 23:36
232 .50 Oleg Tsodikov Ann Arbor, Michigan, United States 21 Jan 2013 15:59


Вы меня расскусили :) я Dmitry. Кстати я нашёл ещё потенциальных русских:

75 12.52 Radoslav Kirov Singapore, Singapore 20 Jan 2013 10:07
112 9.09 Igor Dimitrijevic Paris, France 20 Jan 2013 17:53
117 9.00 Peter Skarin Gävle, Sweden 21 Jan 2013 22:02
226 .79 Alexei Moisseenkov Coventry, United Kingdom 23 Jan 2013 11:32
236 .69 Vassili Skarine Waterloo, Ontario, Canada 21 Jan 2013 08:06

 Профиль  
                  
 
 Re: Factorials
Сообщение24.01.2013, 09:21 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов

(Оффтоп)

dimkadimon в сообщении #675629 писал(а):
А я думал запрещено показывать решения?

Не надоело вам обсасывать этот вопрос? Вы уподобляетесь Gerbicz.
Ну, я могла бы показать пример из статьи по приведённой тут ссылке, как представляется 20! Это было бы можно? Предпочла показать своё решение для 13! Кстати, оно не оптимальное и очень простое, его может с ходу сделать каждый (с карандашом и листом бумаги). Так что, не вижу в этом ничего криминального.
Кроме того, я не участвую в конкурсе, поэтому даже если Al увидит в этом нарушение, он не может применить ко мне санкции.
В прошлой теме дело доходило до абсурда. Я привела решение для N=5, которое было приведено на форуме конкурса (тоже не оптимальное). Gerbicz против! Вот там пусть, а здесь не моги :D Разве не абсурд?

Кстати, как там Правила конкурса говорят о копировании известных решений? Это разрешается? :wink:
Я бы запретила копирование "один в один". Модификации разрешила бы.
Например, известное решение для 20! можно вводить только с изменениями, а не точно
такое.
Марафон головоломок на этом форуме проводился. Не интересно! Кто быстрее найдёт решение в Интернете :-)
Головоломки тогда уж такие надо придумывать, чтобы готовых решений не было в Интернете.
Так же и в конкурсах. Ну, в этом конкурсе, как я понимаю, есть в Интернете только одно решение - для 20! Но и оно, впрочем, немало даёт.

 Профиль  
                  
 
 Re: Factorials
Сообщение24.01.2013, 11:31 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Глеб пока держит первое место. Очень трудно держаться, сильные соперники.
Сейчас 24.02 балла у него, а вчера было 24.35.
Алексея Чернова уже отодвинули на 8 позицию.
Да-а-а-а... конкурсантов море, есть из Китая, Индии, Японии.
Победить в таком конкурсе очень не просто!

Но много таких конкурсантов, у кого меньше 1 балла. Ну, так может любой :D Взять готовое решение для 20! и ввести его. Несерьёзно это как-то... Лишь бы отметиться что ли?

 Профиль  
                  
 
 Re: Factorials
Сообщение24.01.2013, 12:12 
Аватара пользователя


21/02/10
1594
Екатеринбург
Обсуждение статей, правилами конкурса не запрещено??

http://perso.ens-lyon.fr/pascal.koiran/ ... ringer.pdf
VALIANT'S MODEL AND THE COST OF COMPUTING INTEGERS
Pascal Koiran
Заинтерисовали следующие утверждения:

Цитата:
For instance, it is tempting to conjecture that the sequences \lfloor 2^n \ln 2 \rfloor,\lfloor 2^n \pi \rfloor,\lfloor 2^n e \rfloor,\lfloor 2^n \sqrt{2} \rfloor,\lfloor {(3/2)}^n  \rfloor are all hard to compute...


Можно ли из этого утверждения сделать эвристический вывод, что числа принадлежащие этим последовательностям лучше не использовать при составлении последовательностей для конкурса? Поскольку они трудные!

Цитата:
The sequence is said to be "ultimately easy" to compute" if there exists another sequence an a_n \in  \HUGE \mathbb{N} such that the sequence a_n x_n is easy to compute.


Сильно не разбирался в этом определении. Может кто объяснит как его можно использовать.

-- Чт янв 24, 2013 14:21:39 --

http://rjlipton.wordpress.com/2009/02/2 ... actorials/
Factoring and Factorials

Цитата:
Let G(n) be the cost of computing Г(n). Then, such a equation would yield that
G(n)\leq G(n/2)+ O({\log}^{O(1)} n)
This implies a fast method of computing n!.


Есть ли в статье алгоритм быстрого вычисления n!?

 Профиль  
                  
 
 Re: Factorials
Сообщение24.01.2013, 12:44 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Цитата:
Factoring and Factorials

Что такое Factoring? Предположу, что это факторизация.
Если это так, то и я говорила выше, что конкурсная задача связана с факторизацией.

Должно быть, интересная статья.

 Профиль  
                  
 
 Re: Factorials
Сообщение24.01.2013, 13:36 
Аватара пользователя


21/02/10
1594
Екатеринбург
Посчитал последовательность \lfloor 2^n \ln 2 \rfloor
Код:
0,1,4,16,83,499,3493,27947,251529,2515292,27668217,...

Ничего особенного в ней нет. Почему эти числа надо считать трудными, непонятно.

А вот если из последовательности
http://oeis.org/A173419
выбрать минимальные числа с длинной последовательности i, то получится забавня последовательность, состоящая из простых чисел.
Код:
1,2,3,5,7,13,41,113,491

 Профиль  
                  
 
 Re: Factorials
Сообщение24.01.2013, 14:00 


20/01/13
62
Pavlovsky в сообщении #675695 писал(а):
Обсуждение статей, правилами конкурса не запрещено??

http://perso.ens-lyon.fr/pascal.koiran/ ... ringer.pdf
VALIANT'S MODEL AND THE COST OF COMPUTING INTEGERS
Pascal Koiran



And this paper references the following one:

On the ultimate complexity of factorials
Q Cheng - STACS 2003, 2003 - Springer
http://www.cs.ou.edu/~qcheng/paper/factorial.pdf

A few more papers here:
http://scholar.google.com/scholar?q=%22 ... torials%22

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1310 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8 ... 88  След.

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



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

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


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

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