Factorials

[dimkadimon]

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

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

[Nataly-Mak]

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

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

[dimkadimon]

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

участвовать - это не значит, что надо обязательно вводить свои результаты на конкурс.
Участвовать - это решать задачу.
Так участвовал, например, svb в конкурсе с раскрасками. Он активно решал задачу, и это главное. Всё остальное - суета сует

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

[Nataly-Mak]

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

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

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

[Nakilon]

Всем привет.
Я большой велосипедист, участвую под именем 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 разрешены, но отправлять в таком случае рез-таты можно только с одного аккаунта. Иначе, извините, просто не спортивно ..)

[Nataly-Mak]

Nakilon в сообщении #675392 писал(а):

...(и по сути можно было сделать тоже самое на бумаге за час).

Это верно

Цитата:

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

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

Цитата:

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

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

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

Nakilon в сообщении #675392 писал(а):

18 17 (Ruby, бумага)
19 19 (Ruby, бумага)

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

[Nakilon]

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

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

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

-- 23.01.2013, 16:01 --

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

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

участвовать - это не значит, что надо обязательно вводить свои результаты на конкурс.
Участвовать - это решать задачу.
Так участвовал, например, svb в конкурсе с раскрасками. Он активно решал задачу, и это главное. Всё остальное - суета сует

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

Русских, кстати, в конкурсе даже чуть больше, чем кажется на первый взгляд:
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

[Nataly-Mak]

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

[dimkadimon]

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

[Nataly-Mak]

(Оффтоп)

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

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

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

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

[Nataly-Mak]

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

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

[Pavlovsky]

Обсуждение статей, правилами конкурса не запрещено??

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!?

[Nataly-Mak]

Цитата:

Factoring and Factorials

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

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

[Pavlovsky]

Посчитал последовательность \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

[jcmeyrignac]

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