Factorials

[Nataly-Mak]

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

Полагаю, что оптимальное решение где то в районе 200 операций.

Бабка обещала 250 (но тоже надвое сказала).

Кстати, а какая-нибудь теоретическая оценка оптимального решения для 1000! существует?

[dimkadimon]

Уже 254!

[Xaositect]

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

Кстати, а какая-нибудь теоретическая оценка оптимального решения для 1000! существует?

Насколько мне известно, снизу только $\log_2\log_2 (1000!) + 2$ Скорее всего, какими-нибудь переборными рассуждениями можно сделать не $+2$, а $+5$ или $+10$

[Gerbicz]

2^(2^13)<1000!<=2^(2^14), so you need at least 15 operations. This also means that Nataly couldn't solve quickly this problem with excel tables or with paper and pencil.

[Nataly-Mak]

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

2^(2^13)<1000!<=2^(2^14)

Это правильно надо записать так:

$2^{2^{13}}<1000!<2^{2^{14}}$

Равенство невозможно.

Вольфрам:

$2^{2^{14}}$
4933 decimal digits

$1000!$
2568 decimal digits

Впрочем, и без этого понятно, что равенство невозможно: 1000! не состоит из множителей, которые все есть степени двойки.

(Оффтоп)

И что это он в меня такой влюблённый?
Почти ни одно сообщение не обходится без моего имени.

[Nataly-Mak]

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

Будет вам и 250 шагов.
Погодите чуток - будет и белка и свисток.

Уже есть 250 даже 248 есть.

whitefox
вы довольны?
Рубеж в 250 шагов преодолён и достаточно быстро.

-- Вс апр 28, 2013 06:51:12 --

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

Цитата:

264 may be impossible to be reached by the human race, but I can believe it may be close to the actual optimum.

Не согласен!
Очень грубо оценил потенциал подхода который я использую для решения задачи 1000!
Результат 300 операций практически гарантирован, нужно только время. 280 операций наиболее вероятный результат. 240 операций оптимистический прогноз, нужно что бы хорошо повезло.
И это в рамках подхода, который априори не ищет оптимального решения. И без учета возможности тонкой оптимизации последовательностей.
Полагаю, что оптимальное решение где то в районе 200 операций.

Ждём 200 шагов

[Pavlovsky]

1 1.000(248) Robert Gerbicz Halasztelek, Hungary 27 Apr 2013 23:05
2 .984(252) Helge Keller Karlsruhe, Germany 28 Apr 2013 08:21
3 .922(269) Jarek Wroblewski Wroclaw, Poland 28 Apr 2013 09:35
4 .738(336) Alex Chernov Penza, Russia 27 Apr 2013 14:22
5 .732(339) Lars Nagel Mainz, Germany 28 Apr 2013 05:31
6 .658(377) James Buddenhagen Xico, Veracruz, Mexico 26 Apr 2013 05:23
7 .654(379) Valery Pavlovsky Ekaterinburg, Russia 24 Apr 2013 11:06
8 .641(387) Wes Sampson La Jolla, California, United States 22 Apr 2013 00:33

Встреча перестает быть томной. Борьба в первой восьмерке резко обострилась.

[Nataly-Mak]

Ну, не будем о восьмёрке. Борьба в первой тройке вошла в новое русло.
Тут уже борьба не только за третье место, как вы предсказывали.
Вполне возможно, что и на первом месте пока не окончательный лидер.

Всего 4 шага (операции) отделяют Helge Keller от текущего рекорда. Удивительно!

[Gerbicz]

Nataly: "Total 4 steps (operations) are separated Helge Keller from the current record. It's amazing!"

At this point I would prefer the Time-Weighted Standings (Beta), (why is this still in beta?). Btw it will be interesting to see how people will lost on time, example from the previous contest: Gil Dogon finished on the 5th place, but on the weighted standings only on the 31th place.

Even it could be possible that a one year long contest decides on the first day. Suppose that you sleep in Adelaide, Australia, while in Europe win the contest in few hours.

[Pavlovsky]

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

why is this still in beta?

Наталия перевожу.
Всем известно, что на вас работают не только русские, но и иностранцы. И даже Al работает на вас! Немедленно отдайте приказ Al перейти на альтернативную систему подсчета очков. Gerbicz она больше нравится. Не заставляйте человека нервничать.

[Nataly-Mak]

(Оффтоп)

Pavlovsky
вы, видимо, меня не так поняли. Я специально не перевожу бред Gerbicz (игнорирую)

Активность на конкурсе "1000!" завораживает:

Цитата:

2 .984 Helge Keller Karlsruhe, Germany 28 Apr 2013 08:21
3 .922 Jarek Wroblewski Wroclaw, Poland 28 Apr 2013 09:35
4 .849 Michael Hürter Saarbrücken, Germany 28 Apr 2013 16:36
5 .790 Alex Chernov Penza, Russia 28 Apr 2013 15:41
6 .752 Lars Nagel Mainz, Germany 28 Apr 2013 13:18
7 .665 James Buddenhagen Xico, Veracruz, Mexico 28 Apr 2013 15:15

Зрителям очень весело
Двое конкурсантов уже имеют 0.9+ (не 1.000).
Это отличный результат.
Хочется верить, что решение в 248 шагов не предел, есть лучше.

[Pavlovsky]

Helge Keller опубликовал свой алгоритм построения решения для 1000!
http://tech.groups.yahoo.com/group/AlZi ... ssage/5645

[Nataly-Mak]

Здорово!
Pavlovsky
этот алгоритм может вам помочь улучшить ваш результат?

Вот отличный конкурс, молодец организатор
Можно выкладывать всё.

[Pavlovsky]

Я уже пошел другим путем, назад дороги нет.
Хотя
1000! = 2^512 * (2*3)^256 * (2*3*5*7)^128 * (2*3*5*11*13)^64 * b^32 * c^16 * d^8 * e^4 * f^2 *g
очень интересное разложение.

[dimkadimon]

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

Я уже пошел другим путем, назад дороги нет.
Хотя
1000! = 2^512 * (2*3)^256 * (2*3*5*7)^128 * (2*3*5*11*13)^64 * b^32 * c^16 * d^8 * e^4 * f^2 *g
очень интересное разложение.

Значит g =p1*p2*...pk, где каждое pk простое число >= 503. Но найти g за маленькое количество шагов наверное не так просто?