Factorials

[Nataly-Mak]

Ах, ну очень красиво, чёрт побери!

Берём оптимальное решение для 26! (тут Pavlovsky громко заявил, где его можно брать ).
Теперь я хочу получить из этого решения решение для 27!
У меня было решение в 18 шагов --- плохое решение.
Нельзя ли улучшить? - думаю вслух.
Эвристика тривиальная: домножить результат для 26! на 27.
Но 27 - очень хорошее число, ибо $27=3^3$.
Чудесно! По ходу вычислений один раз домножаем на 3 выражение, которое потом возводится в квадрат (плюс 1 шаг), и в конце ещё раз домножаем на 3 --- плюс ещё 1 шаг.

Решение в 17 шагов для 27! получено. Конечно, не оптимальное, но уже совсем близко.

Вот скажите: может ли машина такое придумать? Ни в жисть!

(Оффтоп)

Коллеги!
У меня сегодня маленький юбилей - 5 лет на форуме.
Я как коньяк --- "5 звёздочек"
Не сменить ли мне аватар по этому случаю (спрашивала тут уже)?

Прошу прощения за оффтоп, но хочется поделиться радостным событием с коллегами.

[dimkadimon]

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

Коллеги!
У меня сегодня маленький юбилей - 5 лет на форуме.
Я как коньяк --- "5 звёздочек"
Не сменить ли мне аватар по этому случаю (спрашивала тут уже)?

Прошу прощения за оффтоп, но хочется поделиться радостным событием с коллегами.

Поздравляю с юбилеем и жду новый аватар. Кстати я вывосил свой аватар, как вы просили.

-- 22.03.2013, 19:50 --

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

Возникает задача.
Для заданного N! найти все последовательности длиной 8-11 операций содержащие числа A,B, такие что:
1) A получается из B за одну операцию сложения или вычитания;
2) AB^2 или AB являются делителем N! Можно наложить дополнительное условие A^2 не является делителем N!;
3) A,B больше заданного порога.

Хорошая идея. Думаю таких последовательностей будет много. Как выбрать последовательность которую стоит продливать?

[Nataly-Mak]

(Оффтоп)

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

Поздравляю с юбилеем и жду новый аватар.

Спасибо.
Ну, аватар, наверное, не буду менять...

Цитата:

Кстати я вывосил свой аватар, как вы просили.

Я заметила

[Pavlovsky]

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

Думаю таких последовательностей будет много. Как выбрать последовательность которую стоит продливать?

Провел вычислительный эксперимент для 28!
Берем последовательности длиной 8 операций. Ищем в них число выше порога(это будет число B). Удлиняем последовательность на одну операцию (используя сложение или вычитание), это будет число A. Проверяем делится ли факториал на AB^2.

Порог задал 1000000. Пар чисел A,B получилось всего 14, последовательностей где то около сотни.

Выборочно проверил полученные последовательности. Полным перебором добавляя еще три операции, после чего запускал свои процедуры с условным названием "Оливос". Увы все последовательности оказались плохими.

Стандартная ситуация с эвристиками, имеющими слабое математическое обоснование. Сразу же возникает множество исключений и дополнений. Не люблю эвристики, но куда от них деться?!

-- Пт мар 22, 2013 16:39:43 --

Хожу по кругу (или все таки по спирали?!). Решил вернуться к старой идее. Найти все последовательности заданной длины, содержащие число кратное произведению простых чисел, входящих в факториал в первой степени.

[svb]

(Поздравление)

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

Коллеги!
У меня сегодня маленький юбилей - 5 лет на форуме.
Я как коньяк --- "5 звёздочек"
Не сменить ли мне аватар по этому случаю (спрашивала тут уже)?

Прошу прощения за оффтоп, но хочется поделиться радостным событием с коллегами.

Поздравляю с юбилеем! (начало)

[Nataly-Mak]

(Оффтоп)

svb
спасибо большое! Вы очень точно указали "начало"
Да, оно было именно там! Это было моё самое первое сообщение на форуме.
Преогромное спасибо Максу!! Благадаря ему я тогда удержалась в теме...

[Vovka17]

Пожалуй, я рановато поставил крест на своей программе. Вот уже неделю ничего не кодил, только собирал результаты. Не такие и плохие результаты она выдает, как мне сперва показалось. Только вот уж слишком медленно. Ещё не досчитала до конца (точно, что только к понедельнику закончит ). Пока постою рядом с настоящим программистом. Глядишь, ума наберусь

20   23.77   Alex Chernov   Penza, Russia   27 Feb 2013 10:40
21   23.76   Vladimir Chirkov   Bobruisk, Russia   22 Mar 2013 13:16

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

в какой части света находится Бобруйск не знаю

Знаете, конечно! Это у меня не прикол, а реальный город на карте, в котором я живу. Да, он расположен не в России, а в Беларуси. Это могло сбить с толку. Но сам я - россиянин, ничуть белорусом себя не чувствую, и, поэтому, представляю Россию!

[dimkadimon]

Хорошая новость! Al решил давать призы тем кто займет места 3-7. Приз это майка: http://store.mentalfloss.com/the-mental ... ls-T-Shirt
И если очень хорошо его попросить то можно получить что нибудь другое за $25 с того сайта. Теперь есть к чему стремиться.

-- 23.03.2013, 10:28 --

Vovka17 в сообщении #699981 писал(а):

Знаете, конечно! Это у меня не прикол, а реальный город на карте, в котором я живу. Да, он расположен не в России, а в Беларуси. Это могло сбить с толку. Но сам я - россиянин, ничуть белорусом себя не чувствую, и, поэтому, представляю Россию!

Вот это да. А мы то все думали что вы придумали такой город.

[Pavlovsky]

svb как там поживают бескрайние конечные поля?! Оцени задачу.
Дано: конечное поле F порядка p, p простое число. Поле образовано операциями сложения и умножения по модулю p.
Далее задача стандартная. Используя операции сложения, вычитания и умножения, построить из элементов поля минимальную последовательность начинающуюся с 1 и заканчивающуюся 0. Чтобы не было недоразумений, последняя операция не должна быть вычитанием, в середине последовательности не должно быть нулей.

-- Сб мар 23, 2013 10:53:19 --

21   23.76   Vladimir Chirkov   Bobruisk, Russia   22 Mar 2013 13:16

Прижок тигра 2. Ждем выхода боевика "Прижок тигра 3". Где Тигра сразится с китайским мастером кунфу Hanhong Xue.

[Nataly-Mak]

Vovka17 в сообщении #699981 писал(а):

Пока постою рядом с настоящим программистом. Глядишь, ума наберусь

Да, да, постоять рядом с настоящим программистом очень полезно

Алексей пока неизменно занимает первую строчку в моём личном рейтинге программистов России.
Жалко, что в последний месяц Алексей не проявляет активность. Может быть, просто бросил задачу? Перестала интересовать?

Кстати, Ярослав Вроблевский прислал ответ на моё письмо, в котором я спросила, почему он оставил конкурс. Цитировать не буду, он очень подробно объяснил причину.
Если в двух словах: он решал задачу всего одни сутки с карандашом и бумагой; он не видит дальше хороших идей, кроме эффективного программирования (на которое требуется много времени) и получения тех результатов, которые на конкурсе уже давно достигнуты.
Пишет, что будет ждать следующих конкурсов, которые для него будут более интересными.

[Nataly-Mak]

(Оффтоп)

На сайте primepuzzles.net оубликована головоломка о квадратах Стенли из простых чисел:
http://www.primepuzzles.net/puzzles/puzz_681.htm

Pavlovsky
напрасно вы не оценили квадраты Стенли. Карлос (автор указанного сайта) от них в восторге Он пишет, что построить квадрат Стенли сложнее, чем магический квадрат, так как в квадрате Стенли порядка n имеется n! одинаковых сумм. Это он сам догадался, что будет n! одинаковых сумм, чему был очень рад

[Vovka17]

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

Граждане России, иностранные граждане и лица без гражданства. Читайте эту ветку, в ней достаточно информации, чтобы найти решение для 26! в 15 операций.

Очень хотелось бы найти это решение. Но останусь верным своим принципам и пока довольствуюсь лишь 17 шагам для 26!

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

Ждем выхода боевика "Прижок тигра 3". Где Тигра сразится с китайским мастером кунфу Hanhong Xue.

Мастер Xue, говорите?!.. Это вряд ли. Идеи все уже реализованы, и последний месяц планирую потратить лишь на освоение новых эффективных методов программирования - с заделом на будущие конкурсы.

[Nataly-Mak]

svb, похоже, лёг на дно

svb
ау-у-у!
На предложение войти в состав моей команды вы вроде бы и не отказались, но и согласия полного не вижу.
Может быть, индивидуально решитесь участвовать?

[Nataly-Mak]

Активными на конкурсе остаются следующие россияне:

Цитата:

15 24.19 Valery Pavlovsky Ekaterinburg, Russia 23 Mar 2013 05:13
21 23.76 Vladimir Chirkov Bobruisk, Russia 22 Mar 2013 13:16
46 22.55 Viktor Polesov Moskow, Russia 23 Mar 2013 09:18
47 22.55 Dmitry Ezhov Sterlitamak, Russia 23 Mar 2013 15:22

Остальные заснули, притомились малость

[Pavlovsky]

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

Эвристика тривиальная: домножить результат для 26! на 27.

А если попробовать наоборот? Скажем есть решение 19 шагов для 34! А для 33! лучшее решение 20 шагов. Можно ли из решения для 34! убрать число 34, чтобы получить решение для 33!