Factorials

[Nataly-Mak]

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

Блин, посмотреть за битвой с трибун? Или все таки вписаться в борьбу за "Bragging Rights"?!

А может, побороться за первое место с конца турнирной таблицы?

[whitefox]

Несмотря на мои насмешки над Gerbicz, признаю, что он достаточно хороший математик и талантливый программист. О чём уже писал ранее

whitefox в сообщении #647509 писал(а):

Вы к нему не справедливы.
Gerbicz вполне хороший математик и талантливый программист.
Вот только характер у него склочный.

Но ведь это закон жизни: если где-то прибыло, то в другом месте убыло.

[Nataly-Mak]

(Оффтоп)

whitefox в сообщении #714396 писал(а):

Несмотря на мои насмешки над Gerbicz, признаю, что он достаточно хороший математик и талантливый программист. О чём уже писал ранее.

"Не лучше ли при жизни быть приличным человеком?" (c) В. Высоцкий

[Pavlovsky]

whitefox в сообщении #714396 писал(а):

Но ведь это закон жизни: если где-то прибыло, то в другом месте убыло.

Вот только на этом форуме Gerbicz почему то всегда поворачивается тем местом где убыло.

[Nataly-Mak]

(Оффтоп)

"Да, я везде. Да, я гений. Смотрите, я здесь первый! И здесь я победил."
Это смысл его сообщений, переданный моими словами, но абсолютно точно.

Цитата:

Rank Score Contestant Last Improvement
1 1.000 Helge Keller Karlsruhe, Germany 20 Apr 2013 16:13
2 1.000 Jarek Wroblewski Wroclaw, Poland 20 Apr 2013 16:30
3 1.000 Robert Gerbicz Halasztelek, Hungary 20 Apr 2013 16:52

Без комментариев...

[dimkadimon]

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

Блин, посмотреть за битвой с трибун? Или все таки вписаться в борьбу за "Bragging Rights"?!

Конечно вписаться!

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

Прибросил алгоритм для 1000! Построить решение длиной около 400 операций легко. Но я так понял лучшее решение сейчас в районе 300 операций.

Мне было не так легко. Я с трудом построил 430. Лучшее сейчас 292. Jarek построил 297 как я понял практически вручную!

[whitefox]

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

Вот только на этом форуме Gerbicz почему то всегда поворачивается тем местом где убыло.

Почему только на этом форуме?
Вы опять к нему не справедливы
Он так поступает везде.

[Pavlovsky]

А вольфрам (вольфрам еще называют железякой ) спокойно работает с 1000!
$1000!=2^{994}*3^{498}*5^{249}*7^{164}*11^{98}*13^{81}*17^{61}*19^{54}*23^{44} *29^{35}*31^{33}*37^{27}*41^{24}*43^{23}*47^{21}*53^{18}*59^{16}*61^{16}*67^{14} *71^{14}*73^{13}*79^{12}*83^{12}*89^{11}*97^{10}*101^9*103^9*107^9*109^9*113^8*127^7 *131^7*137^7*139^7*149^6*151^6*157^6*163^6*167^5*173^5*179^5*181^5*191^5*193^5*197^5 *199^5*211^4*223^4*227^4*229^4*233^4*239^4*241^4*251^3*257^3*263^3*269^3*271^3*277^3 *281^3*283^3*293^3*307^3*311^3*313^3*317^3*331^3*337^2*347^2*349^2*353^2*359^2*367^2 *373^2*379^2*383^2*389^2*397^2*401^2*409^2*419^2*421^2*431^2*433^2*439^2*443^2*449^2 *457^2*461^2*463^2*467^2*479^2*487^2*491^2*499^2*503*509*521*523*541*547*557*563*569 *571*577*587*593*599*601*607*613*617*619*631*641*643*647*653*659*661*673*677*683*691 *701*709*719*727*733*739*743*751*757*761*769*773*787*797*809*811*821*823*827*829*839 *853*857*859*863*877*881*883*887*907*911*919*929*937*941*947*953*967*971*977*983*991*997$

[dimkadimon]

whitefox в сообщении #714396 писал(а):

Несмотря на мои насмешки над Gerbicz, признаю, что он достаточно хороший математик и талантливый программист. О чём уже писал ранее

Согласен у него есть большой талант, только очень жалко что он так себя ведёт и этим "портит всю картину". Кстати я думал что рекорд будет не меньше 350, а уже 292!

[Nataly-Mak]

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

Jarek построил 297 как я понял практически вручную!

Jarek действительно гигант. Восхищаюсь!

И при этом он нигде не выпячивает свои заслуги.

-- Вт апр 23, 2013 08:25:02 --

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

А вольфрам (вольфрам еще называют железякой ) спокойно работает с 1000!

Ага, я выше приводила разложение

$1000! = A \cdot (500!)^2$

в Вольфраме. Число А имеет всего 300 десятичных знаков
Так что, можно начать строить решение для 500!, потом к нему добавить число А.
А построение решения для 500! можно начинать с построения решения для 250!
И так далее

Кстати, я читаю сообщения Gerbicz без перевода, это даёт мне прекрасную возможность многое не понимать
Так вот, без перевода поняла следующее: у него есть Бейсик, который спокойно может составить решение для 1016!
Мне бы такой Бейсик
Да плюс ещё кластер (который, я не сомневаюсь, у Gerbicz тоже есть).

Сравниваю производительность своей машины и машины mertz. Примерно в 20 раз.
Поиск решений с добавлением 4 шагов у него выполнялся несколько минут, а у меня 2-3 часа. Поиск решений с добавлением 5 шагов у него выполнялся до 12 часов, у меня это будет уже несколько суток. По одной программе!
Разве не очевидно, что многое решает техника? Особенно в задачах с преобладанием перебора.

[whitefox]

Raw Score -- это Равиль Скорина?

-- 23 апр 2013, 08:36 --

(dimkadimon)

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

этим

Нашли клаву с русской буквой "э"?

[wanderers]

whitefox в сообщении #714388 писал(а):

(Оффтоп)

wanderers в сообщении #714351 писал(а):

Ребята, чего вам неймется? Я выложил описание алгоритма, решающего проблему, поставленную на конкурсе.

Выше уже отмечалось, что Ваше описание Вашего алгоритма из того же разряда, что и описание данное Ферма его Великой теореме.

Пока по поводу моего алгоритма я получил вопросы только от dimkadimon и ему ответил: надо быть либо не в теме, либо не знаю, кем, чтобы не понять, какие таблицы строить. Что касается базы данных, то она никакого отношения к описанному алгоритму не имеет и отвечать о деталях ее построения я не подряжался: поищите халяву в другом месте.

[Pavlovsky]

Алгоритм разбиваем на два этапа.
1) Строим все простые числа.
2) Используя только операцию умножения, строим из простых чисел 1000!

Есть 162 простых числа меньше 1000. То есть после первого этапа у нас будет последовательность длиной 162 плюс небольшие накладные расходы. На втором этапе пользуемся теоремой Оливоса. У нас получится 162(это неверно надо 324) умножения плюс небольшие накладные расходы. Итого получается 324 (это неверно надо 486) операции плюс небольшие накладные расходы.

[Nataly-Mak]

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

Алгоритм разбиваем на два этапа.
1) Строим все простые числа.
2) Используя только операцию умножения, строим из простых чисел 1000!

Есть 162 простых числа меньше 1000. То есть после первого этапа у нас будет последовательность длиной 162 плюс небольшие накладные расходы. На втором этапе пользуемся теоремой Оливоса. У нас получится 162 умножения плюс небольшие накладные расходы. Итого получается 324 операции плюс небольшие накладные расходы.

Что-то я не поняла, разве все простые числа входят в разложение 1000! в первой степени?
Я посмотрела факторизацию 1000!, там степени у простых чисел ого какие.

[Pavlovsky]

Выпишем степени простых чисел из разложения на простые множители 1000!

994,498,249,164,98,81,61,54,44,35,33,27,24,23,21,18,16,14,13,12,11,10,9,8,7,6,5,4,3,2,1

Если бы эта последовательность была аддитивной (показанная последовательность написана задом на перед), тогда по теореме Оливоса у нас было бы 162 умножения. А так придется в последовательность добавить еще несколько чисел, что бы последовательность стала аддитивной. Надо добавить совсем немного 5-6 чисел.

-- Вт апр 23, 2013 10:03:03 --

Ой соврал. умножений потребуется 2*162=324 плюс накладные расходы. Итоговая длина последовательности получается 3*162=486 плюс накладные расходы. Много!